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 |
commit86c7bfdad89a06ef8cc35197d4c39d0a5ad42748
parent9abf7bf3f413c07749305dc32de97b8c81395965
authorDimitrije Dobrota <mail@dimitrijedobrota.com>
dateSun, 7 Apr 2024 21:20:46 +0200

Add check for hidden quads

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

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

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

@@ -143,6 +143,57 @@ class Ref {

return res;
}
auto get_hidden_quads() const {
std::vector<std::tuple<uint8_t, uint16_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];
uint8_t size = 0;
uint16_t tval = val;
while (tval) {
const uint8_t idx = std::countr_zero(tval);
fields[size++] = idx;
tval ^= 1ull << idx;
}
uint16_t mask = (1 << i) | (1 << j) | (1 << k) | (1 << l);
for (uint8_t i = 0; i < 4; i++) {
const uint16_t change = value[fields[i]] & ~(value[fields[i]] & mask);
if (!change) continue;
res.emplace_back(fields[i], change);
}
}
}
}
}
return res;
}
auto get_naked_singles() const {
std::vector<std::tuple<uint8_t, uint8_t>> res;

@@ -262,6 +313,7 @@ class Ref {

mutable uint16_t seen_hidden_pair = 0;
mutable uint16_t seen_hidden_triplet = 0;
mutable uint16_t seen_hidden_quads = 0;
mutable uint16_t seen_naked_pair = 0;
mutable uint16_t seen_naked_triplet = 0;

@@ -331,6 +383,15 @@ class Grid {

changes++;
}
const auto hq = subgrids[subgrid].get_hidden_quads();
for (const auto [field, mask] : hq) {
std::cout << "hidden quads: " << (int)subgrid << " " << (int)field << " "
<< std::bitset<9>(mask) << " " << std::endl;
_mask(subgrid, field, mask);
changes++;
}
const auto ns = subgrids[subgrid].get_naked_singles();
for (const auto [field, val] : ns) {

@@ -415,6 +476,17 @@ class Grid {

changes++;
}
const auto hq = rows[row].get_hidden_quads();
for (const auto [col, mask] : hq) {
const auto [subgrid, field] = row_col_t(row, col).relative();
std::cout << "hidden quads row: " << (int)row << " " << (int)col << " "
<< std::bitset<9>(mask) << " " << std::endl;
_mask(subgrid, field, mask);
changes++;
}
const auto np = rows[row].get_naked_pairs();
for (const auto [val, c1, c2] : np) {
std::cout << "naked pairs row: " << (int)row << " " << (int)c1 << " " << (int)c2 << " "

@@ -492,6 +564,17 @@ class Grid {

changes++;
}
const auto hq = cols[col].get_hidden_quads();
for (const auto [row, mask] : hq) {
const auto [subgrid, field] = row_col_t(row, col).relative();
std::cout << "hidden quad col: " << (int)row << " " << (int)col << " "
<< std::bitset<9>(mask) << " " << std::endl;
_mask(subgrid, field, mask);
changes++;
}
const auto np = cols[col].get_naked_pairs();
for (const auto [val, r1, r2] : np) {
std::cout << "naked pairs col: " << (int)col << " " << (int)r1 << " " << (int)r2 << " "