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 |
commit581e11fbb24974750e8491d22fc8ae8dc2585c5b
parent86c7bfdad89a06ef8cc35197d4c39d0a5ad42748
authorDimitrije Dobrota <mail@dimitrijedobrota.com>
dateMon, 8 Apr 2024 18:48:45 +0200

Add check for pointing pairs and triplets

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

1 files changed, 69 insertions(+), 1 deletions(-)

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

@@ -52,6 +52,44 @@ class Ref {

res[field] = value + 1;
}
auto get_pointing() const {
std::array<std::vector<std::tuple<uint8_t, uint8_t>>, 2> res;
for (uint8_t i = 0; i < 9; i++) {
const uint8_t popcnt = std::popcount(ref[i]);
if (popcnt < 2 || popcnt > 3) continue;
uint16_t row_mask = 0x7;
uint16_t col_mask = 0x49;
if ((seen_point_row & (1 << i)) == 0) {
for (uint8_t k = 0; k < 3; k++) {
if (std::popcount(uint16_t(row_mask & ref[i])) == popcnt) {
seen_point_row |= 1 << i;
res[0].emplace_back(k, i);
break;
}
row_mask <<= 3;
}
}
if ((seen_point_col & (1 << i)) == 0) {
for (uint8_t k = 0; k < 3; k++) {
if (std::popcount(uint16_t(col_mask & ref[i])) == popcnt) {
seen_point_col |= 1 << i;
res[1].emplace_back(k, i);
break;
}
col_mask <<= 3;
}
}
}
return res;
}
auto get_hidden_singles() const {
std::vector<std::tuple<uint8_t, uint8_t>> res;

@@ -318,6 +356,9 @@ class Ref {

mutable uint16_t seen_naked_pair = 0;
mutable uint16_t seen_naked_triplet = 0;
mutable uint16_t seen_naked_quad = 0;
mutable uint16_t seen_point_row = 0;
mutable uint16_t seen_point_col = 0;
};
class Grid {

@@ -440,6 +481,33 @@ class Grid {

changes++;
}
const auto pt = subgrids[subgrid].get_pointing();
for (const auto [row, val] : pt[0]) {
static uint8_t mapping[9][2] = {{1, 2}, {0, 2}, {0, 1}, {4, 5}, {3, 5},
{3, 4}, {7, 8}, {6, 8}, {6, 7}};
std::cout << "pointing row: " << (int)subgrid << " " << (int)row << " " << (int)val
<< std::endl;
_clear_row(mapping[subgrid][0], row, val);
_clear_row(mapping[subgrid][1], row, val);
changes++;
}
for (const auto [col, val] : pt[1]) {
static uint8_t mapping[9][2] = {{3, 6}, {4, 7}, {5, 8}, {0, 6}, {1, 7},
{2, 8}, {0, 3}, {1, 4}, {2, 5}};
std::cout << "pointing col: " << (int)subgrid << " " << (int)col << " " << (int)val
<< std::endl;
_clear_col(mapping[subgrid][0], col, val);
_clear_col(mapping[subgrid][1], col, val);
changes++;
}
}
for (uint8_t row = 0; row < 9; row++) {

@@ -716,7 +784,7 @@ class Grid {

bool _is_finished(uint8_t subgrid) {
for (uint8_t i = 0; i < 9; i++) {
if (subgrids[subgrid].get_ref(i)) return false;
if (!subgrids[subgrid].get_value(i)) return false;
}
return true;
}