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 | 260874dfa278ba73acb805eaf53464771e84d6e5 |
| parent | 57ef6777cbec5c9f61b1fbe942e5732fb7aa68e7 |
| author | Dimitrije Dobrota <mail@dimitrijedobrota.com> |
| date | Tue, 2 Apr 2024 20:36:45 +0200 |
Add util functions and proper grid clearing on set
Diffstat:| M | main.cpp | | | ++++++++++++++++++++++++++++++++++++++++++++++++++++++---------------------------- |
1 files changed, 152 insertions(+), 78 deletions(-)
diff --git a/main.cpp b/main.cpp
@@ -1,107 +1,181 @@
#include <bit>
#include <bitset>
#include <cassert>
#include <cinttypes>
#include <format>
#include <iomanip>
#include <iostream>
static const std::int64_t mask_field = (1 << 9) - 1;
static constexpr const std::int64_t mask_field = (1 << 9) - 1;
static constexpr const std::int64_t mask_value = 0x201008040201;
using row_col_t = std::tuple<uint8_t, uint8_t>;
std::ostream &operator<<(std::ostream &os, row_col_t rc) {
return os << std::format("({}, {})", std::get<0>(rc), std::get<1>(rc));
}
row_col_t row_col(const uint8_t field) { return {field / 3, field % 3}; }
row_col_t row_col_rev(const uint8_t field) { return {2 - field % 3, field / 3}; }
row_col_t row_col(const row_col_t rcr) { return {std::get<1>(rcr), 2 - std::get<0>(rcr)}; }
row_col_t row_col_rev(const row_col_t rc) { return {2 - std::get<1>(rc), std::get<0>(rc)}; }
uint8_t field(const row_col_t rc) { return 3 * std::get<0>(rc) + std::get<1>(rc); }
class Row {
public:
Row(std::uint64_t value = 0) : val(value) {}
operator std::uint64_t() const { return val; }
std::uint64_t get(uint8_t field) const {
uint64_t shift = field * 9;
return (val >> shift) & mask_field;
}
void set(uint8_t field, uint8_t value) {
uint64_t shift = field * 9;
val &= ~(mask_field << shift);
val |= (1ull << value) << shift;
}
friend std::ostream &operator<<(std::ostream &os, const Row r) {
return os << std::setfill('0') << std::setw(14) << std::hex
<< (r.val & ((1ul << 54) - 1));
}
private:
std::uint64_t val;
public:
Row(uint64_t value = 0) : val(value) {}
operator uint64_t() const { return val; }
void set(uint8_t field, uint8_t value) {
clear(field);
toggle(field, value);
}
uint64_t get(uint8_t field) const { return (val >> 9 * field) & mask_field; }
uint64_t get(uint8_t field, uint8_t value) const { return (val >> 9 * field) & (1 << value); }
void toggle(uint8_t field) { val ^= mask_field << 9 * field; }
void clear(uint8_t field) { val &= ~(mask_field << 9 * field); }
void toggle(uint8_t field, uint8_t value) { val ^= 1ull << (9 * field + value); }
void clear(uint8_t field, uint8_t value) { val &= ~(1ull << (9 * field + value)); }
void toggle_all(uint8_t value) { val ^= mask_value << value; }
void clear_all(uint8_t value) { val &= ~(mask_value << value); }
friend std::ostream &operator<<(std::ostream &os, const Row r) {
return os << std::setfill('0') << std::setw(14) << std::hex << (r.val & ((1ul << 54) - 1));
}
private:
uint64_t val;
};
class Subgrid {
public:
Subgrid() {}
public:
Subgrid() {}
uint64_t get(row_col_t rc) const { return rows[std::get<0>(rc)].get(std::get<1>(rc)); }
uint64_t get_rev(row_col_t rc) const { return rows[std::get<0>(rc)].get(std::get<1>(rc) + 3); }
void set(uint8_t field, uint8_t value) {
assert(field < 9 && value < 9);
rows[0].clear_all(value);
rows[1].clear_all(value);
rows[2].clear_all(value);
std::uint64_t get(uint8_t field) const {
return rows[field / 3].get(field % 3);
}
set(row_col(field), value);
set_rev(row_col_rev(field), value);
}
void clear_row(uint8_t row, uint8_t value) {
assert(row < 3 && value < 9);
void set(uint8_t field, uint8_t value) {
rows[field / 3].set(field % 3, value);
rows[2 - field % 3].set(3 + field / 3, value);
}
for (int i = 0; i < 3; i++) {
clear({row, i}, value);
clear_rev(row_col_rev({row, i}), value);
}
}
friend std::ostream &operator<<(std::ostream &os, const Subgrid &b) {
void clear_col(uint8_t col, uint8_t value) {
assert(col < 3 && value < 9);
for (int i = 0; i < 3; i++) {
os << b.rows[i] << " ";
for (int i = 0; i < 3; i++) {
clear({i, col}, value);
clear_rev(row_col_rev({i, col}), value);
}
}
return os;
}
private:
Row rows[3] = {11111111, 22222222, 33333333};
friend std::ostream &operator<<(std::ostream &os, const Subgrid &b) {
for (int i = 0; i < 3; i++) {
os << b.rows[i] << " ";
}
return os;
}
private:
void set(row_col_t rc, uint8_t value) { rows[std::get<0>(rc)].set(std::get<1>(rc), value); }
void set_rev(row_col_t rc, uint8_t value) { rows[std::get<0>(rc)].set(std::get<1>(rc) + 3, value); }
void clear(row_col_t rc, uint8_t value) { rows[std::get<0>(rc)].clear(std::get<1>(rc), value); }
void clear_rev(row_col_t rc, uint8_t value) { rows[std::get<0>(rc)].clear(std::get<1>(rc) + 3, value); }
Row rows[3] = {~0, ~0, ~0};
};
class Grid {
public:
void set(uint8_t subgrid, uint8_t field, uint8_t value) {
subgrids[subgrid].set(field, value);
}
void print() const {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
std::bitset<9> value =
subgrids[(i / 3) * 3 + j / 3].get((i % 3) * 3 + j % 3);
std::cout << value << " ";
if (j % 3 == 2)
std::cout << " ";
}
std::cout << std::endl;
if (i % 3 == 2)
public:
void set(uint8_t subgrid, uint8_t field, uint8_t value) {
assert(subgrid < 9 && field < 9 && value < 9);
const auto [row, col] = row_col(subgrid);
const auto [frow, fcol] = row_col(field);
subgrids[3 * row + 0].clear_row(frow, value);
subgrids[3 * row + 1].clear_row(frow, value);
subgrids[3 * row + 2].clear_row(frow, value);
subgrids[col + 0].clear_col(fcol, value);
subgrids[col + 3].clear_col(fcol, value);
subgrids[col + 6].clear_col(fcol, value);
subgrids[subgrid].set(field, value);
}
void print() const {
std::cout << "Field: " << std::endl;
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
const row_col_t subgrid = {i / 3, j / 3};
const row_col_t field = {i % 3, j % 3};
std::bitset<9> value = subgrids[::field(subgrid)].get(field);
std::cout << value << " ";
if (j % 3 == 2) std::cout << " ";
}
std::cout << std::endl;
if (i % 3 == 2) std::cout << std::endl;
}
std::cout << std::endl;
std::cout << "Reversed Field: " << std::endl;
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
const row_col_t subgrid = {i / 3, j / 3};
const row_col_t rfield = row_col_rev({i % 3, j % 3});
std::bitset<9> value = subgrids[::field(subgrid)].get_rev(rfield);
std::cout << value << " ";
if (j % 3 == 2) std::cout << " ";
}
std::cout << std::endl;
if (i % 3 == 2) std::cout << std::endl;
}
}
}
friend std::ostream &operator<<(std::ostream &os, const Grid &g) {
for (int i = 0; i < 9; i++) {
std::cout << g.subgrids[i] << std::endl;
friend std::ostream &operator<<(std::ostream &os, const Grid &g) {
for (int i = 0; i < 9; i++) {
std::cout << g.subgrids[i] << std::endl;
}
return os;
}
return os;
}
private:
Subgrid subgrids[9];
private:
Subgrid subgrids[9];
};
int main(void) {
Grid g;
g.set(0, 0, 0);
g.set(0, 1, 1);
g.set(0, 2, 2);
g.set(0, 3, 3);
g.set(0, 4, 4);
g.set(0, 5, 5);
g.set(0, 6, 6);
g.set(0, 7, 7);
g.set(0, 8, 8);
std::cout << g << std::endl;
g.print();
return 0;
Grid g;
g.set(0, 0, 3);
g.set(4, 4, 4);
g.set(8, 8, 0);
std::cout << g << std::endl;
g.print();
return 0;
}