Optimizing Sudoku solver in C++

Question

Recently, I wrote a Sudoku solver in C++. My program is very hard and was solved in a few seconds. In my opinion, this is slow.

#include <iostream>
#include <conio.h>
#include <stdlib.h>
#include <time.h>

using namespace std;

int tab_in[9][9] = {{0,0,0,0,0,0,0,1,0},
                    {4,0,0,0,0,0,0,0,0},
                    {0,2,0,0,0,0,0,0,0},
                    {0,0,0,0,5,0,4,0,7},
                    {0,0,8,0,0,0,3,0,0},
                    {0,0,1,0,9,0,0,0,0},
                    {3,0,0,4,0,0,2,0,0},
                    {0,5,0,1,0,0,0,0,0},
                    {0,0,0,8,0,6,0,0,0}};


int squares[9][9] = {{0,0,0,0,0,0,0,0,0},
                     {0,0,0,0,0,0,0,0,0},
                     {0,0,0,0,0,0,0,0,0},
                     {3,3,3,3,3,3,3,3,3},
                     {3,3,3,3,3,3,3,3,3},
                     {3,3,3,3,3,3,3,3,3},
                     {6,6,6,6,6,6,6,6,6},
                     {6,6,6,6,6,6,6,6,6},
                     {6,6,6,6,6,6,6,6,6}};


int tab_out[9][9];
int tab[9][9];
int tab_insert[9][9][10];
int iter=0;

void output_solve();

void load();

bool check(int x, int y, int value);

bool next(int x, int y);

bool solve(int x, int y);

void can_insert();

int main()
{
    //load();
    for(int i=0; i<9; i++)
    {
        for(int j=0; j<9; j++)
        {
            tab_out[i][j]=tab_in[i][j];
        }
    }
    can_insert();
    int a = clock();
    if(!solve(0, 0))
    {
        cout<<"This sudoku is unsolvable!"<<endl;
    }
    else
    {
        output_solve();
        cout<<"\n"<<iter<<endl;
    }
    int b = clock();
    cout<<(b-a)<<"ms"<<endl;
    cout<<iter;
    getch();
    return 0;
}
bool check(int x, int y, int value) 
{
    for(int i = 0; i < 9; i++) 
    {
        if (value == tab_out[x][i] || value == tab_out[i][y]) 
        { 
            return false; 
        }
    }
   for (int i = squares[x][y]; i <= squares[x][y]+2; i++) 
    {
        for (int j = squares[y][x]; j <= squares[y][x]+2; j++) 
        {
    /*for (int i = (x/3)*3; i <= ((x/3)*3)+2; i++) 
    {
        for (int j = (y/3)*3; j <= ((y/3)*3)+2; j++)
        {*/
            if (tab_out[i][j] == value) 
            {
                return false;
            }
        }
    } 
    return true;
}

bool next(int x, int y) 
{
    if (x == 8 && y == 8) return true;
    else if (x == 8) return solve(0, y + 1);
    else return solve(x + 1, y);
}

bool solve(int x, int y) 
{
    if (tab_in[x][y] == 0) 
    {
        int max = tab_insert[x][y][9];
        for(int i = 0; i<max; i++) 
        {
            int val = tab_insert[x][y][i];
            if (check(x, y, val)) 
            {
                tab_out[x][y] = val;
                if (next(x, y)) return true;
            }
        }
        iter++;
        tab_out[x][y] = 0;
        return false;
    } 
    return next(x, y);
}

void load()
{
    for(int i=0; i<9; i++)
        for(int j=0; j<9; j++)
        {
            cout<<i+1<<", "<<j+1<<endl;
            cin>>tab_in[i][j];
        }
}
void output_solve()
{
    for(int i=0; i<9; i++)
    {   cout<<endl;
        if(i%3==0 &&i>0)
        {
            cout<<"---------------\n";
        }
        for(int j=0; j<9; j++)
        {
            if(j%3==0 && j>0) cout<<" | ";
            cout<<tab_out[i][j];
        }
    }
}

void can_insert()
{
    for(int i=0; i<9; i++)
    {
        for(int j=0; j<9; j++)
        {
            for(int k=0; k<9; k++)
            {
                tab_insert[i][j][k]=0;
            }
        }
    }
    for(int i = 0; i<9; i++)
    {
        for(int j = 0; j<9; j++)
        {
            if(tab_in[i][j]==0)
            {
                int count = 0;
                for(int k = 1; k<=9; k++)
                {
                    if(check(i, j, k))
                    {
                        tab_insert[i][j][count] = k;
                        count++;
                    }
                }
                tab_insert[i][j][9]=count;
            }
        }
    }
}

How can I optimize this? Where can I find a good Sudoku solver implementation in C/C++?

Answer 1

Here are some comments that will help you write a better program.

If you're writing C++, use C++

You have included a number of plain C headers, one of which (conio.h) isn't even a Posix standard. Instead, write C++ instead of C++ in a C style. There are many books that can help with this. I usually recommend The C++ Programming Language, 4th ed. by Bjarne Stroustrup. Generally, though, it involves the use of objects instead of just functions, which brings us to the next point.

Use classes

C++ is an object oriented language, and much of its expressiveness derives from that. When you have multiple functions all using the same data structure, as in this code, it's usually a very good hint that the data structure should probably be a class and that the functions should be member functions.

Avoid global variables

Global variables are generally a bad idea. They make your code fragile, difficult to understand, maintain and reuse and impossible to multithread. There is no reason that all of the global variables in your program couldn't be gathered neatly together into an object and then the object a local variable within main.

Comment your code

It's not very easy to read your code and figure out what algorithm is being used to solve the puzzle. Comments help with that and they also describe the purpose and use of individual functions and variables. Uncommented code is usually not easy to maintain.

Name functions well

You have functions called solve and output_solve which give some hint as to their purpose by their name. That's good and just what you want. However, you also have some much more opaque names such as check and can_insert which I might be able to figure out, but without comments the only hint is the function name. Both well-chosen function name and comments are an essential part of the code.

Don't abuse using namespace std

Putting that line in every program is a bad habit that you should avoid.

Profile your code

Finally, after you've cleaned things up, then profile your code. That is, measure which parts are slow and think about the underlying algorithm(s) you're using. Are there better ways of solving the problem? Can you reduce the number of operations or the amount of memory needed? All of these are general ways to speed up a program, but with that said, it's important to make it correct first, and then work on speed optimizations. You have the benefit in that you already have a correct, but slow, implementation.

Think about the user

In order to solve a different puzzle, one has to encode it and recompile. I see that you wrote a load() function so you were thinking about being able to read in a new puzzle, but that's not implemented, and the way that it's written requires a space between every digit and will spin off into an infinite loop if the user accidentally enters a letter. Think about making that a little more durable and then use it instead of a hard-coded data structure. As a bit of a head start, here's a rewritten load() that will work with your exising program.

void load()
{
    std::string line;
    for(int i=0; i<9; i++) {
        std::getline(std::cin, line);
        for(int j=0; j<9; j++) {
            int ch = line[j]-'0';
            if ((ch >= 1) && (ch <= 9))
                tab_in[i][j] = ch;
        }
    }
}

If you uncomment your load() within main, you can read this file from the command line:

.......1.
4........
.2.......
....5.4.7
..8...3..
..1.9....
3..4..2..
.5.1.....
...8.6...

which is identical to your hard-coded puzzle. When you get that all working, consider how your code might solve this one which the current code (incorrectly) states is not solvable.

5.2..6...
...8...41
...4.2...
.7....568
..9...4..
483....9.
...2.3...
93...4...
...9..3.7

Answer 2

If you actually wanted to solve Sudoku instances as quickly as possible, you should consider a SAT solver or a CSP solver. They can work as a black box; just model your Sudoku instance in either formalism, feed it to a solver, and press go.

As far as I can tell, your solver does a brute-force search: pick some variable, try a value, see what happens, and backtrack if you hit a dead-end. There's a very effective heuristic you can use that comes from the domain of CSP solvers. Instead of choosing a "random" cell to assign a value to, choose the variable that has that the fewest legal values. This is a so-called "fail-first heuristic", and the intuition is that this choice is most likely to fail soon, and it thereby prunes the search tree. This heuristic alone should allow you to solve any 9x9 puzzles in a second or two on modern hardware.

This is not a C++-specific answer, but simply an answer from an algorithmic perspective.