5
\$\begingroup\$

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";
    }
}
\$\endgroup\$

1 Answer 1

3
\$\begingroup\$
  • 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.

\$\endgroup\$
1
  • \$\begingroup\$ Good catch with num <= 9, Thanks for your review. \$\endgroup\$
    – Bizkit
    Jan 27, 2016 at 19:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.