Optimizing Sudoku solver in C++

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
#include
#include
#include

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>tab_in[i][j];
}
}
void output_solve()
{
for(int i=0; i0)
{
cout0) 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++;
}
}

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= 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

StackExchange Code Review Q#47949, answer score: 9