doaskuHuman-like solver for sudoku |
| git clone git://git.dimitrijedobrota.com/doasku.git |
| Log | Files | Refs | README | LICENSE | HACKING | CONTRIBUTING | CODE_OF_CONDUCT | BUILDING | |
| commit | 4dca07e7bd573401ba1e1b818e3498419feaa754 |
| parent | 581e11fbb24974750e8491d22fc8ae8dc2585c5b |
| author | Dimitrije Dobrota <mail@dimitrijedobrota.com> |
| date | Mon, 8 Apr 2024 19:18:58 +0200 |
Improve consistency
Diffstat:| M | main.cpp | | | ++++++++++++++++++++++++++++++++++++++++++++-------------------------------------- |
1 files changed, 71 insertions(+), 61 deletions(-)
diff --git a/main.cpp b/main.cpp
@@ -19,9 +19,23 @@ struct row_col_t {
operator uint8_t() const { return 3 * row + col; }
row_col_t absolute(row_col_t rc) { return {uint8_t(row * 3 + rc.row), uint8_t(col * 3 + rc.col)}; }
row_col_t absolute(row_col_t rc) const { return {uint8_t(row * 3 + rc.row), uint8_t(col * 3 + rc.col)}; }
std::tuple<uint8_t, uint8_t> relative() { return {(row / 3) * 3 + col / 3, (row % 3) * 3 + col % 3}; }
std::tuple<uint8_t, uint8_t> relative() const {
return {(row / 3) * 3 + col / 3, (row % 3) * 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];
}
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];
}
friend std::ostream &operator<<(std::ostream &os, row_col_t rc) {
return os << std::format("({}, {})", rc.row, rc.col);
@@ -52,37 +66,41 @@ class Ref {
res[field] = value + 1;
}
auto get_pointing() const {
std::array<std::vector<std::tuple<uint8_t, uint8_t>>, 2> res;
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;
uint16_t row_mask = 0x7;
uint16_t col_mask = 0x49;
if ((seen_point_row & (1 << i)) == 0) {
for (uint8_t k = 0; k < 3; k++) {
if (std::popcount(uint16_t(row_mask & ref[i])) == popcnt) {
seen_point_row |= 1 << i;
res[0].emplace_back(k, i);
break;
}
row_mask <<= 3;
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;
}
}
}
if ((seen_point_col & (1 << i)) == 0) {
for (uint8_t k = 0; k < 3; k++) {
if (std::popcount(uint16_t(col_mask & ref[i])) == popcnt) {
seen_point_col |= 1 << i;
res[1].emplace_back(k, i);
break;
}
return res;
}
col_mask <<= 3;
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;
}
}
}
@@ -382,12 +400,17 @@ class Grid {
cols[ab.col].set(ab.row, value);
subgrids[subgrid].set(field, value);
// clear subgrid, row and col
for (uint8_t i = 0; i < 3; i++) {
_clear_row(subgrid, i, value);
_clear_row(3 * subgrid.row + i, field.row, value);
_clear_col(subgrid.col + 3 * i, field.col, 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 [c1, c2] = row_col_t::other_subgrid_col(subgrid);
_clear_col(c1, field.col, value);
_clear_col(c2, field.col, value);
}
bool solve() {
@@ -398,7 +421,6 @@ class Grid {
for (uint8_t subgrid = 0; subgrid < 9; subgrid++) {
const auto hs = subgrids[subgrid].get_hidden_singles();
for (const auto [field, val] : hs) {
std::cout << "hidden singles: " << (int)subgrid << " " << (int)field << " " << int(val)
<< std::endl;
@@ -435,7 +457,6 @@ class Grid {
const auto ns = subgrids[subgrid].get_naked_singles();
for (const auto [field, val] : ns) {
std::cout << "naked singles: " << (int)subgrid << " " << (int)field << " " << int(val)
<< std::endl;
@@ -482,29 +503,26 @@ class Grid {
changes++;
}
const auto pt = subgrids[subgrid].get_pointing();
for (const auto [row, val] : pt[0]) {
static uint8_t mapping[9][2] = {{1, 2}, {0, 2}, {0, 1}, {4, 5}, {3, 5},
{3, 4}, {7, 8}, {6, 8}, {6, 7}};
const auto ptr = subgrids[subgrid].get_pointing_row();
for (const auto [row, val] : ptr) {
std::cout << "pointing row: " << (int)subgrid << " " << (int)row << " " << (int)val
<< std::endl;
_clear_row(mapping[subgrid][0], row, val);
_clear_row(mapping[subgrid][1], row, val);
const auto [r1, r2] = row_col_t::other_subgrid_row(subgrid);
_clear_row(r1, row, val);
_clear_row(r2, row, val);
changes++;
}
for (const auto [col, val] : pt[1]) {
static uint8_t mapping[9][2] = {{3, 6}, {4, 7}, {5, 8}, {0, 6}, {1, 7},
{2, 8}, {0, 3}, {1, 4}, {2, 5}};
const auto ptc = subgrids[subgrid].get_pointing_col();
for (const auto [col, val] : ptc) {
std::cout << "pointing col: " << (int)subgrid << " " << (int)col << " " << (int)val
<< std::endl;
_clear_col(mapping[subgrid][0], col, val);
_clear_col(mapping[subgrid][1], col, val);
const auto [c1, c2] = row_col_t::other_subgrid_col(subgrid);
_clear_col(c1, col, val);
_clear_col(c2, col, val);
changes++;
}
@@ -513,44 +531,40 @@ class Grid {
for (uint8_t row = 0; row < 9; row++) {
const auto hs = rows[row].get_hidden_singles();
for (const auto [col, val] : hs) {
const auto [subgrid, field] = row_col_t(row, col).relative();
std::cout << "hidden singles row: " << (int)subgrid << " " << (int)field << " "
<< int(val) << std::endl;
std::cout << "hidden singles row: " << (int)row << " " << (int)col << " " << int(val)
<< std::endl;
const auto [subgrid, field] = row_col_t(row, col).relative();
set(subgrid, field, val);
changes++;
}
const auto hp = rows[row].get_hidden_pairs();
for (const auto [col, mask] : hp) {
const auto [subgrid, field] = row_col_t(row, col).relative();
std::cout << "hidden pairs row: " << (int)row << " " << (int)col << " "
<< std::bitset<9>(mask) << " " << std::endl;
const auto [subgrid, field] = row_col_t(row, col).relative();
_mask(subgrid, field, mask);
changes++;
}
const auto ht = rows[row].get_hidden_triplets();
for (const auto [col, mask] : ht) {
const auto [subgrid, field] = row_col_t(row, col).relative();
std::cout << "hidden triplets row: " << (int)row << " " << (int)col << " "
<< std::bitset<9>(mask) << " " << std::endl;
const auto [subgrid, field] = row_col_t(row, col).relative();
_mask(subgrid, field, mask);
changes++;
}
const auto hq = rows[row].get_hidden_quads();
for (const auto [col, mask] : hq) {
const auto [subgrid, field] = row_col_t(row, col).relative();
std::cout << "hidden quads row: " << (int)row << " " << (int)col << " "
<< std::bitset<9>(mask) << " " << std::endl;
const auto [subgrid, field] = row_col_t(row, col).relative();
_mask(subgrid, field, mask);
changes++;
}
@@ -601,44 +615,40 @@ class Grid {
for (uint8_t col = 0; col < 9; col++) {
const auto hs = cols[col].get_hidden_singles();
for (const auto [row, val] : hs) {
const auto [subgrid, field] = row_col_t(row, col).relative();
std::cout << "hidden singles col: " << (int)subgrid << " " << (int)field << " "
<< int(val) << std::endl;
std::cout << "hidden singles col: " << (int)row << " " << (int)col << " " << int(val)
<< std::endl;
const auto [subgrid, field] = row_col_t(row, col).relative();
set(subgrid, field, val);
changes++;
}
const auto hp = cols[col].get_hidden_pairs();
for (const auto [row, mask] : hp) {
const auto [subgrid, field] = row_col_t(row, col).relative();
std::cout << "hidden pairs col: " << (int)row << " " << (int)col << " "
<< std::bitset<9>(mask) << " " << std::endl;
const auto [subgrid, field] = row_col_t(row, col).relative();
_mask(subgrid, field, mask);
changes++;
}
const auto ht = cols[col].get_hidden_triplets();
for (const auto [row, mask] : ht) {
const auto [subgrid, field] = row_col_t(row, col).relative();
std::cout << "hidden triplets col: " << (int)row << " " << (int)col << " "
<< std::bitset<9>(mask) << " " << std::endl;
const auto [subgrid, field] = row_col_t(row, col).relative();
_mask(subgrid, field, mask);
changes++;
}
const auto hq = cols[col].get_hidden_quads();
for (const auto [row, mask] : hq) {
const auto [subgrid, field] = row_col_t(row, col).relative();
std::cout << "hidden quad col: " << (int)row << " " << (int)col << " "
<< std::bitset<9>(mask) << " " << std::endl;
const auto [subgrid, field] = row_col_t(row, col).relative();
_mask(subgrid, field, mask);
changes++;
}