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 |
commita4a5210429ab211058108e0850c8f284d7a375bc
parent55d045aeca3466f352cab5b9c6059c698dfba614
authorDimitrije Dobrota <mail@dimitrijedobrota.com>
dateWed, 3 Apr 2024 19:34:50 +0200

Add reference counting to find loners in subgrid

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

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

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

@@ -89,6 +89,8 @@ class Subgrid {

uint64_t get(row_col_t rc) const { return rows[rc.row].get(rc.col); }
uint64_t get(row_col_rt rc) const { return rows[rc.row].get(rc.col + 3); }
uint16_t get_ref(row_col_t rc) const { return ref[::field(rc)]; }
uint8_t value(row_col_t rc) const {
if (!is_finished(rc)) return 0;
return 1 + std::countr_zero(get(rc));

@@ -107,7 +109,12 @@ class Subgrid {

set(row_col_t(field), value);
set(row_col_rt(field), value);
for (int i = 0; i < 9; i++) {
ref[i] &= ~(1 << field);
}
finished |= 1 << field;
ref[value] = 0;
}
void clear_row(uint8_t row, uint8_t value) {

@@ -115,6 +122,7 @@ class Subgrid {

for (uint8_t i = 0; i < 3; i++) {
const row_col_t rc = {row, i};
ref[value] &= ~(1 << ::field(rc));
clear(row_col_rt(rc), value);
clear(rc, value);
}

@@ -125,6 +133,7 @@ class Subgrid {

for (uint8_t i = 0; i < 3; i++) {
const row_col_t rc = {i, col};
ref[value] &= ~(1 << ::field(rc));
clear(row_col_rt(rc), value);
clear(rc, value);
}

@@ -142,6 +151,12 @@ class Subgrid {

if (std::popcount(get(field)) != 1) continue;
res.emplace_back(field, std::countr_zero(get(field)));
}
for (int i = 0; i < 9; i++) {
if (std::popcount(ref[i]) != 1) continue;
res.emplace_back(std::countr_zero(ref[i]), i);
}
return res;
}

@@ -229,6 +244,14 @@ class Subgrid {

mask(rc, value[field]);
res = true;
// remove cleared from reference
uint64_t tvalue = value[field];
while (tvalue) {
uint16_t idx = std::countr_zero(tvalue);
ref[idx] &= ~(1 << nfield);
tvalue ^= 1ull << idx;
}
}
}
}

@@ -237,6 +260,34 @@ class Subgrid {

return res;
}
friend std::ostream &operator<<(std::ostream &os, Subgrid s) {
os << std::endl << "Field:" << std::endl;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
std::cout << std::bitset<9>(s.get(row_col_t(i, j))) << " ";
}
std::cout << std::endl;
}
os << std::endl << "Rev:" << std::endl;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
std::cout << std::bitset<9>(s.get(row_col_rt(i, j))) << " ";
}
std::cout << std::endl;
}
os << std::endl << "Refs:" << std::endl;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
std::cout << std::bitset<9>(s.get_ref(row_col_t(i, j))) << " ";
}
std::cout << std::endl;
}
return os;
}
private:
void set(row_col_t rc, uint8_t value) { rows[rc.row].set_field(rc.col, value); }
void set(row_col_rt rcr, uint8_t value) { rows[rcr.row].set_field(rcr.col + 3, value); }

@@ -248,6 +299,8 @@ class Subgrid {

void mask(row_col_rt rcr, uint8_t value) { rows[rcr.row].mask(rcr.col + 3, value); }
Row rows[3] = {~0, ~0, ~0};
uint16_t ref[9] = {mask_field, mask_field, mask_field, mask_field, mask_field,
mask_field, mask_field, mask_field, mask_field};
uint16_t finished = 0;
uint64_t shot = 0;

@@ -343,6 +396,19 @@ class Grid {

if (i % 3 == 2) std::cout << std::endl;
}
std::cout << "Refs: " << std::endl;
for (uint8_t i = 0; i < 9; i++) {
for (uint8_t j = 0; j < 9; j++) {
const row_col_t subgrid = {uint8_t(i / 3), uint8_t(j / 3)};
const row_col_t field = {uint8_t(i % 3), uint8_t(j % 3)};
std::bitset<9> value = subgrids[::field(subgrid)].get_ref(field);
std::cout << value << " ";
if (j % 3 == 2) std::cout << " ";
}
std::cout << std::endl;
if (i % 3 == 2) std::cout << std::endl;
}
std::cout << "Board: " << std::endl;
for (uint8_t i = 0; i < 9; i++) {
for (uint8_t j = 0; j < 9; j++) {