I'm trying to learn more algorithmic techniques and I came across an interesting application of recursive backtracking: solving a Sudoku puzzle. I'm looking for a review concerning code style, quality, algorithmic correctness, and maybe tips on how to extend the algorithm/program.
#include <array>
#include <stdexcept>
#include <cctype>
#include <iostream>
#include <string>
template <size_t N = 9, class T = unsigned int>
class SudokuBoard {
private:
std::array<T, N * N> arr_;
static const T UNINITIALIZED = 0;
const T& at(size_t r, size_t c) const { return arr_[(r * N) + c]; }
T& at(size_t r, size_t c) { return arr_[(r * N) + c]; }
bool find_uninitialized_location(size_t &r, size_t &c) const
{
for (r = 0; r < N; ++r) {
for (c = 0; c < N; ++c) {
if (at(r, c) == UNINITIALIZED)
return true;
}
}
return false;
}
public:
SudokuBoard() { arr_.fill(UNINITIALIZED); }
SudokuBoard(const std::string &str)
{
for (size_t i = 0; i < N; ++i) {
for (size_t j = 0; j < N; ++j) {
const size_t index = (i * N) + j;
if (isdigit(str[index])) {
at(i, j) = str[index] - '0';
} else {
throw std::invalid_argument("Numbers range only from 0 - 9");
}
}
}
}
~SudokuBoard() = default;
SudokuBoard(const SudokuBoard &other) = default;
SudokuBoard& operator=(const SudokuBoard &other) = default;
T& operator()(size_t r, size_t c) { return at(r, c); }
const T& operator()(size_t r, size_t c) const { return at(r, c); }
bool solve()
{
size_t row = 0, col = 0;
if (!find_uninitialized_location(row, col)) {
return true;
}
for (size_t num = 1; num <= 9; ++num) {
if (is_safe(row, col, num)) {
at(row, col) = num;
if (solve()) {
return true;
}
at(row, col) = UNINITIALIZED;
}
}
return false;
}
bool used_in_row(size_t r, const T& val) const
{
for (size_t i = 0; i < N; ++i) {
if (at(r, i) == val) {
return true;
}
}
return false;
}
bool used_in_col(size_t c, const T& val) const
{
for (size_t i = 0; i < N; ++i) {
if (at(i, c) == val) {
return true;
}
}
return false;
}
bool used_in_box(size_t r, size_t c, const T& val) const
{
for (size_t i = 0; i < 3; ++i) {
for (size_t j = 0; j < 3; ++j) {
if (at(i + r, j + c) == val) {
return true;
}
}
}
return false;
}
bool is_safe(size_t r, size_t c, const T& val) const
{
return !used_in_row(r, val) &&
!used_in_col(c, val) &&
!used_in_box(r - (r % 3), c - (c % 3), val);
}
};
template<class T, size_t N>
std::ostream& operator<<(std::ostream &os, const SudokuBoard<N, T>& board)
{
for (size_t i = 0; i < N; ++i) {
for (size_t j = 0; j < N; ++j) {
os << board(i, j) << " ";
}
os << "\n";
}
os << "\n";
return os;
}
int main()
{
/* A value of zero means that the cell is empty
* The string represents a serialized matrix
* containing a valid sudoku board representation
*/
const std::string values = "306508400"\
"520000000"\
"087000031"\
"003010080"\
"900863005"\
"050090600"\
"130000250"\
"000000074"\
"005206300";
try {
SudokuBoard<> board(values);
std::cout << "The board: \n" << board;
if (board.solve()) {
std::cout << "The solved board: \n" << board;
} else {
std::cout << "The board has no solution!\n";
}
} catch (const std::invalid_argument &e) {
std::cerr << "Caught an invalid argument exception: " << e.what() << "\n";
} catch (...) {
std::cerr << "Unknown error caught.\n";
}
}