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 |
commit9bc87891964a37a0dfc09358e27a3d2f4ce111a1
parent3754de91370eff1f2b330dc9ea2eb2e63f95dd6d
authorDimitrije Dobrota <mail@dimitrijedobrota.com>
dateFri, 14 Jun 2024 22:25:42 +0200

Proper CMake project

Diffstat:
A.gitignore|++
ACMakeLists.txt|++++++++++++++++++++
Ainclude/cord.hpp|+++++++++++++++++++++++++++++++++++++++++++++
Ainclude/grid.hpp|++++++++++++++++++++++++++++++++++++++++++++
Ainclude/ref.hpp|+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Dmain.cpp|---------------------------------------------------------------------------------
Asrc/CMakeLists.txt|++++++++
Asrc/grid.cpp|+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Asrc/main.cpp|+++++++++++++++
Asrc/ref.cpp|+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

10 files changed, 593 insertions(+), 508 deletions(-)

diff --git a/.gitignore b/.gitignore

@@ -0,0 +1,2 @@

build
.cache

diff --git a/CMakeLists.txt b/CMakeLists.txt

@@ -0,0 +1,20 @@

cmake_minimum_required(VERSION 3.25.2)
set(CMAKE_EXPORT_COMPILE_COMMANDS ON)
project(
doasku
VERSION 0.0.1
DESCRIPTION "Sudoku madness"
HOMEPAGE_URL https://git.dimitrijedobrota.com/doasku.git
LANGUAGES CXX
)
set(CMAKE_CXX_STANDARD 20)
set(CMAKE_CXX_STANDARD_REQUIRED ON)
set(CMAKE_CXX_EXTENSIONS OFF)
if(NOT CMAKE_BUILD_TYPE)
set(CMAKE_BUILD_TYPE Release CACHE STRING "Build type" FORCE)
endif()
add_subdirectory(src)

diff --git a/include/cord.hpp b/include/cord.hpp

@@ -0,0 +1,45 @@

#ifndef DOASKO_CORD_HPP
#define DOASKO_CORD_HPP
#include <cassert>
#include <cinttypes>
#include <utility>
struct cord_t {
cord_t(uint8_t value) : value(value) { assert(value < 9); }
cord_t(uint8_t row, uint8_t col) : value(row * 3 + col) {
assert(row < 3 && col < 3);
}
operator uint8_t() const { return value; }
uint8_t row() const { return value / 3; }
uint8_t col() const { return value % 3; }
uint8_t value;
};
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) {}
cord_t subgrid() const { return subgrid_i; }
cord_t field() const { return field_i; }
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};
}
private:
cord_t subgrid_i;
cord_t field_i;
};
#endif

diff --git a/include/grid.hpp b/include/grid.hpp

@@ -0,0 +1,44 @@

#ifndef DOASKU_GRID_HPP
#define DOASKU_GRID_HPP
#include <string>
#include <utility>
#include "cord.hpp"
#include "ref.hpp"
class Grid {
public:
Grid(const std::string &s);
bool solve();
void print() const;
private:
using operation_t = std::tuple<acord_t, uint16_t>;
void op_set(operation_t op);
void op_mask(operation_t op);
void op_clear(operation_t op);
void op_clear_row(operation_t op);
void op_clear_col(operation_t op);
void op_clear_row_rel(operation_t op);
void op_clear_col_rel(operation_t op);
void _set(acord_t ab, uint8_t value);
void _mask(acord_t ab, uint16_t mask);
void _clear(acord_t ab, uint8_t value);
void _clear_row(cord_t sg, uint8_t row, uint8_t value);
void _clear_col(cord_t sg, uint8_t col, uint8_t value);
bool _is_finished(uint8_t subgrid);
bool _is_finished();
Ref subgrids[9], rows[9], cols[9];
bool changed = false;
};
#endif

diff --git a/include/ref.hpp b/include/ref.hpp

@@ -0,0 +1,63 @@

#ifndef DOASKU_REF_HPP
#define DOASKU_REF_HPP
#include <cstdint>
#include <utility>
#include <vector>
class Ref {
public:
using change_t = std::tuple<uint8_t, uint16_t>;
using changes_t = std::vector<change_t>;
uint16_t get(uint8_t field) const { return value[field]; }
uint16_t get_ref(uint8_t value) const { return ref[value]; }
uint16_t get_value(uint8_t field) const { return res[field]; }
void clear(uint8_t field, uint8_t value);
void set(uint8_t field, uint8_t value);
changes_t get_hidden_singles() const;
changes_t get_naked_singles() const;
auto get_hidden_pairs() const { return get_hidden(2); }
auto get_hidden_triplets() const { return get_hidden(3); }
auto get_hidden_quads() const { return get_hidden(4); }
auto get_naked_pairs() const { return get_naked(2); }
auto get_naked_triplets() const { return get_naked(3); }
auto get_naked_quads() const { return get_naked(4); }
auto get_pointing_row() const { return get_pointing(0x7, 0); }
auto get_pointing_col() const { return get_pointing(0x49, 1); }
private:
changes_t get_naked(int number) const;
changes_t get_hidden(int number) const;
changes_t get_pointing(uint16_t mask, bool seen) const;
bool get_hidden(changes_t &res, uint8_t og, uint8_t number, uint8_t first,
uint16_t val, uint16_t mask) const;
bool get_naked(changes_t &res, uint8_t og, uint8_t number, uint8_t first,
uint16_t val) const;
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};
uint16_t ref[9] = {mask_field, mask_field, mask_field,
mask_field, mask_field, mask_field,
mask_field, mask_field, mask_field};
uint16_t res[9] = {0};
mutable uint16_t seen_hidden[4] = {0};
mutable uint16_t seen_naked[4] = {0};
mutable uint16_t seen_point[2] = {0};
};
#endif

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

@@ -1,508 +0,0 @@

#include <algorithm>
#include <array>
#include <bit>
#include <bitset>
#include <cassert>
#include <cinttypes>
#include <cstring>
#include <format>
#include <iomanip>
#include <iostream>
#include <vector>
template <class Input, class UnaryFunc>
UnaryFunc for_each(Input input, UnaryFunc f) {
return std::for_each(begin(input), end(input), f);
}
struct cord_t {
cord_t(uint8_t value) : value(value) { assert(value < 9); }
cord_t(uint8_t row, uint8_t col) : value(row * 3 + col) {
assert(row < 3 && col < 3);
}
operator uint8_t() const { return value; }
uint8_t row() const { return value / 3; }
uint8_t col() const { return value % 3; }
friend std::ostream &operator<<(std::ostream &os, cord_t cord) {
return os << std::format("({}, {})", cord.row(), cord.col());
}
uint8_t value;
};
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) {}
cord_t subgrid() const { return subgrid_i; }
cord_t field() const { return field_i; }
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, acord_t acord) {
return os << std::format("(({}, {}))", acord.row(), acord.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 {
public:
using change_t = std::tuple<uint8_t, uint16_t>;
using changes_t = std::vector<change_t>;
public:
uint16_t get(uint8_t field) const { return value[field]; }
uint16_t get_ref(uint8_t value) const { return ref[value]; }
uint16_t get_value(uint8_t field) const { return res[field]; }
void clear(uint8_t field, uint8_t value) {
this->value[field] &= ~(1 << value);
ref[value] &= ~(1 << field);
}
void set(uint8_t field, uint8_t value) {
for (uint8_t i = 0; i < 9; i++) {
ref[i] &= ~(1 << field);
}
this->value[field] = ref[value] = 0;
res[field] = value + 1;
}
changes_t get_hidden_singles() const {
changes_t res;
for (uint8_t candidate = 0; candidate < 9; candidate++) {
if (std::popcount(ref[candidate]) != 1) continue;
res.emplace_back(std::countr_zero(ref[candidate]), candidate);
}
return res;
}
changes_t get_naked_singles() const {
changes_t res;
for (uint8_t i = 0; i < 9; i++) {
const auto values = get(i);
if (std::popcount(values) != 1) continue;
const auto value = std::countr_zero(values);
if (!ref[value]) continue;
res.emplace_back(i, value);
}
return res;
}
auto get_hidden_pairs() const { return get_hidden(2); }
auto get_hidden_triplets() const { return get_hidden(3); }
auto get_hidden_quads() const { return get_hidden(4); }
auto get_naked_pairs() const { return get_naked(2); }
auto get_naked_triplets() const { return get_naked(3); }
auto get_naked_quads() const { return get_naked(4); }
auto get_pointing_row() const { return get_pointing(0x7, 0); }
auto get_pointing_col() const { return get_pointing(0x49, 1); }
private:
changes_t get_hidden(int number) const {
assert(number > 1 && number <= 4);
changes_t res;
get_hidden(res, number, number, 0, 0, 0);
return res;
}
bool get_hidden(changes_t &res, uint8_t og, uint8_t number, uint8_t first,
uint16_t val, uint16_t mask) const {
if (number != 0) {
for (uint8_t i = first; i < 9; i++) {
if (std::popcount(ref[i]) < 2) continue;
if (seen_hidden[og] & (1ul << i)) continue;
bool used = get_hidden(res, og, number - 1, i + 1,
val | ref[i], mask | (1 << i));
if (!used) continue;
seen_hidden[og] |= 1ul << i;
if (number != og) return true;
}
return false;
}
if (std::popcount(val) != og) return false;
static uint8_t fields[9];
uint8_t size = 0;
while (val) {
const uint8_t idx = std::countr_zero(val);
fields[size++] = idx;
val ^= 1ull << idx;
}
for (uint8_t i = 0; i < og; i++) {
const uint16_t change =
value[fields[i]] & ~(value[fields[i]] & mask);
if (!change) continue;
res.emplace_back(fields[i], change);
}
return true;
}
changes_t get_naked(int number) const {
assert(number > 1 && number <= 4);
changes_t res;
get_naked(res, number, number, 0, 0);
return res;
}
bool get_naked(changes_t &res, uint8_t og, uint8_t number, uint8_t first,
uint16_t val) const {
static uint8_t seen[4] = {0};
if (number != 0) {
for (uint8_t i = first; i < 9; i++) {
if (this->res[i]) continue;
if (number == og && seen_naked[og] & (1ul << i)) continue;
seen[og - number] = i;
bool used =
get_naked(res, og, number - 1, i + 1, val | value[i]);
if (!used) continue;
if (number == og) seen_naked[og] |= 1ul << i;
if (number != og) return true;
}
return false;
}
if (std::popcount(val) != og) return false;
while (val) {
const uint8_t idx = std::countr_zero(val);
for (uint8_t pos = 0, i; pos < 9; pos++) {
if ((value[pos] & idx) == 0) continue;
for (i = 0; i < og; i++) {
if (pos == seen[i]) break;
}
if (i == og) res.emplace_back(pos, idx);
}
val ^= 1ull << idx;
}
return true;
}
changes_t get_pointing(uint16_t mask, bool seen) const {
changes_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[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_point[seen] |= 1 << i;
res.emplace_back(k, i);
break;
}
}
}
return res;
}
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};
uint16_t ref[9] = {mask_field, mask_field, mask_field,
mask_field, mask_field, mask_field,
mask_field, mask_field, mask_field};
uint16_t res[9] = {0};
mutable uint16_t seen_hidden[4] = {0};
mutable uint16_t seen_naked[4] = {0};
mutable uint16_t seen_point[2] = {0};
};
class Grid {
public:
Grid(const std::string &s) {
int idx = 0;
for (uint8_t i = 0; i < 9; i++) {
for (uint8_t j = 0; j < 9; j++, idx++) {
if (s[idx] == '0') continue;
_set({i, j}, s[idx] - '1');
}
}
}
bool solve() {
// clang-format off
static const auto sub_op =
[this](void (Grid::*op)(operation_t), Ref::changes_t (Ref::*f)() const) {
for(uint8_t subgrid = 0; subgrid < 9; subgrid++) {
for_each((subgrids[subgrid].*(f))(), [this, subgrid, op](const Ref::change_t ch) {
(this->*(op))(operation_t({cord_t(subgrid), cord_t(std::get<0>(ch))}, std::get<1>(ch)));
});
}
return changed;
};
static const auto row_op =
[this](void (Grid::*op)(operation_t), Ref::changes_t (Ref::*f)() const) {
for(uint8_t row = 0; row < 9; row++) {
for_each((rows[row].*(f))(), [this, row, op](const Ref::change_t ch) {
(this->*(op))(operation_t({row, std::get<0>(ch)}, std::get<1>(ch)));
});
}
return changed;
};
static const auto col_op =
[this](void (Grid::*op)(operation_t), Ref::changes_t (Ref::*f)() const) {
for(uint8_t col = 0; col < 9; col++) {
for_each((cols[col].*(f))(), [this, col, op](const Ref::change_t ch) {
(this->*(op))(operation_t({std::get<0>(ch), col}, std::get<1>(ch)));
});
}
return changed;
};
static const auto all_op =
[this](void (Grid::*op)(operation_t), Ref::changes_t (Ref::*f)() const) {
sub_op(op, f), row_op(op, f), col_op(op, f);
return changed;
};
// clang-format on
changed = true;
while (changed) {
changed = false;
if (sub_op(&Grid::op_set, &Ref::get_naked_singles)) continue;
if (all_op(&Grid::op_set, &Ref::get_hidden_singles)) continue;
if (sub_op(&Grid::op_clear_row, &Ref::get_pointing_row)) continue;
if (sub_op(&Grid::op_clear_col, &Ref::get_pointing_col)) continue;
if (all_op(&Grid::op_mask, &Ref::get_hidden_pairs)) continue;
if (all_op(&Grid::op_mask, &Ref::get_hidden_triplets)) continue;
if (all_op(&Grid::op_mask, &Ref::get_hidden_quads)) continue;
if (all_op(&Grid::op_clear, &Ref::get_naked_pairs)) continue;
if (all_op(&Grid::op_clear, &Ref::get_naked_triplets)) continue;
if (all_op(&Grid::op_clear, &Ref::get_naked_quads)) continue;
row_op(&Grid::op_clear_row_rel, &Ref::get_pointing_row);
col_op(&Grid::op_clear_col_rel, &Ref::get_pointing_row);
}
return _is_finished();
}
void print() const {
// clang-format off
static const auto print_i = [this](const Ref refs[9], uint16_t (Ref::*f)(uint8_t) const, bool bits) {
for (uint8_t i = 0; i < 9; i++) {
for (uint8_t j = 0; j < 9; j++) {
const cord_t subgrid = {uint8_t(i / 3), uint8_t(j / 3)};
const cord_t field = {uint8_t(i % 3), uint8_t(j % 3)};
uint16_t value = (refs[subgrid].*(f))((uint8_t)field);
if (bits) std::cout << std::bitset<9>(value) << " ";
else std::cout << value << " ";
if (j % 3 == 2) std::cout << " ";
}
std::cout << std::endl;
if (i % 3 == 2) std::cout << std::endl;
}
};
// clang-format on
std::cout << "Field: " << std::endl;
print_i(subgrids, &Ref::get, true);
std::cout << "Refs: " << std::endl;
print_i(subgrids, &Ref::get_ref, true);
std::cout << "Board: " << std::endl;
print_i(subgrids, &Ref::get_value, false);
}
private:
using operation_t = std::tuple<acord_t, uint16_t>;
void op_set(operation_t op) {
_set(std::get<0>(op), std::get<1>(op));
changed = true;
}
void op_mask(operation_t op) {
_mask(std::get<0>(op), std::get<1>(op));
changed = true;
}
void op_clear(operation_t op) {
_clear(std::get<0>(op), std::get<1>(op));
changed = true;
}
void op_clear_row(operation_t op) {
const auto [ab, val] = op;
const auto [r1, r2] = other_subgrid_row(ab.subgrid());
_clear_row(r1, ab.field(), val);
_clear_row(r2, ab.field(), val);
changed = true;
}
void op_clear_col(operation_t op) {
const auto [ab, val] = op;
const auto [c1, c2] = other_subgrid_col(ab.subgrid());
_clear_col(c1, ab.field(), val);
_clear_col(c2, ab.field(), val);
changed = true;
}
void op_clear_row_rel(operation_t op) {
const auto [ab, val] = op;
const auto [r1, r2] = other_subgrid_row(ab.row());
_clear_row((r1 / 3) * 3 + ab.col(), r1 % 3, val);
_clear_row((r2 / 3) * 3 + ab.col(), r2 % 3, val);
changed = true;
}
void op_clear_col_rel(operation_t op) {
const auto [ab, val] = op;
const auto [c1, c2] = other_subgrid_row(ab.col());
_clear_col(ab.row() * 3 + c1 / 3, c1 % 3, val);
_clear_col(ab.row() * 3 + c2 / 3, c2 % 3, val);
changed = true;
}
void _set(acord_t ab, uint8_t value) {
rows[ab.row()].set(ab.col(), value);
cols[ab.col()].set(ab.row(), value);
subgrids[ab.subgrid()].set(ab.field(), value);
_clear_row(ab.subgrid(), 0, value);
_clear_row(ab.subgrid(), 1, value);
_clear_row(ab.subgrid(), 2, value);
const auto [r1, r2] = other_subgrid_row(ab.subgrid());
_clear_row(r1, ab.field().row(), value);
_clear_row(r2, ab.field().row(), value);
const auto [c1, c2] = other_subgrid_col(ab.subgrid());
_clear_col(c1, ab.field().col(), value);
_clear_col(c2, ab.field().col(), value);
}
void _mask(acord_t ab, uint16_t mask) {
while (mask) {
const uint8_t idx = std::countr_zero(mask);
_clear(ab, idx);
mask ^= 1ull << idx;
}
}
void _clear(acord_t ab, uint8_t value) {
subgrids[ab.subgrid()].clear(ab.field(), value);
rows[ab.row()].clear(ab.col(), value);
cols[ab.col()].clear(ab.row(), 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);
}
}
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);
}
}
bool _is_finished(uint8_t subgrid) {
for (uint8_t i = 0; i < 9; i++) {
if (!subgrids[subgrid].get_value(i)) return false;
}
return true;
}
bool _is_finished() {
for (uint8_t i = 0; i < 9; i++) {
if (!_is_finished(i)) return false;
}
return true;
}
Ref subgrids[9], rows[9], cols[9];
bool changed = false;
};
int main(const int argc, const char *argv[]) {
for (int i = 1; i < argc; i++) {
Grid g(argv[i]);
g.print();
std::cout << (g.solve() ? "solved" : "unable to solve") << std::endl;
g.print();
}
return 0;
}

diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt

@@ -0,0 +1,8 @@

add_executable(doasku main.cpp ref.cpp grid.cpp)
target_include_directories(doasku PRIVATE ../include)
set_target_properties(doasku PROPERTIES
VERSION ${PROJECT_VERSION}
SOVERSION ${PROJECT_VERSION_MAJOR}
RUNTIME_OUTPUT_DIRECTORY "${CMAKE_BINARY_DIR}/bin"
)

diff --git a/src/grid.cpp b/src/grid.cpp

@@ -0,0 +1,240 @@

#include <algorithm>
#include <bitset>
#include <iostream>
#include "grid.hpp"
template <class Input, class UnaryFunc>
UnaryFunc for_each(Input input, UnaryFunc f) {
return std::for_each(begin(input), end(input), f);
}
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];
}
Grid::Grid(const std::string &s) {
int idx = 0;
for (uint8_t i = 0; i < 9; i++) {
for (uint8_t j = 0; j < 9; j++, idx++) {
if (s[idx] == '0') continue;
_set({i, j}, s[idx] - '1');
}
}
}
bool Grid::solve() {
// clang-format off
static const auto sub_op =
[this](void (Grid::*op)(operation_t), Ref::changes_t (Ref::*f)() const) {
for(uint8_t subgrid = 0; subgrid < 9; subgrid++) {
for_each((subgrids[subgrid].*(f))(), [this, subgrid, op](const Ref::change_t ch) {
(this->*(op))(operation_t({cord_t(subgrid), cord_t(std::get<0>(ch))}, std::get<1>(ch)));
});
}
return changed;
};
static const auto row_op =
[this](void (Grid::*op)(operation_t), Ref::changes_t (Ref::*f)() const) {
for(uint8_t row = 0; row < 9; row++) {
for_each((rows[row].*(f))(), [this, row, op](const Ref::change_t ch) {
(this->*(op))(operation_t({row, std::get<0>(ch)}, std::get<1>(ch)));
});
}
return changed;
};
static const auto col_op =
[this](void (Grid::*op)(operation_t), Ref::changes_t (Ref::*f)() const) {
for(uint8_t col = 0; col < 9; col++) {
for_each((cols[col].*(f))(), [this, col, op](const Ref::change_t ch) {
(this->*(op))(operation_t({std::get<0>(ch), col}, std::get<1>(ch)));
});
}
return changed;
};
static const auto all_op =
[this](void (Grid::*op)(operation_t), Ref::changes_t (Ref::*f)() const) {
sub_op(op, f), row_op(op, f), col_op(op, f);
return changed;
};
// clang-format on
changed = true;
while (changed) {
changed = false;
if (sub_op(&Grid::op_set, &Ref::get_naked_singles)) continue;
if (all_op(&Grid::op_set, &Ref::get_hidden_singles)) continue;
if (sub_op(&Grid::op_clear_row, &Ref::get_pointing_row)) continue;
if (sub_op(&Grid::op_clear_col, &Ref::get_pointing_col)) continue;
if (all_op(&Grid::op_mask, &Ref::get_hidden_pairs)) continue;
if (all_op(&Grid::op_mask, &Ref::get_hidden_triplets)) continue;
if (all_op(&Grid::op_mask, &Ref::get_hidden_quads)) continue;
if (all_op(&Grid::op_clear, &Ref::get_naked_pairs)) continue;
if (all_op(&Grid::op_clear, &Ref::get_naked_triplets)) continue;
if (all_op(&Grid::op_clear, &Ref::get_naked_quads)) continue;
row_op(&Grid::op_clear_row_rel, &Ref::get_pointing_row);
col_op(&Grid::op_clear_col_rel, &Ref::get_pointing_row);
}
return _is_finished();
}
void Grid::print() const {
// clang-format off
static const auto print_i = [this](const Ref refs[9], uint16_t (Ref::*f)(uint8_t) const, bool bits) {
for (uint8_t i = 0; i < 9; i++) {
for (uint8_t j = 0; j < 9; j++) {
const cord_t subgrid = {uint8_t(i / 3), uint8_t(j / 3)};
const cord_t field = {uint8_t(i % 3), uint8_t(j % 3)};
uint16_t value = (refs[subgrid].*(f))((uint8_t)field);
if (bits) std::cout << std::bitset<9>(value) << " ";
else std::cout << value << " ";
if (j % 3 == 2) std::cout << " ";
}
std::cout << std::endl;
if (i % 3 == 2) std::cout << std::endl;
}
};
// clang-format on
std::cout << "Field: " << std::endl;
print_i(subgrids, &Ref::get, true);
std::cout << "Refs: " << std::endl;
print_i(subgrids, &Ref::get_ref, true);
std::cout << "Board: " << std::endl;
print_i(subgrids, &Ref::get_value, false);
}
void Grid::op_set(operation_t op) {
_set(std::get<0>(op), std::get<1>(op));
changed = true;
}
void Grid::op_mask(operation_t op) {
_mask(std::get<0>(op), std::get<1>(op));
changed = true;
}
void Grid::op_clear(operation_t op) {
_clear(std::get<0>(op), std::get<1>(op));
changed = true;
}
void Grid::op_clear_row(operation_t op) {
const auto [ab, val] = op;
const auto [r1, r2] = other_subgrid_row(ab.subgrid());
_clear_row(r1, ab.field(), val);
_clear_row(r2, ab.field(), val);
changed = true;
}
void Grid::op_clear_col(operation_t op) {
const auto [ab, val] = op;
const auto [c1, c2] = other_subgrid_col(ab.subgrid());
_clear_col(c1, ab.field(), val);
_clear_col(c2, ab.field(), val);
changed = true;
}
void Grid::op_clear_row_rel(operation_t op) {
const auto [ab, val] = op;
const auto [r1, r2] = other_subgrid_row(ab.row());
_clear_row((r1 / 3) * 3 + ab.col(), r1 % 3, val);
_clear_row((r2 / 3) * 3 + ab.col(), r2 % 3, val);
changed = true;
}
void Grid::op_clear_col_rel(operation_t op) {
const auto [ab, val] = op;
const auto [c1, c2] = other_subgrid_row(ab.col());
_clear_col(ab.row() * 3 + c1 / 3, c1 % 3, val);
_clear_col(ab.row() * 3 + c2 / 3, c2 % 3, val);
changed = true;
}
void Grid::_set(acord_t ab, uint8_t value) {
rows[ab.row()].set(ab.col(), value);
cols[ab.col()].set(ab.row(), value);
subgrids[ab.subgrid()].set(ab.field(), value);
_clear_row(ab.subgrid(), 0, value);
_clear_row(ab.subgrid(), 1, value);
_clear_row(ab.subgrid(), 2, value);
const auto [r1, r2] = other_subgrid_row(ab.subgrid());
_clear_row(r1, ab.field().row(), value);
_clear_row(r2, ab.field().row(), value);
const auto [c1, c2] = other_subgrid_col(ab.subgrid());
_clear_col(c1, ab.field().col(), value);
_clear_col(c2, ab.field().col(), value);
}
void Grid::_mask(acord_t ab, uint16_t mask) {
while (mask) {
const uint8_t idx = std::countr_zero(mask);
_clear(ab, idx);
mask ^= 1ull << idx;
}
}
void Grid::_clear(acord_t ab, uint8_t value) {
subgrids[ab.subgrid()].clear(ab.field(), value);
rows[ab.row()].clear(ab.col(), value);
cols[ab.col()].clear(ab.row(), value);
}
void Grid::_clear_row(cord_t sg, uint8_t row, uint8_t value) {
for (uint8_t i = 0; i < 3; i++) {
_clear({sg, {row, i}}, value);
}
}
void Grid::_clear_col(cord_t sg, uint8_t col, uint8_t value) {
for (uint8_t i = 0; i < 3; i++) {
_clear({sg, {i, col}}, value);
}
}
bool Grid::_is_finished(uint8_t subgrid) {
for (uint8_t i = 0; i < 9; i++) {
if (!subgrids[subgrid].get_value(i)) return false;
}
return true;
}
bool Grid::_is_finished() {
for (uint8_t i = 0; i < 9; i++) {
if (!_is_finished(i)) return false;
}
return true;
}

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

@@ -0,0 +1,15 @@

#include <iostream>
#include "grid.hpp"
int main(const int argc, const char *argv[]) {
for (int i = 1; i < argc; i++) {
Grid g(argv[i]);
g.print();
std::cout << (g.solve() ? "solved" : "unable to solve") << std::endl;
g.print();
}
return 0;
}

diff --git a/src/ref.cpp b/src/ref.cpp

@@ -0,0 +1,156 @@

#include <cassert>
#include "ref.hpp"
void Ref::clear(uint8_t field, uint8_t value) {
this->value[field] &= ~(1 << value);
ref[value] &= ~(1 << field);
}
void Ref::set(uint8_t field, uint8_t value) {
for (uint8_t i = 0; i < 9; i++) {
ref[i] &= ~(1 << field);
}
this->value[field] = ref[value] = 0;
res[field] = value + 1;
}
Ref::changes_t Ref::get_hidden_singles() const {
changes_t res;
for (uint8_t candidate = 0; candidate < 9; candidate++) {
if (std::popcount(ref[candidate]) != 1) continue;
res.emplace_back(std::countr_zero(ref[candidate]), candidate);
}
return res;
}
Ref::changes_t Ref::get_naked_singles() const {
changes_t res;
for (uint8_t i = 0; i < 9; i++) {
const auto values = get(i);
if (std::popcount(values) != 1) continue;
const auto value = std::countr_zero(values);
if (!ref[value]) continue;
res.emplace_back(i, value);
}
return res;
}
Ref::changes_t Ref::get_hidden(int number) const {
assert(number > 1 && number <= 4);
changes_t res;
get_hidden(res, number, number, 0, 0, 0);
return res;
}
bool Ref::get_hidden(changes_t &res, uint8_t og, uint8_t number, uint8_t first,
uint16_t val, uint16_t mask) const {
if (number != 0) {
for (uint8_t i = first; i < 9; i++) {
if (std::popcount(ref[i]) < 2) continue;
if (seen_hidden[og] & (1ul << i)) continue;
bool used = get_hidden(res, og, number - 1, i + 1, val | ref[i],
mask | (1 << i));
if (!used) continue;
seen_hidden[og] |= 1ul << i;
if (number != og) return true;
}
return false;
}
if (std::popcount(val) != og) return false;
static uint8_t fields[9];
uint8_t size = 0;
while (val) {
const uint8_t idx = std::countr_zero(val);
fields[size++] = idx;
val ^= 1ull << idx;
}
for (uint8_t i = 0; i < og; i++) {
const uint16_t change = value[fields[i]] & ~(value[fields[i]] & mask);
if (!change) continue;
res.emplace_back(fields[i], change);
}
return true;
}
Ref::changes_t Ref::get_naked(int number) const {
assert(number > 1 && number <= 4);
changes_t res;
get_naked(res, number, number, 0, 0);
return res;
}
bool Ref::get_naked(changes_t &res, uint8_t og, uint8_t number, uint8_t first,
uint16_t val) const {
static uint8_t seen[4] = {0};
if (number != 0) {
for (uint8_t i = first; i < 9; i++) {
if (this->res[i]) continue;
if (number == og && seen_naked[og] & (1ul << i)) continue;
seen[og - number] = i;
bool used = get_naked(res, og, number - 1, i + 1, val | value[i]);
if (!used) continue;
if (number == og) seen_naked[og] |= 1ul << i;
if (number != og) return true;
}
return false;
}
if (std::popcount(val) != og) return false;
while (val) {
const uint8_t idx = std::countr_zero(val);
for (uint8_t pos = 0, i; pos < 9; pos++) {
if ((value[pos] & idx) == 0) continue;
for (i = 0; i < og; i++) {
if (pos == seen[i]) break;
}
if (i == og) res.emplace_back(pos, idx);
}
val ^= 1ull << idx;
}
return true;
}
Ref::changes_t Ref::get_pointing(uint16_t mask, bool seen) const {
changes_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[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_point[seen] |= 1 << i;
res.emplace_back(k, i);
break;
}
}
}
return res;
}