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 |
commit5c636d4f8cdc17acaf9b37f1c5a56668061f0c55
parentaded653ae1e36bb63d3d9663569a5b84e930a3df
authorDimitrije Dobrota <mail@dimitrijedobrota.com>
dateTue, 9 Apr 2024 22:18:53 +0200

Better solve iteration loop

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

1 files changed, 142 insertions(+), 225 deletions(-)

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

@@ -372,15 +372,13 @@ class Grid {

void set(row_col_t subgrid, row_col_t field, uint8_t value) {
const auto ab = subgrid.absolute(field);
std::cout << "setting " << (int)value << ": " << ab << std::endl;
rows[ab.row].set(ab.col, value);
cols[ab.col].set(ab.row, value);
subgrids[subgrid].set(field, value);
for (uint8_t i = 0; i < 3; i++) {
_clear_row(subgrid, i, value);
}
_clear_row(subgrid, 0, value);
_clear_row(subgrid, 1, value);
_clear_row(subgrid, 2, value);
const auto [r1, r2] = row_col_t::other_subgrid_row(subgrid);
_clear_row(r1, field.row, value);

@@ -394,311 +392,230 @@ class Grid {

bool solve() {
int iter = 1;
while (iter--) {
uint8_t changes = 0;
for (uint8_t subgrid = 0; subgrid < 9; subgrid++) {
const auto hs = subgrids[subgrid].get_hidden_singles();
for (const auto [field, val] : hs) {
std::cout << "hidden singles: " << (int)subgrid << " " << (int)field << " " << int(val)
<< std::endl;
for (const auto [field, val] : subgrids[subgrid].get_naked_singles()) {
set(subgrid, field, val);
changes++;
}
const auto hp = subgrids[subgrid].get_hidden_pairs();
for (const auto [field, mask] : hp) {
std::cout << "hidden pairs: " << (int)subgrid << " " << (int)field << " "
<< std::bitset<9>(mask) << " " << std::endl;
_mask(subgrid, field, mask);
changes++;
}
const auto ht = subgrids[subgrid].get_hidden_triplets();
for (const auto [field, mask] : ht) {
std::cout << "hidden triples: " << (int)subgrid << " " << (int)field << " "
<< std::bitset<9>(mask) << " " << std::endl;
_mask(subgrid, field, mask);
changes++;
iter = true;
}
}
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;
if (iter) continue;
_mask(subgrid, field, mask);
changes++;
for (uint8_t idx = 0; idx < 9; idx++) {
for (const auto [field, val] : subgrids[idx].get_hidden_singles()) {
set(idx, field, val);
iter = true;
}
const auto ns = subgrids[subgrid].get_naked_singles();
for (const auto [field, val] : ns) {
std::cout << "naked singles: " << (int)subgrid << " " << (int)field << " " << int(val)
<< std::endl;
for (const auto [col, val] : rows[idx].get_hidden_singles()) {
const auto [subgrid, field] = row_col_t(idx, col).relative();
set(subgrid, field, val);
changes++;
}
const auto np = subgrids[subgrid].get_naked_pairs();
for (const auto [val, f1, f2] : np) {
std::cout << "naked pairs: " << (int)subgrid << " " << (int)f1 << " " << (int)f2 << " "
<< (int)val << std::endl;
for (uint8_t field = 0; field < 9; field++) {
if (field == f1 || field == f2) continue;
_clear(subgrid, field, val);
}
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++;
iter = true;
}
const auto nq = subgrids[subgrid].get_naked_quads();
for (const auto [val, f1, f2, f3, f4] : nq) {
std::cout << "naked quads: " << (int)subgrid << " " << (int)f1 << " " << (int)f2 << " "
<< (int)f3 << " " << (int)f4 << " " << (int)val << std::endl;
for (uint8_t field = 0; field < 9; field++) {
if (field == f1 || field == f2 || field == f3 || field == f4) continue;
_clear(subgrid, field, val);
}
changes++;
for (const auto [row, val] : cols[idx].get_hidden_singles()) {
const auto [subgrid, field] = row_col_t(row, idx).relative();
set(subgrid, field, val);
iter = true;
}
}
const auto ptr = subgrids[subgrid].get_pointing_row();
for (const auto [row, val] : ptr) {
std::cout << "pointing row: " << (int)subgrid << " " << (int)row << " " << (int)val
<< std::endl;
if (iter) continue;
for (uint8_t subgrid = 0; subgrid < 9; subgrid++) {
for (const auto [row, val] : subgrids[subgrid].get_pointing_row()) {
const auto [r1, r2] = row_col_t::other_subgrid_row(subgrid);
_clear_row(r1, row, val);
_clear_row(r2, row, val);
changes++;
iter = true;
}
const auto ptc = subgrids[subgrid].get_pointing_col();
for (const auto [col, val] : ptc) {
std::cout << "pointing col: " << (int)subgrid << " " << (int)col << " " << (int)val
<< std::endl;
for (const auto [col, val] : subgrids[subgrid].get_pointing_col()) {
const auto [c1, c2] = row_col_t::other_subgrid_col(subgrid);
_clear_col(c1, col, val);
_clear_col(c2, col, val);
changes++;
iter = true;
}
}
for (uint8_t row = 0; row < 9; row++) {
const auto hs = rows[row].get_hidden_singles();
for (const auto [col, val] : hs) {
std::cout << "hidden singles row: " << (int)row << " " << (int)col << " " << int(val)
<< std::endl;
if (iter) continue;
const auto [subgrid, field] = row_col_t(row, col).relative();
set(subgrid, field, val);
changes++;
for (uint8_t idx = 0; idx < 9; idx++) {
for (const auto [field, mask] : subgrids[idx].get_hidden_pairs()) {
_mask(idx, field, mask);
iter = true;
}
const auto hp = rows[row].get_hidden_pairs();
for (const auto [col, mask] : hp) {
std::cout << "hidden pairs row: " << (int)row << " " << (int)col << " "
<< std::bitset<9>(mask) << " " << std::endl;
for (const auto [col, mask] : rows[idx].get_hidden_pairs()) {
const auto [subgrid, field] = row_col_t(idx, col).relative();
_mask(subgrid, field, mask);
iter = true;
}
const auto [subgrid, field] = row_col_t(row, col).relative();
for (const auto [row, mask] : cols[idx].get_hidden_pairs()) {
const auto [subgrid, field] = row_col_t(row, idx).relative();
_mask(subgrid, field, mask);
changes++;
iter = true;
}
}
const auto ht = rows[row].get_hidden_triplets();
for (const auto [col, mask] : ht) {
std::cout << "hidden triplets row: " << (int)row << " " << (int)col << " "
<< std::bitset<9>(mask) << " " << std::endl;
if (iter) continue;
const auto [subgrid, field] = row_col_t(row, col).relative();
_mask(subgrid, field, mask);
changes++;
for (uint8_t idx = 0; idx < 9; idx++) {
for (const auto [field, mask] : subgrids[idx].get_hidden_triplets()) {
_mask(idx, field, mask);
iter = true;
}
const auto hq = rows[row].get_hidden_quads();
for (const auto [col, mask] : hq) {
std::cout << "hidden quads row: " << (int)row << " " << (int)col << " "
<< std::bitset<9>(mask) << " " << std::endl;
for (const auto [col, mask] : rows[idx].get_hidden_triplets()) {
const auto [subgrid, field] = row_col_t(idx, col).relative();
_mask(subgrid, field, mask);
iter = true;
}
const auto [subgrid, field] = row_col_t(row, col).relative();
for (const auto [row, mask] : cols[idx].get_hidden_triplets()) {
const auto [subgrid, field] = row_col_t(row, idx).relative();
_mask(subgrid, field, mask);
changes++;
iter = true;
}
}
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 << " "
<< (int)val << std::endl;
if (iter) continue;
for (uint8_t col = 0; col < 9; col++) {
if (col == c1 || col == c2) continue;
const auto [subgrid, field] = row_col_t(row, col).relative();
_clear(subgrid, field, val);
}
for (uint8_t idx = 0; idx < 9; idx++) {
for (const auto [field, mask] : subgrids[idx].get_hidden_quads()) {
_mask(idx, field, mask);
iter = true;
}
for (const auto [col, mask] : rows[idx].get_hidden_quads()) {
const auto [subgrid, field] = row_col_t(idx, col).relative();
_mask(subgrid, field, mask);
iter = true;
}
changes++;
for (const auto [row, mask] : cols[idx].get_hidden_quads()) {
const auto [subgrid, field] = row_col_t(row, idx).relative();
_mask(subgrid, field, mask);
iter = true;
}
}
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;
if (iter) continue;
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);
for (uint8_t idx = 0; idx < 9; idx++) {
for (const auto [val, f1, f2] : subgrids[idx].get_naked_pairs()) {
for (uint8_t field = 0; field < 9; field++) {
if (field == f1 || field == f2) continue;
_clear(idx, field, val);
}
changes++;
iter = true;
}
const auto nq = rows[row].get_naked_quads();
for (const auto [val, c1, c2, c3, c4] : nq) {
std::cout << "naked quad row: " << (int)row << " " << (int)c1 << " " << (int)c2 << " "
<< (int)c3 << " " << (int)c4 << " " << (int)val << std::endl;
for (const auto [val, c1, c2] : rows[idx].get_naked_pairs()) {
for (uint8_t col = 0; col < 9; col++) {
if (col == c1 || col == c2 || col == c3 || col == c4) continue;
const auto [subgrid, field] = row_col_t(row, col).relative();
if (col == c1 || col == c2) continue;
const auto [subgrid, field] = row_col_t(idx, col).relative();
_clear(subgrid, field, val);
}
changes++;
iter = true;
}
const auto ptr = rows[row].get_pointing_row();
for (const auto [idx, val] : ptr) {
std::cout << "box line reduction row: " << (int)row << " " << (int)idx << " " << (int)val
<< std::endl;
const auto [r1, r2] = row_col_t::other_subgrid_row(row);
_clear_row((r1 / 3) * 3 + idx, r1 % 3, val);
_clear_row((r2 / 3) * 3 + idx, r2 % 3, val);
changes++;
for (const auto [val, r1, r2] : cols[idx].get_naked_pairs()) {
for (uint8_t row = 0; row < 9; row++) {
if (row == r1 || row == r2) continue;
const auto [subgrid, field] = row_col_t(row, idx).relative();
_clear(subgrid, field, val);
}
iter = true;
}
}
for (uint8_t col = 0; col < 9; col++) {
const auto hs = cols[col].get_hidden_singles();
for (const auto [row, val] : hs) {
std::cout << "hidden singles col: " << (int)row << " " << (int)col << " " << int(val)
<< std::endl;
const auto [subgrid, field] = row_col_t(row, col).relative();
set(subgrid, field, val);
changes++;
}
const auto hp = cols[col].get_hidden_pairs();
for (const auto [row, mask] : hp) {
std::cout << "hidden pairs col: " << (int)row << " " << (int)col << " "
<< std::bitset<9>(mask) << " " << std::endl;
const auto [subgrid, field] = row_col_t(row, col).relative();
_mask(subgrid, field, mask);
changes++;
}
if (iter) continue;
const auto ht = cols[col].get_hidden_triplets();
for (const auto [row, mask] : ht) {
std::cout << "hidden triplets col: " << (int)row << " " << (int)col << " "
<< std::bitset<9>(mask) << " " << std::endl;
for (uint8_t idx = 0; idx < 9; idx++) {
for (const auto [val, f1, f2, f3] : subgrids[idx].get_naked_triplets()) {
for (uint8_t field = 0; field < 9; field++) {
if (field == f1 || field == f2 || field == f3) continue;
_clear(idx, field, val);
}
const auto [subgrid, field] = row_col_t(row, col).relative();
_mask(subgrid, field, mask);
changes++;
iter = true;
}
const auto hq = cols[col].get_hidden_quads();
for (const auto [row, mask] : hq) {
std::cout << "hidden quad col: " << (int)row << " " << (int)col << " "
<< std::bitset<9>(mask) << " " << std::endl;
const auto [subgrid, field] = row_col_t(row, col).relative();
_mask(subgrid, field, mask);
changes++;
for (const auto [val, c1, c2, c3] : rows[idx].get_naked_triplets()) {
for (uint8_t col = 0; col < 9; col++) {
if (col == c1 || col == c2 || col == c3) continue;
const auto [subgrid, field] = row_col_t(idx, col).relative();
_clear(subgrid, field, val);
}
iter = true;
}
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 << " "
<< (int)val << std::endl;
for (const auto [val, r1, r2, r3] : cols[idx].get_naked_triplets()) {
for (uint8_t row = 0; row < 9; row++) {
if (row == r1 || row == r2) continue;
const auto [subgrid, field] = row_col_t(row, col).relative();
if (row == r1 || row == r2 || row == r3) continue;
const auto [subgrid, field] = row_col_t(row, idx).relative();
_clear(subgrid, field, val);
}
changes++;
iter = true;
}
}
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;
if (iter) continue;
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);
for (uint8_t idx = 0; idx < 9; idx++) {
for (const auto [val, f1, f2, f3, f4] : subgrids[idx].get_naked_quads()) {
for (uint8_t field = 0; field < 9; field++) {
if (field == f1 || field == f2 || field == f3 || field == f4) continue;
_clear(idx, field, val);
}
changes++;
iter = true;
}
const auto nq = cols[col].get_naked_quads();
for (const auto [val, r1, r2, r3, r4] : nq) {
std::cout << "naked quad col: " << (int)col << " " << (int)r1 << " " << (int)r2 << " "
<< (int)r3 << " " << (int)r4 << " " << (int)val << std::endl;
for (const auto [val, c1, c2, c3, c4] : rows[idx].get_naked_quads()) {
for (uint8_t col = 0; col < 9; col++) {
if (col == c1 || col == c2 || col == c3 || col == c4) continue;
const auto [subgrid, field] = row_col_t(idx, col).relative();
_clear(subgrid, field, val);
}
iter = true;
}
for (const auto [val, r1, r2, r3, r4] : cols[idx].get_naked_quads()) {
for (uint8_t row = 0; row < 9; row++) {
if (row == r1 || row == r2 || row == r3 || row == r4) continue;
const auto [subgrid, field] = row_col_t(row, col).relative();
const auto [subgrid, field] = row_col_t(row, idx).relative();
_clear(subgrid, field, val);
}
changes++;
iter = true;
}
}
const auto ptr = cols[col].get_pointing_row();
for (const auto [idx, val] : ptr) {
std::cout << "box line reduction col: " << (int)col << " " << (int)idx << " " << (int)val
<< std::endl;
if (iter) continue;
const auto [c1, c2] = row_col_t::other_subgrid_row(col);
_clear_col(idx * 3 + c1 / 3, c1 % 3, val);
_clear_col(idx * 3 + c2 / 3, c2 % 3, val);
for (uint8_t idx = 0; idx < 9; idx++) {
for (const auto [index, val] : rows[idx].get_pointing_row()) {
const auto [r1, r2] = row_col_t::other_subgrid_row(idx);
_clear_row((r1 / 3) * 3 + index, r1 % 3, val);
_clear_row((r2 / 3) * 3 + index, r2 % 3, val);
changes++;
iter = true;
}
}
if (changes) iter++;
for (const auto [index, val] : cols[idx].get_pointing_row()) {
const auto [c1, c2] = row_col_t::other_subgrid_row(idx);
_clear_col(index * 3 + c1 / 3, c1 % 3, val);
_clear_col(index * 3 + c2 / 3, c2 % 3, val);
iter = true;
}
}
}
return _is_finished();