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
commit bcd759724a4653673d65a047a8c56b1d3b026a7f
parent a4a5210429ab211058108e0850c8f284d7a375bc
author Dimitrije Dobrota < mail@dimitrijedobrota.com >
date Thu, 4 Apr 2024 12:37:38 +0200

Extract reference logic and general streamlining

Diffstat:
M main.cpp | ++++++++++++++++++++++++++++++++++++++++++++++++ ----------------------------------

1 files changed, 60 insertions(+), 42 deletions(-)

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

@@ -12,6 +12,9 @@

static constexpr const std::int64_t mask_field = (1 << 9) - 1;
static constexpr const std::int64_t mask_value = 0x201008040201;

using change_t = std::tuple<uint8_t, uint8_t>;
using changes_t = std::vector<change_t>;

class row_col_t;
class row_col_rt;

@@ -48,6 +51,35 @@ 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(row_col_t rc) const { return ref[::field(rc)]; }

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

void remove(row_col_t rc, uint8_t value) { ref[value] &= ~(1 << ::field(rc)); }
void remove(row_col_t rc) {
for (uint8_t i = 0; i < 9; i++) {
ref[i] &= ~(1 << ::field(rc));
}
}

changes_t lone() const {
changes_t res;

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

return res;
}

private:
uint16_t ref[9] = {mask_field, mask_field, mask_field, mask_field, mask_field,
mask_field, mask_field, mask_field, mask_field};
};

class Row {
public:
Row(uint64_t value = 0) : val(value) {}

@@ -89,7 +121,7 @@ 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)]; }
uint16_t get_ref(row_col_t rc) const { return ref.get(rc); }

uint8_t value(row_col_t rc) const {
if (!is_finished(rc)) return 0;

@@ -109,12 +141,10 @@ 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);
}
ref.remove(field);
ref.clear(value);

finished |= 1 << field;
ref[value] = 0;
}

void clear_row(uint8_t row, uint8_t value) {

@@ -122,7 +152,7 @@ class Subgrid {


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

@@ -133,30 +163,23 @@ class Subgrid {


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

using change_t = std::tuple<uint8_t, uint8_t>;
using changes_t = std::vector<change_t>;

changes_t check_lone() {
if (is_finished()) return {};

changes_t res;
changes_t res = ref.lone();

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)));
}

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;
}

@@ -209,7 +232,6 @@ class Subgrid {

static uint8_t count[512];
static uint64_t value[9];

std::memset(count, 0x00, sizeof(count));
for (uint8_t i = 0; i < 3; i++) {
for (uint8_t j = 0; j < 3; j++) {
const auto field = ::field({i, j});

@@ -230,28 +252,25 @@ class Subgrid {

// if current is not part of a tuple continue
if (popcnt <= 1 || popcnt != found) continue;

for (uint8_t k = 0; k < 3; k++) {
for (uint8_t l = 0; l < 3; l++) {
const row_col_t rc = {k, l};
const uint8_t nfield = ::field(rc);
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;
// 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]);
// 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;
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;
}
// remove cleared from reference
uint64_t tvalue = value[field];
while (tvalue) {
uint16_t idx = std::countr_zero(tvalue);
ref.remove(nfield, idx);
tvalue ^= 1ull << idx;
}
}
}

@@ -299,8 +318,7 @@ 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};
Ref ref;

uint16_t finished = 0;
uint64_t shot = 0;

@@ -310,8 +328,8 @@ class Grid {

public:
Grid(const std::string &s) {
int idx = 0;
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++, idx++) {
for (uint8_t i = 0; i < 9; i++) {
for (uint8_t j = 0; j < 9; j++, idx++) {
if (s[idx] == '0') continue;
set((i / 3) * 3 + j / 3, (i % 3) * 3 + j % 3, s[idx] - '1');
}

@@ -340,7 +358,7 @@ class Grid {

while (iter--) {
uint8_t changes = 0;

for (int i = 0; i < 9; i++) {
for (uint8_t i = 0; i < 9; i++) {
const auto lones = subgrids[i].check_lone();
for (const auto [field, val] : lones) {
set(i, field, val);

@@ -348,7 +366,7 @@ class Grid {

}
}

for (int i = 0; i < 9; i++) {
for (uint8_t i = 0; i < 9; i++) {
changes += subgrids[i].check_force();
}

@@ -375,7 +393,7 @@ class Grid {

if (changes) iter++;
}

for (int i = 0; i < 9; i++) {
for (uint8_t i = 0; i < 9; i++) {
if (!subgrids[i].is_finished()) return false;
}
return true;