10
\$\begingroup\$

I made a sudoku solver using backtracking in C++ and I would like to know what can I do to speed up my code. I am new to this language and I don't know all its special tricks yet! I was told to go to this website for this type of question.

This is my class definition (sudoku.h)

const int SIZE = 9;
class sudoku
{
public:
    static int steps;
    sudoku(std::string input_sudoku);
    void print();
    bool solve();

private:
    int grid[SIZE][SIZE];
    int posibilities[SIZE][SIZE];
    bool add_works(int num, int row, int col);
    bool solve_recursive(int row, int col);
    bool find_next(int* row, int* col);
    bool solve_recursive2();
    bool find_all_possibilities(int& row, int& col, bool& remaining);
};

And this is my implementation (sudoku.cpp)

int sudoku::steps = 0;

sudoku::sudoku(std::string input_sudoku)
{
    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) {
            int value = input_sudoku[i*SIZE + j] == '.' ? 0 : input_sudoku[i*SIZE + j] - '0';
            grid[i][j] = value;
            posibilities[i][j] = 0;
        }
    }
    print();
}

void sudoku::print()
{
    std::cout << "print : " << steps << std::endl;
    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) {
            if (grid[i][j] == 0)
                std::cout << ' ';
            else
                std::cout << grid[i][j];
        }

        std::cout << "\n";
    }
    std::cout << "\n";
}
bool sudoku::solve() 
{
    auto begin = std::chrono::high_resolution_clock ::now();
    //if (solve_recursive(0,0)) {
    if (solve_recursive2()) {
        auto delta = std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::high_resolution_clock::now() - begin).count();
        std::cout << "Elapsed time (us): "<< delta << std::endl;
        print();
        return true;
    }
    return false;   
}

bool sudoku::solve_recursive(int row, int col)
{
    steps++;
    if (!find_next(&row, &col)) return true;
    for (int i = 1; i <= SIZE; i++) {
        if (add_works(i, row, col)) {
            grid[row][col] = i;
            if (solve_recursive(row, col))
                return true;
            else
                grid[row][col] = 0;
        }
    }
    return false;
}

bool sudoku::find_next(int* row, int* col) 
{
    for (; *row < SIZE; (*row)++) {
        for (; *col < SIZE; (*col)++) {
            if (grid[*row][*col] == 0)
                return true;
        }
        (*col) = 0;
    }
    return false;
}

bool sudoku::solve_recursive2()
{
    steps++;
    int row, col;
    bool remaining;
    if (!find_all_possibilities(row, col, remaining)) return false;
    if (!remaining) return true;
    for (int i = 1; i <= SIZE; i++) {
        if (add_works(i, row, col)) {
            grid[row][col] = i;
            if (solve_recursive2())
                return true;
            else
                grid[row][col] = 0;
        }
    }
    return false;
}

bool sudoku::add_works(int num, int row, int col)
{
    int s_row = row / 3, s_col = col / 3;
    for (int i = 0; i < SIZE; i++) {
        if (grid[i][col] == num || //check col
            grid[row][i] == num || //check row
            grid[s_row * 3 + i / 3][s_col * 3 + i % 3] == num) //check square
            return false;
    }
    return true;
}

bool sudoku::find_all_possibilities(int& row, int& col, bool& remaining)
{
    int min = 10;
    remaining = false;
    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) {
            if (grid[i][j] == 0){
                posibilities[i][j] = 0;
                for (int k = 1; k <= SIZE; k++) {
                    if (add_works(k,i,j)){
                        posibilities[i][j]++;
                    }
                }
                if (posibilities[i][j] == 0)
                    return false;
                remaining = true;
                if (posibilities[i][j] < min) {
                    min = posibilities[i][j];
                    row = i;
                    col = j;
                    if (posibilities[i][j] == 1)
                        return true;
                }   
            }
        }
    }
    return true;
}

And this is the client code (main.cpp) I used two sudoku I found on internet, one hard and one easy to test the speed of the algorithm

int main() {    
    string sudoku_easy = "000079065000003002005060093340050106000000000608020059950010600700600000820390000";
    sudoku sudo_easy = sudoku(sudoku_easy);
    sudo_easy.solve();

    string sudoku_hard = "4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......";
    sudoku sudo_hard = sudoku(sudoku_hard);
    sudo_hard.solve();
}
\$\endgroup\$
  • 1
    \$\begingroup\$ One thing that I definitely would recommend is to do a few first passes over the board and see which cells only have one possible value. You should keep doing this until you can't find any cells that only have one possible value. For me this provided me with a large speedup for easier boards. For benchmarking, you can try these sudokus: sudocue.net/files/sudoku-x-12-7193.sdm which are the hardest there are. \$\endgroup\$ – maxb May 31 '18 at 12:24
  • \$\begingroup\$ The fastest implementation is Knuth’s “Dancing Links”. \$\endgroup\$ – JDługosz May 31 '18 at 22:03
2
\$\begingroup\$

Performance
First, the best way to optimize C++ code is to compile it -O3. Then profile the code to find out where the bottlenecks are.

In the bad old days when inline functions needed to be explicitly declared, incrementing a pointer through an array would have been a good way to speed up the code, iterators are preferred over pointers now. Using iterators would mean changing from the C style integer arrays currently used to the C++ container type std::array. After utilizing iterators you can then look at the STL algorithms and see if any can help. All of the STL algorithms have been optimized as much as possible to make the STL library perform as well as it can.

It might be good to think about data heuristics in find_all_possibilities(). Rather than starting with 9 and working down to 1 it might be better to find the most common number and solve that first. After that solve for the next most populated number. For example, the hard Sudoku has three 4s, two 1s, two 2s, two 7s and two 8s, try solving for 4 first. Try solving the 3 x 3 square that is most populated first.

Algorithms will supply faster solutions that optimizing the code.

Add Test Cases
It might be good to get multiple hard puzzles, get all the times and average them. Maybe have 3 loops of tests that have averages. An average for easy puzzles, and average for medium puzzles and an average for hard puzzles.

Remove Unused Code
The functions solve_recursive() and find_next() are unused. It might have been better to remove these functions prior to the code review. Unused code can confuse anyone that needs to maintain the code or review the code.

The find_next() function is using pointers. The use of C style pointers is discouraged in modern C++.

Style Improvements
It might be better to have one declaration and initialization per statement, someone that needs to modify the code might miss part of this line in the function add_works():

    int s_row = row / 3, s_col = col / 3;

It might be better if the code was like this:

    int s_row = row / 3;
    int s_col = col / 3;

More vertical spacing might help the readability of the code.

The function find_all_possibilities() is rather complex, it might be good to break it up into sub functions if you can.

Output
What are the time units being measured, milliseconds, nanoseconds? It might help the user if the output contained the units as well as the numbers

The solved matrix is hard to read, it might be better to put 2 or 3 spaces between each number output and space the lines.

\$\endgroup\$
0
\$\begingroup\$

You might try different types for the cells other than int. If they were one-byte, you would fit more into the data cache. Use a typedef for cell_type everywhere instead of int and it will be easy to change and check timing differences (like I do here since the result can go either way!

Division and modulo is very slow, and jams up the CPU besides. For division by a constant, the CPU will go to some effort to replace that with a multiply and a few other short operations. But your %3 is a lot of effort for simply wrapping around.

grid[s_row * 3 + i / 3][s_col * 3 + i % 3] == num) //check square

Here you are holding s_row and s_col constant (so define the local variables as const!) and incrementing i in a loop. So don’t calculate the two-d indexing each time!! Precomputing the two indexes and just adding 1 each time is a start, but I think you can use strides technique to move from square to square with one pointer addition each time.


⧺ES.9 Avoid ALL_CAPS names. Such names are commonly used for macros.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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