doasku

Human-like solver for sudoku
git clone git://git.dimitrijedobrota.com/doasku.git
Log | Files | Refs | README | LICENSE | HACKING | CONTRIBUTING | CODE_OF_CONDUCT | BUILDING |
commitc982a96b1332bb740067be737e7ec8f6a0b43262
parent7852ef886ef95b2233d9cd52bef2b2b4536ac6fe
authorDimitrije Dobrota <mail@dimitrijedobrota.com>
dateSun, 14 Apr 2024 19:34:52 +0200

Streamline get_hidden functions

Diffstat:
Mmain.cpp|+++++++++++++++++++++++++---------------------------------------------------------

1 files changed, 50 insertions(+), 115 deletions(-)

diff --git a/main.cpp b/main.cpp

@@ -91,23 +91,6 @@ class Ref {

return res;
}
void get_indices(uint8_t indices[9], uint16_t mask) const {
uint8_t size = 0;
while (mask) {
const uint8_t idx = std::countr_zero(mask);
indices[size++] = idx;
mask ^= 1ull << idx;
}
}
void get_hidden_changes(uint8_t fields[9], uint16_t mask, uint8_t n, changes_t &vec) const {
for (uint8_t i = 0; i < n; i++) {
const uint16_t change = value[fields[i]] & ~(value[fields[i]] & mask);
if (!change) continue;
vec.emplace_back(fields[i], change);
}
}
public:
uint16_t get(uint8_t field) const { return value[field]; }
uint16_t get_ref(uint8_t value) const { return ref[value]; }

@@ -142,103 +125,9 @@ class Ref {

return res;
}
auto get_hidden_pairs() const {
changes_t res;
for (uint8_t i = 0; i < 9; i++) {
if (std::popcount(ref[i]) != 2) continue;
if (seen_hidden_pair & (1ul << i)) continue;
for (uint8_t j = i + 1; j < 9; j++) {
if (ref[i] != ref[j]) continue;
if (seen_hidden_pair & (1ul << j)) continue;
seen_hidden_pair |= 1ul << i;
seen_hidden_pair |= 1ul << j;
static uint8_t fields[9];
get_indices(fields, ref[i]);
const uint16_t mask = (1 << i) | (1 << j);
get_hidden_changes(fields, mask, 2, res);
}
}
return res;
}
auto get_hidden_triplets() const {
changes_t res;
for (uint8_t i = 0; i < 9; i++) {
if (std::popcount(ref[i]) < 2) continue;
if (seen_hidden_triplet & (1ul << i)) continue;
for (uint8_t j = i + 1; j < 9; j++) {
if (std::popcount(ref[j]) < 2) continue;
if (seen_hidden_triplet & (1ul << j)) continue;
for (uint8_t k = j + 1; k < 9; k++) {
if (std::popcount(ref[k]) < 2) continue;
if (seen_hidden_triplet & (1ul << k)) continue;
const uint16_t val = ref[i] | ref[j] | ref[k];
if (std::popcount(val) != 3) continue;
seen_hidden_triplet |= 1ul << i;
seen_hidden_triplet |= 1ul << j;
seen_hidden_triplet |= 1ul << k;
static uint8_t fields[9];
get_indices(fields, val);
uint16_t mask = (1 << i) | (1 << j) | (1 << k);
get_hidden_changes(fields, mask, 3, res);
}
}
}
return res;
}
auto get_hidden_quads() const {
changes_t res;
for (uint8_t i = 0; i < 9; i++) {
if (std::popcount(ref[i]) < 2) continue;
if (seen_hidden_quads & (1ul << i)) continue;
for (uint8_t j = i + 1; j < 9; j++) {
if (std::popcount(ref[j]) < 2) continue;
if (seen_hidden_quads & (1ul << j)) continue;
for (uint8_t k = j + 1; k < 9; k++) {
if (std::popcount(ref[k]) < 2) continue;
if (seen_hidden_quads & (1ul << k)) continue;
for (uint8_t l = k + 1; l < 9; l++) {
if (std::popcount(ref[l]) < 2) continue;
if (seen_hidden_quads & (1ul << l)) continue;
uint16_t val = ref[i] | ref[j] | ref[k] | ref[l];
if (std::popcount(val) != 4) continue;
seen_hidden_quads |= 1ul << i;
seen_hidden_quads |= 1ul << j;
seen_hidden_quads |= 1ul << k;
seen_hidden_quads |= 1ul << l;
static uint8_t fields[9];
get_indices(fields, val);
uint16_t mask = (1 << i) | (1 << j) | (1 << k) | (1 << l);
get_hidden_changes(fields, mask, 4, res);
}
}
}
}
return res;
}
auto get_hidden_pairs() const { return get_hidden(2); }
auto get_hidden_triplets() const { return get_hidden(3); }
auto get_hidden_quads() const { return get_hidden(4); }
auto get_naked_singles() const {
changes_t res;

@@ -361,6 +250,51 @@ class Ref {

}
private:
changes_t get_hidden(int number) const {
assert(number > 1 && number <= 4);
changes_t res;
get_hidden(res, number, number, 0, 0, 0);
return res;
}
bool get_hidden(changes_t &res, uint8_t og, uint8_t number, uint8_t first, uint16_t val,
uint16_t mask) const {
if (number != 0) {
for (int i = first; i < 9; i++) {
if (std::popcount(ref[i]) < 2) continue;
if (seen_hidden[og] & (1ul << i)) continue;
bool used = get_hidden(res, og, number - 1, i + 1, val | ref[i], mask | (1 << i));
if (!used) continue;
seen_hidden[og] |= 1ul << i;
if (number != og) return true;
}
return false;
}
if (std::popcount(val) != og) return false;
static uint8_t fields[9];
uint8_t size = 0;
while (val) {
const uint8_t idx = std::countr_zero(val);
fields[size++] = idx;
val ^= 1ull << idx;
}
for (uint8_t i = 0; i < og; i++) {
const uint16_t change = value[fields[i]] & ~(value[fields[i]] & mask);
if (!change) continue;
res.emplace_back(fields[i], change);
}
return true;
}
static constexpr const std::int64_t mask_field = (1 << 9) - 1;
static constexpr const std::int64_t mask_value = 0x201008040201;

@@ -372,7 +306,8 @@ class Ref {

uint16_t res[9] = {0};
mutable uint16_t seen_hidden_pair = 0, seen_hidden_triplet = 0, seen_hidden_quads = 0;
mutable uint16_t seen_hidden[4] = {0};
mutable uint16_t seen_naked_pair = 0, seen_naked_triplet = 0, seen_naked_quad = 0;
mutable uint16_t seen_point_row = 0, seen_point_col = 0;
};