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 |
commitaded653ae1e36bb63d3d9663569a5b84e930a3df
parent373064734d5b09ee3e8181d04f6a92396fb20a65
authorDimitrije Dobrota <mail@dimitrijedobrota.com>
dateTue, 9 Apr 2024 21:45:18 +0200

Cleanup code with helper functions

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

1 files changed, 57 insertions(+), 79 deletions(-)

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

@@ -46,6 +46,47 @@ struct row_col_t {

};
class Ref {
auto get_pointing(uint16_t mask, uint16_t &seen) const {
std::vector<std::tuple<uint8_t, uint8_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;
}
void get_indices(uint8_t indices[9], uint16_t mask) const {
uint8_t size = 0;
while (mask) {
const uint8_t idx = std::countr_zero(mask);
indices[size++] = idx;
mask ^= 1ull << idx;
}
}
using hidden_t = std::tuple<uint8_t, uint16_t>;
using hiddens_t = std::vector<hidden_t>;
void get_hidden_changes(uint8_t fields[9], uint16_t mask, uint8_t n, hiddens_t &vec) const {
for (uint8_t i = 0; i < n; i++) {
const uint16_t change = value[fields[i]] & ~(value[fields[i]] & mask);
if (!change) continue;
vec.emplace_back(fields[i], change);
}
}
public:
uint16_t get(uint8_t field) const { return value[field]; }
uint16_t get_ref(uint8_t value) const { return ref[value]; }

@@ -67,45 +108,13 @@ class Ref {

}
auto get_pointing_row() const {
std::vector<std::tuple<uint8_t, uint8_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_row & (1 << i)) == 0) {
uint16_t row_mask = 0x7;
for (uint8_t k = 0; k < 3; k++, row_mask <<= 3) {
if (std::popcount(uint16_t(row_mask & ref[i])) != popcnt) continue;
seen_point_row |= 1 << i;
res.emplace_back(k, i);
break;
}
}
}
return res;
static const uint16_t row_mask = 0x7;
return get_pointing(row_mask, seen_point_row);
}
auto get_pointing_col() const {
std::vector<std::tuple<uint8_t, uint8_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_col & (1 << i)) == 0) {
uint16_t col_mask = 0x49;
for (uint8_t k = 0; k < 3; k++, col_mask <<= 3) {
if (std::popcount(uint16_t(col_mask & ref[i])) != popcnt) continue;
seen_point_col |= 1 << i;
res.emplace_back(k, i);
break;
}
}
}
return res;
static const uint16_t col_mask = 0x49;
return get_pointing(col_mask, seen_point_col);
}
auto get_hidden_singles() const {

@@ -120,7 +129,7 @@ class Ref {

}
auto get_hidden_pairs() const {
std::vector<std::tuple<uint8_t, uint16_t>> res;
hiddens_t res;
for (uint8_t i = 0; i < 9; i++) {
if (std::popcount(ref[i]) != 2) continue;

@@ -133,21 +142,10 @@ class Ref {

seen_hidden_pair |= 1ul << j;
static uint8_t fields[9];
uint8_t size = 0;
uint16_t tval = ref[i];
while (tval) {
const uint8_t idx = std::countr_zero(tval);
fields[size++] = idx;
tval ^= 1ull << idx;
}
get_indices(fields, ref[i]);
uint16_t mask = (1 << i) | (1 << j);
for (uint8_t i = 0; i < 2; i++) {
const uint16_t change = value[fields[i]] & ~(value[fields[i]] & mask);
if (!change) continue;
res.emplace_back(fields[i], change);
}
const uint16_t mask = (1 << i) | (1 << j);
get_hidden_changes(fields, mask, 2, res);
}
}

@@ -155,7 +153,7 @@ class Ref {

}
auto get_hidden_triplets() const {
std::vector<std::tuple<uint8_t, uint16_t>> res;
hiddens_t res;
for (uint8_t i = 0; i < 9; i++) {
if (std::popcount(ref[i]) < 2) continue;

@@ -169,7 +167,7 @@ class Ref {

if (std::popcount(ref[k]) < 2) continue;
if (seen_hidden_triplet & (1ul << k)) continue;
uint16_t val = ref[i] | ref[j] | ref[k];
const uint16_t val = ref[i] | ref[j] | ref[k];
if (std::popcount(val) != 3) continue;
seen_hidden_triplet |= 1ul << i;

@@ -177,21 +175,10 @@ class Ref {

seen_hidden_triplet |= 1ul << k;
static uint8_t fields[9];
uint8_t size = 0;
uint16_t tval = val;
while (tval) {
const uint8_t idx = std::countr_zero(tval);
fields[size++] = idx;
tval ^= 1ull << idx;
}
get_indices(fields, val);
uint16_t mask = (1 << i) | (1 << j) | (1 << k);
for (uint8_t i = 0; i < 3; i++) {
const uint16_t change = value[fields[i]] & ~(value[fields[i]] & mask);
if (!change) continue;
res.emplace_back(fields[i], change);
}
get_hidden_changes(fields, mask, 3, res);
}
}
}

@@ -227,21 +214,10 @@ class Ref {

seen_hidden_quads |= 1ul << l;
static uint8_t fields[9];
uint8_t size = 0;
uint16_t tval = val;
while (tval) {
const uint8_t idx = std::countr_zero(tval);
fields[size++] = idx;
tval ^= 1ull << idx;
}
get_indices(fields, val);
uint16_t mask = (1 << i) | (1 << j) | (1 << k) | (1 << l);
for (uint8_t i = 0; i < 4; i++) {
const uint16_t change = value[fields[i]] & ~(value[fields[i]] & mask);
if (!change) continue;
res.emplace_back(fields[i], change);
}
get_hidden_changes(fields, mask, 4, res);
}
}
}

@@ -323,6 +299,7 @@ class Ref {

auto get_naked_quads() const {
std::vector<std::tuple<uint8_t, uint8_t, uint8_t, uint8_t, uint8_t>> res;
for (uint8_t i = 0; i < 9; i++) {
if (this->res[i]) continue;
if (seen_naked_quad & (1ul << i)) continue;

@@ -362,6 +339,7 @@ class Ref {

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