doasku

Human-like solver for sudoku

git clone git://git.dimitrijedobrota.com/doasku.git

commit	f8fc7a0c1b8f2edfdb7259eec445c4244dedcf5b
parent	4bd367d95546d5af024d7a6cce8b631ae75cb53a
author	Dimitrije Dobrota <mail@dimitrijedobrota.com>
date	Thu, 4 Apr 2024 19:46:25 +0200

Big code cleanup

Diffstat:

main.cpp

++++++++++++++++++++++++++++++++++++----------------------------------------------

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

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

@@ -24,6 +24,7 @@ struct row_col_t {

row_col_t(row_col_rt rc);

explicit operator row_col_rt() const;

operator uint8_t() const { return 3 * row + col; }

row_col_t absolute(row_col_t rc) { return {uint8_t(row * 3 + rc.row), uint8_t(col * 3 + rc.col)}; }

@@ -51,16 +52,14 @@ struct row_col_rt {

row_col_t::row_col_t(row_col_rt rc) : row(rc.col), col(2 - rc.row) {}

row_col_rt::row_col_rt(row_col_t rc) : row(2 - rc.col), col(rc.row) {}

uint8_t field(row_col_t rc) { return 3 * rc.row + rc.col; }

class Ref {

public:

uint16_t get(uint8_t value) const { return ref[value]; }

void clear(uint8_t value) { ref[value] = 0; }

void zero(uint8_t value) { ref[value] = 0; }

void remove(uint8_t field, uint8_t value) { ref[value] &= ~(1 << field); }

void remove(uint8_t field) {

void clear(uint8_t field, uint8_t value) { ref[value] &= ~(1 << field); }

void clear(uint8_t field) {

for (uint8_t i = 0; i < 9; i++) {

ref[i] &= ~(1 << field);

}

@@ -103,8 +102,6 @@ class Row {

void toggle_all(uint8_t value) { val ^= mask_value << value; }

void clear_all(uint8_t value) { val &= ~(mask_value << value); }

void mask(uint8_t field, uint16_t mask) { val &= ~(uint64_t(mask) << 9 * field); }

friend std::ostream &operator<<(std::ostream &os, Row r) {

for (int i = 0; i < 6; i++) {

os << std::bitset<9>(r.get(i)) << " ";

@@ -130,7 +127,7 @@ class Subgrid {

return 1 + std::countr_zero(get(rc));

}

bool is_finished(row_col_t rc) const { return finished & (1 << ::field(rc)); }

bool is_finished(row_col_t rc) const { return finished & (1 << rc); }

bool is_finished() const { return finished == (1 << 9) - 1; }

void set(row_col_t rc, uint8_t value) {

@@ -143,47 +140,19 @@ class Subgrid {

_set(row_col_rt(rc), value);

_set(rc, value);

const uint8_t field = ::field(rc);

ref.clear(value);

ref.remove(field);

finished |= 1 << field;

}

void clear_row(uint8_t row, uint8_t value) {

assert(row < 3 && value < 9);

ref.zero(value);

ref.clear(rc);

for (uint8_t i = 0; i < 3; i++) {

const row_col_t rc = {row, i};

_clear(row_col_rt(rc), value);

_clear(rc, value);

ref.remove(::field(rc), value);

}

finished |= 1 << rc;

}

void clear_col(uint8_t col, uint8_t value) {

assert(col < 3 && value < 9);

for (uint8_t i = 0; i < 3; i++) {

const row_col_t rc = {i, col};

_clear(row_col_rt(rc), value);

_clear(rc, value);

ref.remove(::field(rc), value);

}

void clear(row_col_t rc, uint8_t value) {

_clear(row_col_rt(rc), value);

_clear(rc, value);

void mask(row_col_t rc, uint16_t mask) {

_mask(row_col_rt(rc), mask);

_mask(rc, mask);

ref.clear(rc, value);

}

void ref_clear(row_col_t rc, uint8_t value) { ref.clear(value); }

void ref_remove(row_col_t rc, uint8_t value) { ref.remove(::field(rc), value); }

void ref_remove(row_col_t rc) { ref.remove(::field(rc)); }

changes_t get_lone() const {

if (is_finished()) return {};

return ref.get_lone();

@@ -290,7 +259,7 @@ class Subgrid {

os << std::endl << "Refs:" << std::endl;

for (uint8_t i = 0; i < 3; i++) {

for (uint8_t j = 0; j < 3; j++) {

std::cout << std::bitset<9>(s.get_ref(::field({i, j}))) << " ";

std::cout << std::bitset<9>(s.get_ref(row_col_t{i, j})) << " ";

}

std::cout << std::endl;

}

@@ -305,9 +274,6 @@ class Subgrid {

void _clear(row_col_t rc, uint8_t value) { rows[rc.row].clear(rc.col, value); }

void _clear(row_col_rt rcr, uint8_t value) { rows[rcr.row].clear(rcr.col + 3, value); }

void _mask(row_col_t rc, uint8_t value) { rows[rc.row].mask(rc.col, value); }

void _mask(row_col_rt rcr, uint8_t value) { rows[rcr.row].mask(rcr.col + 3, value); }

Row rows[3] = {~0, ~0, ~0};

Ref ref;

@@ -332,34 +298,20 @@ class Grid {

const auto ab = subgrid.absolute(field);

subgrids[3 * subgrid.row + 0].clear_row(field.row, value);

subgrids[3 * subgrid.row + 1].clear_row(field.row, value);

subgrids[3 * subgrid.row + 2].clear_row(field.row, value);

subgrids[subgrid.col + 0].clear_col(field.col, value);

subgrids[subgrid.col + 3].clear_col(field.col, value);

subgrids[subgrid.col + 6].clear_col(field.col, value);

rows[ab.row].remove(ab.col);

cols[ab.col].remove(ab.row);

rows[ab.row].clear(value);

cols[ab.col].clear(value);

std::cout << "setting " << (int)value << ": " << ab << std::endl;

for (uint8_t i = 0; i < 9; i++) {

rows[i].remove(ab.col, value);

cols[i].remove(ab.row, value);

_zero(ab, value);

uint8_t trow = subgrid.row * 3 + i / 3;

uint8_t tcol = subgrid.col * 3 + i % 3;

for (uint8_t i = 0; i < 3; i++) {

// clear current block

_clear_row(subgrid, i, value);

rows[trow].remove(tcol, value);

cols[tcol].remove(trow, value);

// clear intersecting row and col

_clear_row(3 * subgrid.row + i, field.row, value);

_clear_col(subgrid.col + 3 * i, field.col, value);

}

std::cout << "setting " << (int)value << ": " << ab << std::endl;

subgrids[::field(subgrid)].set(field, value);

subgrids[subgrid].set(field, value);

}

bool solve() {

@@ -370,9 +322,11 @@ class Grid {

for (uint8_t subgrid = 0; subgrid < 9; subgrid++) {

const auto lones = subgrids[subgrid].get_lone();

for (const auto [field, val] : lones) {

set(subgrid, field, val);

std::cout << "lone: " << subgrid << " " << (int)field << " " << int(val) << std::endl;

std::cout << "lone: " << (int)subgrid << " " << (int)field << " " << int(val)

<< std::endl;

set(subgrid, field, val);

changes++;

}

@@ -383,7 +337,6 @@ class Grid {

const uint8_t subgrid = (row / 3) * 3 + col / 3;

const uint8_t field = (row % 3) * 3 + col % 3;

std::cout << (int)row << " " << (int)col << std::endl;

std::cout << "lone row: " << (int)subgrid << " " << (int)field << " " << int(val)

<< std::endl;

@@ -409,21 +362,17 @@ class Grid {

for (uint8_t i = 0; i < 9; i++) {

const auto naked = subgrids[i].check_naked();

for (const auto [field, mask] : naked) {

subgrids[i].mask(field, mask);

const auto rc = row_col_t(i).absolute(field);

uint16_t tmask = mask;

while (tmask) {

uint16_t idx = std::countr_zero(tmask);

subgrids[i].ref_remove(field, idx);

rows[rc.row].remove(rc.col);

cols[rc.col].remove(rc.row);

_clear(i, field, idx);

tmask ^= 1ull << idx;

}

std::cout << "naked: " << i << " " << (int)field << " " << int(mask) << std::endl;

std::cout << "naked: " << (int)i << " " << (int)field << " " << std::bitset<9>(mask)

<< std::endl;

changes++;

}

@@ -434,8 +383,8 @@ class Grid {

for (const auto [col, val] : rays[0]) {

static uint8_t mapping[9][2] = {{3, 6}, {4, 7}, {5, 8}, {0, 6}, {1, 7},

{2, 8}, {0, 3}, {1, 4}, {2, 5}};

subgrids[mapping[i][0]].clear_col(col, val);

subgrids[mapping[i][1]].clear_col(col, val);

_clear_col(mapping[i][0], col, val);

_clear_col(mapping[i][1], col, val);

std::cout << "col: " << (int)i << " " << (int)col << " " << (int)val << std::endl;

changes++;

@@ -444,8 +393,8 @@ class Grid {

for (const auto [row, val] : rays[1]) {

static uint8_t mapping[9][2] = {{1, 2}, {0, 2}, {0, 1}, {4, 5}, {3, 5},

{3, 4}, {7, 8}, {6, 8}, {6, 7}};

subgrids[mapping[i][0]].clear_row(row, val);

subgrids[mapping[i][1]].clear_row(row, val);

_clear_row(mapping[i][0], row, val);

_clear_row(mapping[i][1], row, val);

std::cout << "row: " << (int)i << " " << (int)row << " " << (int)val << std::endl;

changes++;

@@ -458,6 +407,7 @@ class Grid {

for (uint8_t i = 0; i < 9; i++) {

if (!subgrids[i].is_finished()) return false;

}

return true;

}

@@ -468,7 +418,7 @@ class Grid {

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(field);

std::bitset<9> value = subgrids[subgrid].get(field);

std::cout << value << " ";

if (j % 3 == 2) std::cout << " ";

}

@@ -481,7 +431,7 @@ class Grid {

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(field));

std::bitset<9> value = subgrids[subgrid].get_ref(field);

std::cout << value << " ";

if (j % 3 == 2) std::cout << " ";

}

@@ -512,7 +462,7 @@ class Grid {

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::cout << (int)subgrids[::field(subgrid)].value(field) << " ";

std::cout << (int)subgrids[subgrid].value(field) << " ";

if (j % 3 == 2) std::cout << " ";

}

std::cout << std::endl;

@@ -521,6 +471,38 @@ class Grid {

}

private:

void _clear(row_col_t ab, uint8_t value) {

rows[ab.row].clear(ab.col, value);

cols[ab.col].clear(ab.row, value);

}

void _clear(row_col_t ab) {

rows[ab.row].clear(ab.col);

cols[ab.col].clear(ab.row);

}

void _zero(row_col_t ab, uint8_t value) {

rows[ab.row].zero(value);

cols[ab.col].zero(value);

}

void _clear(row_col_t sg, row_col_t field, uint8_t value) {

_clear(sg.absolute(field), value);

subgrids[sg].clear(field, value);

}

void _clear_row(row_col_t sg, uint8_t row, uint8_t value) {

for (uint8_t i = 0; i < 3; i++) {

_clear(sg, {row, i}, value);

}

void _clear_col(row_col_t sg, uint8_t col, uint8_t value) {

for (uint8_t i = 0; i < 3; i++) {

_clear(sg, {i, col}, value);

}

Subgrid subgrids[9];

Ref rows[9];

Ref cols[9];