# Recursive backtracking Sudoku solver

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";
}
}

• Template arguments

• Since the row, column and a block must accommodate the same set of numbers, N is necessarily a square number. I recommend to template the board on the modulus M, deduce N as M^2, and use M everywhere you use 3.

• Templating on T looks a bit strange. At least I don't see what advantage it may serve.

• Unnecessary computations

Instead of recomputing uninitialized locations at each call to solve I recommend to compute the vector of such locations once, and pass it around by reference, removing and restoring locations, along the lines of

bool solve(std::vector<std::pair<int, int>>& uninitialized)
{
if (uninitialized.size() == 0)
return true;

auto row = uninitialized.back.first;
auto col = uninitialized.back.second;
uninitialized.pop_back();

for (size_t num = 1; num <= N; ++num) {
if (is_safe(row, col, num)) {
at(row, col) = num;

if (solve(uninitialized)) {
return true;
}
}
}

at(row, col) = UNINITIALIZED;
uninitialized.push_back(std::make_pair(row, col));
return false;
}

Please notice that you shall iterate until num <= N, not 9.

• Magic numbers 3 and 9