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;    }}
Recursive backtracking Sudoku solver
c++;performance;algorithm;sudoku
Template argumentsSince 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 computationsInstead 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 9addressed above.