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 |
commit80ab88e90146b327b622201960bae4414106d2e0
parent1f999f0dafb7e5b013add6f89e89a1fb28a60d02
authorDimitrije Dobrota <mail@dimitrijedobrota.com>
dateSun, 7 Apr 2024 19:32:34 +0200

Add check for naked triplets

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

1 files changed, 71 insertions(+), 0 deletions(-)

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

@@ -102,6 +102,35 @@ class Ref {

return res;
}
auto get_naked_triplets() const {
std::vector<std::tuple<uint8_t, uint8_t, uint8_t, uint8_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);
res.emplace_back(idx, i, j, k);
val ^= 1ull << idx;
}
}
}
}
return res;
}
private:
uint16_t value[9] = {mask_field, mask_field, mask_field, mask_field, mask_field,
mask_field, mask_field, mask_field, mask_field};

@@ -111,6 +140,7 @@ class Ref {

uint16_t res[9] = {0};
mutable uint16_t seen_naked_pair = 0;
mutable uint16_t seen_naked_triplet = 0;
};
class Grid {

@@ -180,6 +210,19 @@ class Grid {

changes++;
}
const auto nt = subgrids[subgrid].get_naked_triplets();
for (const auto [val, f1, f2, f3] : nt) {
std::cout << "naked triplets: " << (int)subgrid << " " << (int)f1 << " " << (int)f2 << " "
<< (int)f3 << " " << (int)val << std::endl;
for (uint8_t field = 0; field < 9; field++) {
if (field == f1 || field == f2 || field == f3) continue;
_clear(subgrid, field, val);
}
changes++;
}
}
for (uint8_t row = 0; row < 9; row++) {

@@ -207,6 +250,20 @@ class Grid {

changes++;
}
const auto nt = rows[row].get_naked_triplets();
for (const auto [val, c1, c2, c3] : nt) {
std::cout << "naked triplets row: " << (int)row << " " << (int)c1 << " " << (int)c2 << " "
<< (int)c3 << " " << (int)val << std::endl;
for (uint8_t col = 0; col < 9; col++) {
if (col == c1 || col == c2 || col == c3) continue;
const auto [subgrid, field] = row_col_t(row, col).relative();
_clear(subgrid, field, val);
}
changes++;
}
}
for (uint8_t col = 0; col < 9; col++) {

@@ -234,6 +291,20 @@ class Grid {

changes++;
}
const auto nt = cols[col].get_naked_triplets();
for (const auto [val, r1, r2, r3] : nt) {
std::cout << "naked triplets col: " << (int)col << " " << (int)r1 << " " << (int)r2 << " "
<< (int)r3 << " " << (int)val << std::endl;
for (uint8_t row = 0; row < 9; row++) {
if (row == r1 || row == r2 || row == r3) continue;
const auto [subgrid, field] = row_col_t(row, col).relative();
_clear(subgrid, field, val);
}
changes++;
}
}
if (changes) iter++;