doasku

Human-like solver for sudoku

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

commit	55d045aeca3466f352cab5b9c6059c698dfba614
parent	87ada69fe7c5f08b472fee90c45e0e5d17354f08
author	Dimitrije Dobrota <mail@dimitrijedobrota.com>
date	Wed, 3 Apr 2024 17:13:54 +0200

Add checking forced within a subgrid

Diffstat:

main.cpp

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

1 files changed, 167 insertions(+), 6 deletions(-)

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

@@ -1,10 +1,13 @@

#include <array>

#include <bit>

#include <bitset>

#include <cassert>

#include <cinttypes>

#include <cstring>

#include <format>

#include <iomanip>

#include <iostream>

#include <vector>

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

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

@@ -66,6 +69,15 @@ 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, uint64_t mask) { val &= ~(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)) << " ";

}

return os;

}

private:

uint64_t val;

};

@@ -83,6 +95,7 @@ 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);

@@ -117,17 +130,112 @@ class Subgrid {

}

void check_lone() {

bool res = false;

for (int field = 0, mask = 1; field < 9; field++, mask++) {

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;

for (int field = 0, mask = 1; field < 9; field++, mask <<= 1) {

if (finished & mask) continue;

if (std::popcount(get(field)) != 1) continue;

set(field, std::countr_zero(get(field)));

res = true;

res.emplace_back(field, std::countr_zero(get(field)));

}

return res;

}

std::array<changes_t, 2> check_ray() {

if (is_finished()) return {};

Row o012 = rows[0] | rows[1] | rows[2];

uint64_t mask = {

// clang-format off

(o012.get(1) | o012.get(2)) << 0 |

(o012.get(0) | o012.get(2)) << 9 |

(o012.get(0) | o012.get(1)) << 18 |

(o012.get(4) | o012.get(5)) << 27 |

(o012.get(3) | o012.get(5)) << 36 |

(o012.get(3) | o012.get(4)) << 45

// clang-format on

};

Row potent = (rows[0] & rows[1]) | (rows[0] & rows[2]) | (rows[1] & rows[2]);

Row shooting = potent & ~mask & ~shot;

shot |= shooting;

std::array<changes_t, 2> res;

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

uint64_t val = shooting.get(i);

while (val) {

uint8_t idx = std::countr_zero(val);

res[0].emplace_back(i, idx);

val ^= 1ull << idx;

}

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

uint64_t val = shooting.get(i + 3);

while (val) {

uint8_t idx = std::countr_zero(val);

res[1].emplace_back(i, idx);

val ^= 1ull << idx;

}

return res;

}

void check_ray() {}

bool check_force() {

if (is_finished()) return false;

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

value[field] = rows[i].get(j);

count[value[field]]++;

}

bool res = false;

for (int field = 0; field < 9; field++) {

const uint8_t popcnt = std::popcount(value[field]);

const uint8_t found = count[value[field]];

// no need to check any more times

count[value[field]] = 0;

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

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

}

return res;

}

private:

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

@@ -136,8 +244,13 @@ 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};

uint16_t finished = 0;

uint64_t shot = 0;

};

class Grid {

@@ -169,6 +282,52 @@ class Grid {

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

}

bool solve() {

int iter = 1;

while (iter--) {

uint8_t changes = 0;

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

const auto lones = subgrids[i].check_lone();

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

set(i, field, val);

changes++;

}

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

changes += subgrids[i].check_force();

}

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

const auto rays = subgrids[i].check_ray();

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

changes++;

}

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

changes++;

}

if (changes) iter++;

}

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

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

}

return true;

}

void print() const {

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

@@ -207,6 +366,8 @@ int main(const int argc, const char *argv[]) {

Grid g(argv[i]);

g.print();

std::cout << (g.solve() ? "solved" : "unable to solve") << std::endl;

g.print();

}

return 0;