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 |
commit36ea6d6c6b8f484e4b4c21bfcbeecbc821658fdb
parentc982a96b1332bb740067be737e7ec8f6a0b43262
authorDimitrije Dobrota <mail@dimitrijedobrota.com>
dateTue, 16 Apr 2024 18:06:46 +0200

Streamline get_naked functions

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

1 files changed, 51 insertions(+), 110 deletions(-)

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

@@ -125,10 +125,6 @@ class Ref {

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;

@@ -143,111 +139,13 @@ class Ref {

return res;
}
auto get_naked_pairs() const {
changes_t res;
for (uint8_t i = 0; i < 9; i++) {
if (std::popcount(value[i]) != 2) continue;
if (seen_naked_pair & (1ul << i)) continue;
for (uint8_t j = i + 1; j < 9; j++) {
if (value[i] != value[j]) continue;
if (seen_naked_pair & (1ul << j)) continue;
seen_naked_pair |= 1ul << i;
seen_naked_pair |= 1ul << j;
uint16_t val = value[i];
while (val) {
const uint8_t idx = std::countr_zero(val);
for (uint8_t pos = 0; pos < 9; pos++) {
if (pos == i || pos == j) continue;
res.emplace_back(pos, idx);
}
val ^= 1ull << idx;
}
}
}
return res;
}
auto get_naked_triplets() const {
changes_t res;
for (uint8_t i = 0; i < 9; i++) {
if (this->res[i]) continue;
if (seen_naked_triplet & (1ul << i)) continue;
for (uint8_t j = i + 1; j < 9; j++) {
if (this->res[j]) continue;
if (seen_naked_triplet & (1ul << j)) continue;
for (uint8_t k = j + 1; k < 9; k++) {
if (this->res[k]) continue;
if (seen_naked_triplet & (1ul << k)) continue;
uint16_t val = value[i] | value[j] | value[k];
if (std::popcount(val) != 3) continue;
seen_naked_triplet |= 1ul << i;
seen_naked_triplet |= 1ul << j;
seen_naked_triplet |= 1ul << k;
while (val) {
const uint8_t idx = std::countr_zero(val);
for (uint8_t pos = 0; pos < 9; pos++) {
if (pos == i || pos == j || pos == k) continue;
res.emplace_back(pos, idx);
}
val ^= 1ull << idx;
}
}
}
}
return res;
}
auto get_naked_quads() const {
changes_t 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); }
for (uint8_t i = 0; i < 9; i++) {
if (this->res[i]) continue;
if (seen_naked_quad & (1ul << i)) continue;
for (uint8_t j = i + 1; j < 9; j++) {
if (this->res[j]) continue;
if (seen_naked_quad & (1ul << j)) continue;
for (uint8_t k = j + 1; k < 9; k++) {
if (this->res[k]) continue;
if (seen_naked_quad & (1ul << k)) continue;
for (uint8_t l = k + 1; l < 9; l++) {
if (this->res[l]) continue;
if (seen_naked_quad & (1ul << l)) continue;
uint16_t val = value[i] | value[j] | value[k] | value[l];
if (std::popcount(val) != 4) continue;
seen_naked_quad |= 1ul << i;
seen_naked_quad |= 1ul << j;
seen_naked_quad |= 1ul << k;
seen_naked_quad |= 1ul << l;
while (val) {
const uint8_t idx = std::countr_zero(val);
for (uint8_t pos = 0; pos < 9; pos++) {
if (pos == i || pos == j || pos == k || pos == l) continue;
res.emplace_back(pos, idx);
}
val ^= 1ull << idx;
}
}
}
}
}
return res;
}
auto get_naked_pairs() const { return get_naked(2); }
auto get_naked_triplets() const { return get_naked(3); }
auto get_naked_quads() const { return get_naked(4); }
private:
changes_t get_hidden(int number) const {

@@ -261,7 +159,7 @@ class Ref {

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++) {
for (uint8_t i = first; i < 9; i++) {
if (std::popcount(ref[i]) < 2) continue;
if (seen_hidden[og] & (1ul << i)) continue;

@@ -295,6 +193,49 @@ class Ref {

return true;
}
changes_t get_naked(int number) const {
assert(number > 1 && number <= 4);
changes_t res;
get_naked(res, number, number, 0, 0);
return res;
}
bool get_naked(changes_t &res, uint8_t og, uint8_t number, uint8_t first, uint16_t val) const {
static uint8_t seen[4] = {0};
if (number != 0) {
for (uint8_t i = first; i < 9; i++) {
if (this->res[i]) continue;
if (number == og && seen_naked[og] & (1ul << i)) continue;
seen[og - number] = i;
bool used = get_naked(res, og, number - 1, i + 1, val | value[i]);
if (!used) continue;
if (number == og) seen_naked[og] |= 1ul << i;
if (number != og) return true;
}
return false;
}
if (std::popcount(val) != og) return false;
while (val) {
const uint8_t idx = std::countr_zero(val);
for (uint8_t pos = 0, i; pos < 9; pos++) {
for (i = 0; i < og; i++) {
if (pos == seen[i]) break;
}
if (i == og) res.emplace_back(pos, idx);
}
val ^= 1ull << idx;
}
return true;
}
static constexpr const std::int64_t mask_field = (1 << 9) - 1;
static constexpr const std::int64_t mask_value = 0x201008040201;

@@ -307,8 +248,8 @@ class Ref {

uint16_t res[9] = {0};
mutable uint16_t seen_hidden[4] = {0};
mutable uint16_t seen_naked[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;
};