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 7610d22bd50aa367c3ce076b6e53671603b3b3fd
parent 36ea6d6c6b8f484e4b4c21bfcbeecbc821658fdb
author Dimitrije Dobrota < mail@dimitrijedobrota.com >
date Tue, 16 Apr 2024 18:22:20 +0200

General cleanup

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

1 files changed, 49 insertions(+), 84 deletions(-)

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

@@ -69,33 +69,10 @@ class Ref {

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

private:
auto get_pointing(uint16_t mask, uint16_t &seen) const {
changes_t res;

for (uint8_t i = 0; i < 9; i++) {
const uint8_t popcnt = std::popcount(ref[i]);
if (popcnt < 2 || popcnt > 3) continue;

if ((seen & (1 << i)) == 0) {
uint16_t cmask = mask;
for (uint8_t k = 0; k < 3; k++, cmask <<= 3) {
if (std::popcount(uint16_t(cmask & ref[i])) != popcnt) continue;
seen |= 1 << i;
res.emplace_back(k, i);
break;
}
}
}

return res;
}

public:
uint16_t get(uint8_t field) const { return value[field]; }
uint16_t get_ref(uint8_t value) const { return ref[value]; }

uint8_t get_value(uint8_t field) const { return res[field]; }
uint16_t get_value(uint8_t field) const { return res[field]; }

void clear(uint8_t field, uint8_t value) {
this->value[field] &= ~(1 << value);

@@ -111,10 +88,7 @@ class Ref {

res[field] = value + 1;
}

auto get_pointing_row() const { return get_pointing(0x7, seen_point_row); }
auto get_pointing_col() const { return get_pointing(0x49, seen_point_col); }

auto get_hidden_singles() const {
changes_t get_hidden_singles() const {
changes_t res;

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

@@ -125,7 +99,7 @@ class Ref {

return res;
}

auto get_naked_singles() const {
changes_t get_naked_singles() const {
changes_t res;

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

@@ -147,6 +121,9 @@ class Ref {

auto get_naked_triplets() const { return get_naked(3); }
auto get_naked_quads() const { return get_naked(4); }

auto get_pointing_row() const { return get_pointing(0x7, 0); }
auto get_pointing_col() const { return get_pointing(0x49, 1); }

private:
changes_t get_hidden(int number) const {
assert(number > 1 && number <= 4);

@@ -236,6 +213,27 @@ class Ref {

return true;
}

changes_t get_pointing(uint16_t mask, bool seen) const {
changes_t res;

for (uint8_t i = 0; i < 9; i++) {
const uint8_t popcnt = std::popcount(ref[i]);
if (popcnt < 2 || popcnt > 3) continue;

if ((seen_point[seen] & (1 << i)) == 0) {
uint16_t cmask = mask;
for (uint8_t k = 0; k < 3; k++, cmask <<= 3) {
if (std::popcount(uint16_t(cmask & ref[i])) != popcnt) continue;
seen_point[seen] |= 1 << i;
res.emplace_back(k, i);
break;
}
}
}

return res;
}

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

@@ -247,10 +245,7 @@ class Ref {


uint16_t res[9] = {0};

mutable uint16_t seen_hidden[4] = {0};
mutable uint16_t seen_naked[4] = {0};

mutable uint16_t seen_point_row = 0, seen_point_col = 0;
mutable uint16_t seen_hidden[4] = {0}, seen_naked[4] = {0}, seen_point[2] = {0};
};

class Grid {

@@ -372,64 +367,34 @@ class Grid {

}

void print() const {
// clang-format off
static const auto print_i = [this](const Ref refs[9], uint16_t (Ref::*f)(uint8_t) const, bool bits) {
for (uint8_t i = 0; i < 9; i++) {
for (uint8_t j = 0; j < 9; j++) {
const cord_t subgrid = {uint8_t(i / 3), uint8_t(j / 3)};
const cord_t field = {uint8_t(i % 3), uint8_t(j % 3)};

std::cout << "Field: " << std::endl;
for (uint8_t i = 0; i < 9; i++) {
for (uint8_t j = 0; j < 9; j++) {
const cord_t subgrid = {uint8_t(i / 3), uint8_t(j / 3)};
const cord_t field = {uint8_t(i % 3), uint8_t(j % 3)};
std::bitset<9> value = subgrids[subgrid].get(field);
std::cout << value << " ";
if (j % 3 == 2) std::cout << " ";
}
std::cout << std::endl;
if (i % 3 == 2) std::cout << std::endl;
}
uint16_t value = (refs[subgrid].*(f))((uint8_t)field);
if (bits) std::cout << std::bitset<9>(value) << " ";
else std::cout << value << " ";

std::cout << "Refs: " << std::endl;
for (uint8_t i = 0; i < 9; i++) {
for (uint8_t j = 0; j < 9; j++) {
const cord_t subgrid = {uint8_t(i / 3), uint8_t(j / 3)};
const cord_t field = {uint8_t(i % 3), uint8_t(j % 3)};
std::bitset<9> value = subgrids[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;
}
if (j % 3 == 2) std::cout << " ";
}

/*
std::cout << "Row Refs: " << std::endl;
for (uint8_t i = 0; i < 9; i++) {
for (uint8_t j = 0; j < 9; j++) {
std::cout << std::bitset<9>(rows[i].get_ref(j)) << " ";
std::cout << std::endl;
if (i % 3 == 2) std::cout << std::endl;
}
std::cout << std::endl;
if (i % 3 == 2) std::cout << std::endl;
}
};
// clang-format on

std::cout << "Col Refs: " << std::endl;
for (uint8_t i = 0; i < 9; i++) {
for (uint8_t j = 0; j < 9; j++) {
std::cout << std::bitset<9>(cols[i].get_ref(j)) << " ";
}
std::cout << std::endl;
if (i % 3 == 2) std::cout << std::endl;
}
*/
std::cout << "Field: " << std::endl;
print_i(subgrids, &Ref::get, true);

std::cout << "Refs: " << std::endl;
print_i(subgrids, &Ref::get_ref, true);

std::cout << "Board: " << std::endl;
for (uint8_t i = 0; i < 9; i++) {
for (uint8_t j = 0; j < 9; j++) {
const cord_t subgrid = {uint8_t(i / 3), uint8_t(j / 3)};
const cord_t field = {uint8_t(i % 3), uint8_t(j % 3)};
std::cout << (int)subgrids[subgrid].get_value(field) << " ";
if (j % 3 == 2) std::cout << " ";
}
std::cout << std::endl;
if (i % 3 == 2) std::cout << std::endl;
}
print_i(subgrids, &Ref::get_value, false);
}

private: