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 |
commitdacb9c0718e06fafa9f537593f512b833aa29db5
parent2fb993f0a6bc697bcbbd0f97cebba384a9053b54
authorDimitrije Dobrota <mail@dimitrijedobrota.com>
dateThu, 4 Apr 2024 13:44:08 +0200

Move streamlining

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

1 files changed, 56 insertions(+), 54 deletions(-)

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

@@ -64,7 +64,7 @@ class Ref {

}
}
changes_t lone() const {
changes_t get_lone() const {
changes_t res;
for (uint8_t i = 0; i < 9; i++) {

@@ -131,20 +131,20 @@ class Subgrid {

bool is_finished(row_col_t rc) const { return finished & (1 << ::field(rc)); }
bool is_finished() const { return finished == (1 << 9) - 1; }
void set(uint8_t field, uint8_t value) {
assert(field < 9 && value < 9);
void set(row_col_t rc, uint8_t value) {
assert(value < 9);
rows[0].clear_all(value);
rows[1].clear_all(value);
rows[2].clear_all(value);
set(row_col_t(field), value);
set(row_col_rt(field), value);
_set(row_col_rt(rc), value);
_set(rc, value);
ref.remove(field);
ref.remove(rc);
ref.clear(value);
finished |= 1 << field;
finished |= 1 << ::field(rc);
}
void clear_row(uint8_t row, uint8_t value) {

@@ -153,8 +153,8 @@ class Subgrid {

for (uint8_t i = 0; i < 3; i++) {
const row_col_t rc = {row, i};
ref.remove(rc, value);
clear(row_col_rt(rc), value);
clear(rc, value);
_clear(row_col_rt(rc), value);
_clear(rc, value);
}
}

@@ -164,26 +164,24 @@ class Subgrid {

for (uint8_t i = 0; i < 3; i++) {
const row_col_t rc = {i, col};
ref.remove(rc, value);
clear(row_col_rt(rc), value);
clear(rc, value);
_clear(row_col_rt(rc), value);
_clear(rc, value);
}
}
changes_t check_lone() {
if (is_finished()) return {};
void mask(row_col_t rc, uint16_t mask) {
_mask(row_col_rt(rc), mask);
_mask(rc, mask);
}
changes_t res = ref.lone();
void remove_ref(row_col_t rc, uint8_t value) { ref.remove(rc, value); }
for (int field = 0, mask = 1; field < 9; field++, mask <<= 1) {
if (finished & mask) continue;
if (std::popcount(get(field)) != 1) continue;
res.emplace_back(field, std::countr_zero(get(field)));
}
return res;
changes_t check_lone() const {
if (is_finished()) return {};
return ref.get_lone();
}
std::array<changes_t, 2> check_ray() {
std::array<changes_t, 2> check_ray() const {
if (is_finished()) return {};
Row o012 = rows[0] | rows[1] | rows[2];

@@ -226,21 +224,18 @@ class Subgrid {

return res;
}
bool check_force() {
if (is_finished()) return false;
changes_t check_naked() const {
if (is_finished()) return {};
static uint8_t count[512];
static uint16_t value[9];
for (uint8_t i = 0; i < 3; i++) {
for (uint8_t j = 0; j < 3; j++) {
const auto field = ::field({i, j});
value[field] = rows[i].get(j);
count[value[field]]++;
}
for (uint8_t field = 0; field < 9; field++) {
value[field] = get(field);
count[value[field]]++;
}
bool res = false;
changes_t res;
for (int field = 0; field < 9; field++) {
const uint8_t popcnt = std::popcount(value[field]);

@@ -253,26 +248,14 @@ class Subgrid {

if (popcnt <= 1 || popcnt != found) continue;
for (uint8_t nfield = 0; nfield < 9; nfield++) {
const row_col_t rc(nfield);
// skip part of the tuple
if (value[field] == value[nfield]) continue;
// are we going to clear any bits?
if (value[field] & value[nfield]) {
mask(row_col_rt(rc), value[field]);
mask(rc, value[field]);
res = true;
// remove cleared from reference
uint16_t tvalue = value[field];
while (tvalue) {
uint16_t idx = std::countr_zero(tvalue);
ref.remove(nfield, idx);
tvalue ^= 1ull << idx;
}
}
if ((value[field] & value[nfield]) == 0) continue;
res.emplace_back(nfield, value[field]);
}
}

@@ -308,20 +291,20 @@ class Subgrid {

}
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); }
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); }
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 _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); }
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;
uint16_t finished = 0;
uint64_t shot = 0;
mutable uint64_t shot = 0;
};
class Grid {

@@ -362,12 +345,27 @@ class Grid {

const auto lones = subgrids[i].check_lone();
for (const auto [field, val] : lones) {
set(i, field, val);
std::cout << "lone: " << i << " " << (int)field << " " << int(val) << std::endl;
changes++;
}
}
for (uint8_t i = 0; i < 9; i++) {
changes += subgrids[i].check_force();
const auto naked = subgrids[i].check_naked();
for (const auto [field, mask] : naked) {
subgrids[i].mask(field, mask);
uint16_t tmask = mask;
while (tmask) {
uint16_t idx = std::countr_zero(tmask);
subgrids[i].remove_ref(field, idx);
tmask ^= 1ull << idx;
}
std::cout << "naked: " << i << " " << (int)field << " " << int(mask) << std::endl;
changes++;
}
}
for (uint8_t i = 0; i < 9; i++) {

@@ -378,6 +376,8 @@ class Grid {

{2, 8}, {0, 3}, {1, 4}, {2, 5}};
subgrids[mapping[i][0]].clear_col(col, val);
subgrids[mapping[i][1]].clear_col(col, val);
std::cout << "col: " << (int)i << " " << (int)col << " " << (int)val << std::endl;
changes++;
}

@@ -386,6 +386,8 @@ class Grid {

{3, 4}, {7, 8}, {6, 8}, {6, 7}};
subgrids[mapping[i][0]].clear_row(row, val);
subgrids[mapping[i][1]].clear_row(row, val);
std::cout << "row: " << (int)i << " " << (int)row << " " << (int)val << std::endl;
changes++;
}
}