Fast and flexible Sudoku Solver in C++

Question

After seeing a lot of Sudoku solvers on Code Review I decided to implement my own.

My implementation aims to be very fast and flexible, supporting some Sudoku variations (irregular boxes, extra unique areas...)

I structured the code in three main classes, that are:

• Cell
• SudokuBoard
• SudokuSolver

There is also a struct, uniqueContainers; it inherits from std::vector<uniqueContainer>. uniqueContainer is just a typedef for std::vector<short>; it holds a collection of areas that must not contain any duplicates (rows, columns, boxes...). It also possess a type index, to distinguish between other uniqueContainers (rows-columns, boxes-columns...)

Cell is an object representing a single cell in the board; it holds a vector containing the possible candidates for the cell, and if after removing a candidate only one remains it falls back to a short variable for the number.

It has some helper functions, mostly getters and setters, and one to remove a candidate.

SudokuBoard represents the actual board, inheriting privately from std::vector<Cell>, it has some static members, that are the side of the board, a vector of uniqueContainers (so rows, columns...) , and the indices that map the cell to the appropriate container.

This indices are stored in a vector, that has size \$ Cells \cdot nUniqueContainers \$; for example, in a classic \$ 9 \times 9 \$ sudoku, the only uniqueContainers would be rows, columns and boxes, so the size of indices would be \$ 81 \cdot 3 \$. E.g. The cell 18, will have indices 2, 0 and 0, because it belongs to the third row, the first column and the first box.

There are two static methods, one to initialize the unique containers, and the other to add unique containers (not rows, columns or boxes, which are added by default).

SudokuSolver contains the algorithm to solve the Sudoku; it is a bruteforce algorithm, but it recurses only on the cell with the least number of candidates, and before doing this it eliminates all the illegal candidates from the board.

When a solution is found, the solver stores it in a vector, and if it has not been specified to find only one solution, it keeps searching.

While solving it also keep track of the total recursion steps.

In the main there are eleven test Sudokus, some classic \$ 9 \times 9 \$, an empty \$ 4 \times 4 \$ and some variations (HyperSudoku, Nonomino and Sudoku X).

For most of them it takes, on my computer, from 30 microsec for the easiest to 500 microsec for the hardest ones.

testSudoku4 is the exception, topping out with 5 ms required to solve it.

What I am most interested in is to make it even faster and, if possible, more elegant.

Here the source code:

main.cpp

#include <algorithm>
#include <array>
#include <chrono>
#include <iostream>
#include <numeric>
#include <string>
#include <string_view>
#include <vector>

#include "SudokuSolver.h"

int main()
{
    std::string testSudoku1 =
    {
        "080090030030000069902063158020804590851907046394605870563040987200000015010050020" //MEDIUM SUDOKU
    };
    std::string testSudoku2 =
    {
        "001700806070000215000020000307040008000080000800060709000010000298000060706005300" //EASY SUDOKU
    };
    std::string testSudoku3 =
    {
        "075001002000000009090027040000094300000000000003810000030760010900000000600400580" //MEDIUM SUDOKU
    };
    std::string testSudoku4 =
    {
        "506000700010300000700050800000000020000070608000102040800090006030004000065000000" //EXTREME
    };
    std::string testSudoku5 =
    {
        "900784500700000930000001000080000006079030480300000070000200000065000004007468003" //EXTREME
    };
    std::string testSudoku6 =
    {
        "907000003000807000005003700040902050090060080010408020004200800000306000300000206" //EXTREME
    };
    std::string testSudoku7 =
    {
        "927000003000807000005003700040902050090060080010408020004200800000306000300000206" //INVALID BOARD
    };
    std::string testSudoku8 = 
    {
        "0000000000000000"        //4x4 EMPTY SUDOKU
    };

    std::string testSudoku9 =
    {
        "000000010002000034000051000000006500070300080003000000000080000580000900690000000"        //HYPERSUDOKU SUDOKU
    };
    std::vector<std::vector<short>> areasHyper(4, std::vector<short>(9));  //HYPERSUDOKU AREAS
    areasHyper[0] = { 10, 11, 12, 19, 20, 21, 28, 29, 30 };
    areasHyper[1] = { 14, 15, 16, 23, 24, 25, 32, 33, 34 };
    areasHyper[2] = { 46, 47, 48, 55, 56, 57, 64, 65, 66 };
    areasHyper[3] = { 50, 51, 52, 59, 60, 61, 68, 69, 70 };

    std::string testSudoku10 =
    {
        "300000004002060100010908020005000600020000010009000800080304060004010900500000007"        //NONOMINO SUDOKU
    };
    std::vector<std::vector<short>> areasN(9, std::vector<short>(9));  //NONOMINO AREAS, DISABLE BOXES WHEN SOLVING
    areasN[0] = { 0, 1, 2, 9, 10, 11, 18, 27, 28 };
    areasN[1] = { 3, 12, 13, 14, 23, 24, 25, 34, 35 };
    areasN[2] = { 4, 5, 6, 7, 8, 15, 16, 17, 26 };
    areasN[3] = { 19, 20, 21, 22, 29, 36, 37, 38, 39 };
    areasN[4] = { 30, 31, 32, 33, 40,  47, 48, 49, 50 };
    areasN[5] = { 41, 42, 43, 44, 51, 58, 59, 60, 61 };
    areasN[6] = { 45, 46, 55, 56, 57, 66, 67, 68, 77 };
    areasN[7] = { 54, 63, 64, 65, 72, 73, 74, 75, 76 };
    areasN[8] = { 52, 53, 62, 69, 70, 71, 78, 79, 80 };

    std::string testSudoku11 =
    {
        "400805200000000000080070000000208907000000004105300000000000010000000000001007006"        //X SUDOKU
    };

    std::vector<std::vector<short>> areasX(2, std::vector<short>(9)); //X AREAS

    areasX[0] = { 0, 10, 20, 30, 40, 50, 60, 70, 80 };
    areasX[1] = { 8, 16, 24, 32, 40, 48, 56, 64, 72 };

    /*std::string sudoku; //TO GET A SUDOKU FROM INPUT

    std::cout << "For empty cells type 0, without spaces" << std::endl;
    std::cout << "Input row 1 : ";
    std::cin >> sudoku;

    int nRows = sudoku.length();

    for (int i = 1; i < nRows; i++)
    {
        std::string row;

        std::cout << "Input row " << i + 1 << " : ";
        std::cin >> row;
        sudoku += row;
    }

    SudokuSolver solver(sudoku); */

    SudokuSolver solver(testSudoku4);  //SOLVE A TEST SUDOKU

    int status = solver.solve();
    if (status == 1)
    {
        std::cout << "SOLVED" << std::endl;
    }
    else if (status == 0)
    {
        std::cout << "ERROR ON THE BOARD" << std::endl;
    }

    std::cout << std::endl << solver << std::endl;

    /*int nSolves = 1000;  BENCHMARKING CODE

    auto t0 = std::chrono::high_resolution_clock::now();

    for (int i = 0; i < nSolves; i++)
    {
        solver.solve();
    }

    auto t1 = std::chrono::high_resolution_clock::now();

    auto time = std::chrono::duration_cast<std::chrono::microseconds>(t1 - t0).count();

    std::cout << "Solving took " << time << " microsecs" << std::endl;
    std::cout << "Average solving time : " << (time) / nSolves << " microsecs" << std::endl;*/

    return 0;
}

Cell.h

enum class SudokuProgress : short
{
    PROGRESS,
    NO_PROGRESS,
    CONFLICT
};


class Cell
{
private:
    std::vector<short> candidates;

    short num;
public:
    Cell(short maxCand) : candidates(maxCand), num(0)
    {
        std::iota(candidates.begin(), candidates.end(), 1); 
    }

    Cell(short n, short maxCand) : num(n) {}

    const auto& getCandidates() const //CALL ONLY IF NOT SOLVED
    {
        return candidates;
    }

    void resetCands()
    {
        candidates.clear();
    }

    void setNum(int n)
    {
        num = n;
    }

    short getNum() const
    {
        return num;
    }

    short candidatesCount() const //CALL ONLY IF NOT SOLVED
    {
        return candidates.size();
    }

    bool empty() const
    {
        return num == -1;
    }

    SudokuProgress removeCandidate(short n)
    {
        if (!solved())
        {
            if (auto it = std::find(candidates.begin(), candidates.end(), n); it != candidates.end())
            {
                std::iter_swap(it, candidates.end() - 1);
                candidates.pop_back();

                if (candidates.size() == 1)
                {
                    num = candidates[0];
                }

                return SudokuProgress::PROGRESS;
            }
        }
        else if (num == n)
        {
            num = -1;
            return SudokuProgress::CONFLICT;
        }

        return SudokuProgress::NO_PROGRESS;
    }

    bool solved() const
    {
        return num > 0;
    }

    friend std::ostream& operator<<(std::ostream& os, const Cell& cell)
    {
        os << cell.getNum();
        return os;
    }
};

SudokuBoard.h

#include "Cell.h"

typedef std::vector<Cell>::iterator cellIt;
typedef short cellIndex;

typedef short ContID;
typedef std::vector<short> uniqueContainer;

struct uniqueContainers : std::vector<uniqueContainer>
{
    const ContID id;

    uniqueContainers(const int& nConts, const int& contSize, const ContID& i) : std::vector<uniqueContainer>(nConts, uniqueContainer(contSize)), id(i) {}

    uniqueContainers(const int& nConts, const int& contSize) : uniqueContainers(nConts, contSize, -1) {}
};

class SudokuBoard : std::vector<Cell>
{
private:
    static std::vector<uniqueContainers> uniqueConts; //UNIQUE CONTAINERS(ROWS; COLUMNS AND BOXES)
    static short side;

    static std::vector<short> contIndices;

    short solvedCells;

    static void initUniqueConts(bool box = true)  //INITIALIZES DEFAULT UNIQUE CONTAINERS
    {
        uniqueConts.clear();

        uniqueConts.emplace_back(side, side, 0); //ROWS
        uniqueConts.emplace_back(side, side, 1); //COLUMNS
        if (box)
        {
            uniqueConts.emplace_back(side, side, 2); //BOXES
        }

        uniqueContainers& rows = uniqueConts[0];
        uniqueContainers& columns = uniqueConts[1];

        for (int i = 0; i < side; i++)
        {
            for (int j = 0; j < side; j++)
            {
                rows[i][j] = side * i + j;
                columns[j][i] = side * i + j;
            }
        }

        if (box)
        {
            uniqueContainers& boxes = uniqueConts[2];
            int boxSize = sqrt(side);

            for (int i = 0; i < side; i++)
            {
                for (int j = 0; j < boxSize; j++)
                {
                    const uniqueContainer& row = rows[(i / boxSize) * boxSize + j];

                    int rowOffset = i % boxSize * boxSize;

                    std::copy(row.begin() + rowOffset, row.begin() + (rowOffset + boxSize), boxes[i].begin() + j * boxSize);
                }
            }
        }
    }

    static void addUniqueConts(const uniqueContainers& unique)
    {
        uniqueConts.emplace_back(unique.size(), unique[0].size(), uniqueConts.back().id + 1);

        std::copy(unique.begin(), unique.end(), uniqueConts.back().begin());
    }
public:
    SudokuBoard() {}

    SudokuBoard(const SudokuBoard& other)
    {
        solvedCells = other.solvedCells;
        this->reserve(side*side);

        for (auto& cell : other)
        {
            if (cell.solved())
            {
                this->emplace_back(cell.getNum(), side);
            }
            else
            {
                this->push_back(cell);
            }
        }
    }

    SudokuBoard(SudokuBoard&& other) : std::vector<Cell>(std::move(other)), solvedCells(other.solvedCells) {}

    void initCells(std::string_view boardStr) //CALL ONLY AFTER INITIALIZING UNIQUE CONTAINERS
    {
        side = sqrt(boardStr.length());
        contIndices.resize(boardStr.length()*uniqueConts.size());

        std::fill(contIndices.begin(), contIndices.end(), -1);

        for (int i = 0; i < boardStr.length(); i++)
        {
            short n = boardStr[i] - '0';

            for (const uniqueContainers& uniqueCont : uniqueConts)
            {
                for (int j = 0; j < uniqueCont.size(); j++)
                {
                    if (std::find(uniqueCont[j].begin(), uniqueCont[j].end(), i) != uniqueCont[j].end())
                    {
                        contIndices[i + uniqueCont.id * boardStr.length()] = j;
                        break;
                    }
                }
            }

            if (n == 0)
            {
                this->emplace_back(side);
            }
            else
            {
                this->emplace_back(n, side);
                solvedCells++;
            }
        }
    }

    short& getContIndex(const cellIndex& cellIndex, const ContID& uniqueContIndex) const
    {
        return contIndices[cellIndex + uniqueContIndex * this->size()];
    }

    bool solved() const
    {
        return solvedCells == this->size();
    }

    friend std::ostream& operator<<(std::ostream& os, const SudokuBoard& board)
    {
        for (int i = 0; i < side; i++)
        {
            for (int j = 0; j < side; j++)
            {
                if (board[j + board.side * i].solved())
                {
                    os << board[j + side * i];
                }
                else
                {
                    os << '0';
                }

                os << " ";
            }

            if (i < side - 1)
                os << std::endl;
        }

        return os;
    }

    friend class SudokuSolver;
};


std::vector<short> SudokuBoard::contIndices;
std::vector<uniqueContainers> SudokuBoard::uniqueConts;
short SudokuBoard::side;

SudokuSolver.h

#include "SudokuBoard.h"

class SudokuSolver
{
private:
    SudokuBoard startBoard;

    int totalBoards;
    bool uniqueSol;

    std::vector<SudokuBoard> solutions;

    SudokuProgress removeCandidate(SudokuBoard& board, const int &eraser, const uniqueContainer& cont, std::vector<cellIndex>& nextCheck) //ERASER MUST BE A SOLVED CELL
    {
        SudokuProgress status = SudokuProgress::NO_PROGRESS;

        for (const cellIndex& cell : cont)
        {
            if (cell != eraser)
            {
                SudokuProgress progress = board[cell].removeCandidate(board[eraser].getNum());

                if (progress == SudokuProgress::PROGRESS) //removeCandidate(int) INSIDE CELL; NOT RECURSIVE
                {
                    if (board[cell].solved()) //CHECK FOR SOLVED CELLS
                    {
                        nextCheck.push_back(cell);
                        board.solvedCells++;

                        status = SudokuProgress::PROGRESS;
                    }
                }
                else if (progress == SudokuProgress::CONFLICT) //INVALID BOARD
                {
                    return SudokuProgress::CONFLICT;
                }
            }
        }

        return status;
    }

    SudokuProgress removeConflicts(SudokuBoard& board, std::vector<cellIndex>& toCheck) //REMOVE ILLEGAL CANDIDATES FROM CELLS
    {
        SudokuProgress status = SudokuProgress::NO_PROGRESS;

        std::vector<cellIndex> check(std::move(toCheck));
        toCheck.reserve(check.size());

        for (const uniqueContainers& uniqueConts : board.uniqueConts)
        {
            for (const cellIndex& cell : check)
            {
                int contIndex = board.getContIndex(cell, uniqueConts.id);

                if (contIndex != -1)
                {
                    SudokuProgress solvedCount = removeCandidate(board, cell, uniqueConts[contIndex], toCheck);

                    if (solvedCount == SudokuProgress::PROGRESS)
                    {
                        status = SudokuProgress::PROGRESS;
                    }
                    else if (solvedCount == SudokuProgress::CONFLICT)
                        return SudokuProgress::CONFLICT;
                }
            }
        }

        return status;
    }

    bool solve(SudokuBoard board, std::vector<cellIndex> toCheck)
    {
        bool solved = false;

        while (true)
        {
            SudokuProgress status = SudokuProgress::NO_PROGRESS;

            do
            {

                status = removeConflicts(board, toCheck);

            } while (status == SudokuProgress::PROGRESS);

            if (status == SudokuProgress::CONFLICT)
            {
                break;
            }

            if (board.solved())
            {
                solutions.emplace_back(std::move(board));

                return true;
            }
            else
            {
                cellIt leastCands = board.begin();

                for (auto cell = leastCands + 1; cell != board.end(); ++cell)
                {
                    if (!cell->solved())
                    {
                        if (cell->candidatesCount() < leastCands->candidatesCount() || leastCands->solved())
                        {
                            leastCands = cell;
                        }
                    }
                }

                toCheck.push_back(leastCands - board.begin()); //toCheck IS GUARANTEED TO BE EMPTY BEFORE THIS LINE

                board.solvedCells++;

                auto& cands = leastCands->getCandidates();

                for (auto cand = cands.begin(); cand != cands.end() - 1; ++cand)
                {
                    totalBoards++;

                    leastCands->setNum(*cand);

                    if (solve(board, toCheck))
                    {
                        solved = true;

                        if (uniqueSol)
                            return true;
                    }
                }

                leastCands->setNum(cands.back());
            }
        }

        return solved;
    }

public:
    SudokuSolver(std::string_view boardStr) : totalBoards(0)
    {
        SudokuBoard::side = sqrt(boardStr.length());
        SudokuBoard::initUniqueConts();

        startBoard.initCells(boardStr);
    }

    SudokuSolver(std::string_view boardStr, const std::vector<uniqueContainers>& areas, bool boxes = true) : totalBoards(0)
    {
        SudokuBoard::side = sqrt(boardStr.length());
        SudokuBoard::initUniqueConts(boxes);
        for (const auto& area : areas)
        {
            SudokuBoard::addUniqueConts(area);
        }

        startBoard.initCells(boardStr);
    }

    int solve(bool uniqueSolution = false)
    {
        uniqueSol = uniqueSolution;
        std::vector<cellIndex> toCheck;

        for (auto cell = startBoard.begin(); cell != startBoard.end(); ++cell)
        {
            if (cell->solved())
            {
                toCheck.push_back(cell - startBoard.begin());
            }
        }

        totalBoards++;
        return solve(startBoard, std::move(toCheck));
    }

    friend std::ostream& operator<<(std::ostream& os, const SudokuSolver& solver)
    {
        os << "TESTED " << solver.totalBoards << " BOARDS" << std::endl;

        if (solver.uniqueSol)
        {
            os << "FIRST SOLUTION FOUND" << std::endl;
        }
        else
        {
            os << solver.solutions.size() << " SOLUTIONS FOUND" << std::endl;
        }

        for (const auto& sol : solver.solutions)
            os << sol << std::endl << std::endl;

        os << "INITIAL BOARD " << std::endl << solver.startBoard << std::endl;

        return os;
    }
};

Answer 1

I see a number of things that may help you improve your program.

Use the appropriate #includes

In order to compile and link, the SudokuBoard.h file requires some additional headers:

#include <cmath>

Also, where the code uses sqrt, this should be qualified with a namespace as std::sqrt.

Employ header guards in all headers

Every header should be encapsulated with header guards to avoid problems if headers get included twice.

Separate interface from implementation

The interface goes into a header file and the implementation (that is, everything that actually emits bytes including all functions and data) should be in a separate .cpp file. As these classes are written, everything is inlined, so while that compiles, it's not really optimal from a design standpoint. As written, it takes a great deal of effort to study, for example, the source code of SudokuSolver.h to try to determine the public interface for the SudokuSolver class.

Make each header file standalone

The SudokuSolver.h header file uses std::vector, std::string_view and others. For that reason, it should include the appropriate headers rather than relying on another local included file to do that on its behalf. See SF.11.

Don't use std::endl if '\n' will do

Using std::endl emits a \n and flushes the stream. Unless you really need the stream flushed, you can improve the performance of the code by simply emitting '\n' instead of using the potentially more computationally costly std::endl.

Fully qualify static data members in external functions

Within the code for std::ostream& operator<<(std::ostream& os, const SudokuBoard& board), in some cases the static data side is correctly referred to as board.side but in other places it's just side. To maintain consistency (and to allow linking when you separate implementation from interface as suggested above), every instance should be board.side.

Fully initialize objects

The SudokuBoard object contains a number of values which should be initialized, including solvedCells. Right now this unitialized value is used before any value is assigned to it which is undefined behavior. Generally, it's best to initialize every member variable. See C.41. Also, writing this:

void initCells(std::string_view boardStr) //CALL ONLY AFTER INITIALIZING UNIQUE CONTAINERS

is a bad idea for a public class member function. If there are invariants (that is, things that must always be true for a class instance), the class itself should take care of them and not rely on the user to always do the right thing.

Prefer using to typedef for aliases

Instead of lines like these:

typedef std::vector<Cell>::iterator cellIt;
typedef short cellIndex;

I'd recommend writing them like this:

using cellIt = std::vector<Cell>::iterator;
using cellIndex = short;

This makes them easier for humans to read and understand. See T.43.

Be wary of friends

Your human friends are probably just fine, but friend classes should be viewed with some skepticism. For instance, in this code we have friend class SudokuSolver; as part of the SudokuBoard class. Since the only use of the SudokuBoard class, this suggests that something is wrong with the interface of the SudokuBoard class. The SudokuBoard should be usable to any calling class without being declared as a friend.

Rethink your class interfaces

In addition to the suggestion above, it may be useful to revisit the class interfaces. For example, we have this somewhat complex line in the SudokuSolver class:

SudokuProgress progress = board[cell].removeCandidate(board[eraser].getNum());

It's not obvious what that's supposed to be doing. I'd suggest many of the functions that take a SudokuBoard& argument should probably instead be member functions of the SudokuBoard class.