Recursive backtracking Sudoku solver

Question

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

Answer 1

• 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

  addressed above.