doasku

Human-like solver for sudoku

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

commit	f95e9990a789decde3e871a3b48461ce51a40493
parent	5c636d4f8cdc17acaf9b37f1c5a56668061f0c55
author	Dimitrije Dobrota <mail@dimitrijedobrota.com>
date	Thu, 11 Apr 2024 14:33:32 +0200

Better type safety with absolute coordinate type * rename row_col_t to cord_t * added acord_t

Diffstat:

main.cpp

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

1 files changed, 101 insertions(+), 101 deletions(-)

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

@@ -1,6 +1,7 @@

#include <array>

#include <bit>

#include <bitset>

#include <cassert>

#include <cinttypes>

#include <cstring>

#include <format>

@@ -8,43 +9,56 @@

#include <iostream>

#include <vector>

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

static constexpr const std::int64_t mask_value = 0x201008040201;

struct cord_t {

cord_t(uint8_t row, uint8_t col) : value(row * 3 + col) { assert(row < 3 && col < 3); }

cord_t(uint8_t value) : value(value) { assert(value < 9); }

class row_col_t;

explicit operator uint8_t() const { return value; }

struct row_col_t {

row_col_t(uint8_t row, uint8_t col) : row(row), col(col) {}

row_col_t(uint8_t field) : row(field / 3), col(field % 3) {}

uint8_t row() const { return value / 3; }

uint8_t col() const { return value % 3; }

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

friend std::ostream &operator<<(std::ostream &os, cord_t cord) {

return os << std::format("({}, {})", cord.row(), cord.col());

}

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

uint8_t value;

};

std::tuple<uint8_t, uint8_t> relative() const {

return {(row / 3) * 3 + col / 3, (row % 3) * 3 + col % 3};

}

class acord_t {

public:

acord_t(cord_t subgrid, cord_t field) : subgrid_i(subgrid), field_i(field) {}

acord_t(uint8_t row, uint8_t col) : subgrid_i(row / 3, col / 3), field_i(row % 3, col % 3) {}

static std::tuple<uint8_t, uint8_t> other_subgrid_row(uint8_t subgrid) {

static std::tuple<uint8_t, uint8_t> mapping[9] = {{1, 2}, {0, 2}, {0, 1}, {4, 5}, {3, 5},

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

return mapping[subgrid];

}

cord_t subgrid() const { return subgrid_i; }

cord_t field() const { return field_i; }

static std::tuple<uint8_t, uint8_t> other_subgrid_col(uint8_t subgrid) {

static std::tuple<uint8_t, uint8_t> mapping[9] = {{3, 6}, {4, 7}, {5, 8}, {0, 6}, {1, 7},

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

return mapping[subgrid];

}

uint8_t row() const { return subgrid_i.row() * 3 + field_i.row(); }

uint8_t col() const { return subgrid_i.col() * 3 + field_i.col(); }

std::tuple<cord_t, cord_t> relative() const { return {subgrid_i, field_i}; }

friend std::ostream &operator<<(std::ostream &os, row_col_t rc) {

return os << std::format("({}, {})", rc.row, rc.col);

friend std::ostream &operator<<(std::ostream &os, acord_t acord) {

return os << std::format("({}, {})", acord.row(), acord.col());

}

uint8_t row;

uint8_t col;

private:

cord_t subgrid_i;

cord_t field_i;

};

static std::tuple<uint8_t, uint8_t> other_subgrid_row(uint8_t subgrid) {

static std::tuple<uint8_t, uint8_t> mapping[9] = {{1, 2}, {0, 2}, {0, 1}, {4, 5}, {3, 5},

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

return mapping[subgrid];

}

static std::tuple<uint8_t, uint8_t> other_subgrid_col(uint8_t subgrid) {

static std::tuple<uint8_t, uint8_t> mapping[9] = {{3, 6}, {4, 7}, {5, 8}, {0, 6}, {1, 7},

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

return mapping[subgrid];

}

class Ref {

auto get_pointing(uint16_t mask, uint16_t &seen) const {

std::vector<std::tuple<uint8_t, uint8_t>> res;

@@ -337,6 +351,9 @@ class Ref {

}

private:

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

static constexpr const std::int64_t mask_value = 0x201008040201;

uint16_t value[9] = {mask_field, mask_field, mask_field, mask_field, mask_field,

mask_field, mask_field, mask_field, mask_field};

@@ -364,29 +381,27 @@ class Grid {

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

set({i, j}, s[idx] - '1');

}

void set(row_col_t subgrid, row_col_t field, uint8_t value) {

const auto ab = subgrid.absolute(field);

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

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

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

void set(acord_t ab, uint8_t value) {

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

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

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

_clear_row(subgrid, 0, value);

_clear_row(subgrid, 1, value);

_clear_row(subgrid, 2, value);

_clear_row(ab.subgrid(), 0, value);

_clear_row(ab.subgrid(), 1, value);

_clear_row(ab.subgrid(), 2, value);

const auto [r1, r2] = row_col_t::other_subgrid_row(subgrid);

_clear_row(r1, field.row, value);

_clear_row(r2, field.row, value);

const auto [r1, r2] = other_subgrid_row((uint8_t)ab.subgrid());

_clear_row(r1, ab.field().row(), value);

_clear_row(r2, ab.field().row(), value);

const auto [c1, c2] = row_col_t::other_subgrid_col(subgrid);

_clear_col(c1, field.col, value);

_clear_col(c2, field.col, value);

const auto [c1, c2] = other_subgrid_col((uint8_t)ab.subgrid());

_clear_col(c1, ab.field().col(), value);

_clear_col(c2, ab.field().col(), value);

}

bool solve() {

@@ -395,7 +410,7 @@ class Grid {

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

for (const auto [field, val] : subgrids[subgrid].get_naked_singles()) {

set(subgrid, field, val);

set({cord_t(subgrid), cord_t(field)}, val);

iter = true;

}

@@ -404,19 +419,17 @@ class Grid {

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

for (const auto [field, val] : subgrids[idx].get_hidden_singles()) {

set(idx, field, val);

set({cord_t(idx), cord_t(field)}, val);

iter = true;

}

for (const auto [col, val] : rows[idx].get_hidden_singles()) {

const auto [subgrid, field] = row_col_t(idx, col).relative();

set(subgrid, field, val);

set({idx, col}, val);

iter = true;

}

for (const auto [row, val] : cols[idx].get_hidden_singles()) {

const auto [subgrid, field] = row_col_t(row, idx).relative();

set(subgrid, field, val);

set({row, idx}, val);

iter = true;

}

@@ -425,7 +438,7 @@ class Grid {

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

const auto [r1, r2] = other_subgrid_row(subgrid);

_clear_row(r1, row, val);

_clear_row(r2, row, val);

@@ -433,7 +446,7 @@ class Grid {

}

for (const auto [col, val] : subgrids[subgrid].get_pointing_col()) {

const auto [c1, c2] = row_col_t::other_subgrid_col(subgrid);

const auto [c1, c2] = other_subgrid_col(subgrid);

_clear_col(c1, col, val);

_clear_col(c2, col, val);

@@ -445,19 +458,17 @@ class Grid {

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

for (const auto [field, mask] : subgrids[idx].get_hidden_pairs()) {

_mask(idx, field, mask);

_mask({cord_t(idx), cord_t(field)}, mask);

iter = true;

}

for (const auto [col, mask] : rows[idx].get_hidden_pairs()) {

const auto [subgrid, field] = row_col_t(idx, col).relative();

_mask(subgrid, field, mask);

_mask({idx, col}, mask);

iter = true;

}

for (const auto [row, mask] : cols[idx].get_hidden_pairs()) {

const auto [subgrid, field] = row_col_t(row, idx).relative();

_mask(subgrid, field, mask);

_mask({row, idx}, mask);

iter = true;

}

@@ -466,19 +477,17 @@ class Grid {

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

for (const auto [field, mask] : subgrids[idx].get_hidden_triplets()) {

_mask(idx, field, mask);

_mask({cord_t(idx), cord_t(field)}, mask);

iter = true;

}

for (const auto [col, mask] : rows[idx].get_hidden_triplets()) {

const auto [subgrid, field] = row_col_t(idx, col).relative();

_mask(subgrid, field, mask);

_mask({idx, col}, mask);

iter = true;

}

for (const auto [row, mask] : cols[idx].get_hidden_triplets()) {

const auto [subgrid, field] = row_col_t(row, idx).relative();

_mask(subgrid, field, mask);

_mask({row, idx}, mask);

iter = true;

}

@@ -487,19 +496,17 @@ class Grid {

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

for (const auto [field, mask] : subgrids[idx].get_hidden_quads()) {

_mask(idx, field, mask);

_mask({cord_t(idx), cord_t(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);

_mask({idx, col}, mask);

iter = true;

}

for (const auto [row, mask] : cols[idx].get_hidden_quads()) {

const auto [subgrid, field] = row_col_t(row, idx).relative();

_mask(subgrid, field, mask);

_mask({row, idx}, mask);

iter = true;

}

@@ -510,7 +517,7 @@ class Grid {

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

_clear({cord_t(idx), cord_t(field)}, val);

}

iter = true;

@@ -519,8 +526,7 @@ class Grid {

for (const auto [val, c1, c2] : rows[idx].get_naked_pairs()) {

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

if (col == c1 || col == c2) continue;

const auto [subgrid, field] = row_col_t(idx, col).relative();

_clear(subgrid, field, val);

_clear({idx, col}, val);

}

iter = true;

}

@@ -528,8 +534,7 @@ class Grid {

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

_clear({row, idx}, val);

}

iter = true;

}

@@ -541,7 +546,7 @@ class Grid {

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

_clear({cord_t(idx), cord_t(field)}, val);

}

iter = true;

@@ -550,8 +555,7 @@ class Grid {

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

_clear({idx, col}, val);

}

iter = true;

}

@@ -559,8 +563,7 @@ class Grid {

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 || row == r3) continue;

const auto [subgrid, field] = row_col_t(row, idx).relative();

_clear(subgrid, field, val);

_clear({row, idx}, val);

}

iter = true;

}

@@ -572,7 +575,7 @@ class Grid {

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

_clear({cord_t(idx), cord_t(field)}, val);

}

iter = true;

@@ -581,8 +584,7 @@ class Grid {

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

_clear({idx, col}, val);

}

iter = true;

}

@@ -590,8 +592,7 @@ class Grid {

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, idx).relative();

_clear(subgrid, field, val);

_clear({row, idx}, val);

}

iter = true;

}

@@ -601,7 +602,7 @@ class Grid {

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

const auto [r1, r2] = other_subgrid_row(idx);

_clear_row((r1 / 3) * 3 + index, r1 % 3, val);

_clear_row((r2 / 3) * 3 + index, r2 % 3, val);

@@ -609,7 +610,7 @@ class Grid {

}

for (const auto [index, val] : cols[idx].get_pointing_row()) {

const auto [c1, c2] = row_col_t::other_subgrid_row(idx);

const auto [c1, c2] = other_subgrid_row(idx);

_clear_col(index * 3 + c1 / 3, c1 % 3, val);

_clear_col(index * 3 + c2 / 3, c2 % 3, val);

@@ -626,9 +627,9 @@ class Grid {

std::cout << "Field: " << std::endl;

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

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[subgrid].get(field);

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[(uint8_t)subgrid].get((uint8_t)field);

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

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

}

@@ -639,9 +640,9 @@ class Grid {

std::cout << "Refs: " << std::endl;

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

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[subgrid].get_ref(field);

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[(uint8_t)subgrid].get_ref((uint8_t)field);

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

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

}

@@ -672,9 +673,9 @@ class Grid {

std::cout << "Board: " << std::endl;

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

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[subgrid].get_value(field) << " ";

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[(uint8_t)subgrid].get_value((uint8_t)field) << " ";

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

}

std::cout << std::endl;

@@ -683,31 +684,30 @@ class Grid {

}

private:

void _mask(row_col_t sg, row_col_t field, uint16_t mask) {

void _mask(acord_t ab, uint16_t mask) {

while (mask) {

const uint8_t idx = std::countr_zero(mask);

_clear(sg, field, idx);

_clear(ab, idx);

mask ^= 1ull << idx;

}

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

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

void _clear(acord_t ab, uint8_t value) {

subgrids[(uint8_t)ab.subgrid()].clear((uint8_t)ab.field(), value);

row_col_t ab = sg.absolute(field);

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

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

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

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

}

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

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

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

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

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

}

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

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

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

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

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

}