Faster Sudoku solver in C

Question

I am writing a Sudoku solver in C, but am having problems with how long it takes to run. It can solve easier puzzles but once I put in one a little more difficult it runs and runs and never stops.

int solver (int x, int y)
{
 int a;
 int b;
 int i;
 int j;
 printf("Depth: %d\n", counter);
 for (a=1; a<10; a++)
 { 
 if (checkEverything(x, y, a))
 {
 board[x][y] = a;
 counter++;
 if (counter == 81)
 {
 return true;
 }
 if (counter > 200 || counter < -10) {
 return false;
 }
 for (i=0; i<9; i++)
 {
 for (j=0; j<9; j++)
 {
 if (board[i][j] == 0)
 {
 if (solver(i, j))
 {
 return true;
 } 
 }
 }
 }
 counter--;
 //printf("%d", a); 
 }
 }
 //printf("No Solution1");
 board[x][y] = 0;
 return false;
}

• Till: @parsaporahmad Why should threads make anything faster?
• Michael Walz: Please format your code correctly, even if it takes you 3 minutes more !
• Aki Suihkonen: if ( board[x][y] = a; xxx;? (The code requires a bit more than just formatting)
• Jongware: Put a counter in and check how many guesses you are making. Mathemathics suggests this runs in the billions. Try to make a "hard" Sudoku into a "simple" one by first testing for easy solutions on rows, columns, and blocks, before going Brute Force.
• KarlP: I don't see any of the important parts here so I don't know why it's slow. If it takes more than a few seconds to solve a 9x9 sudoku, the algorithm is flawed. I did a sudoku solver (in java) that solves (one solution) all "hard" examples on wiki in one or two seconds, and human solvable (or at least by me) in a few milliseconds. It's based on a naive depth first search with backtracking, but the trick to get that to work is to calculate all "fixed" positions before going bananas with generating solution candidates.

Answer 1

There are a number of things that could be improved in this code.

Post complete code

I understand that this code was migrated from Stack Overflow where the rules are a little different, but here on Code Review, we want to see not just one small piece but the whole code. I can guess what checkEveryting() and solver() might do, but you'll get better reviews here by not making reviewers guess.

Use a better algorithm

The fundamental problem with this code is that the algorithm is very inefficient. Look at the Related panel to the right and you'll see more than a half dozen other similar programs. Look over those to get ideas about how this might more efficiently be done.

Make the formatting consistent

The code currently include this:

 if (counter == 81)
 {
 return true;
 }
 if (counter > 200 || counter < -10) {
 return false;
 }

In one case, the opening { is on the same line, and in the other it's on the next line. It's a small thing, but it's useful to choose a convention and stick with it.

Avoid the use of global variables

I see that counter and board are declared as global variables rather than as local variables. It's generally better to explicitly pass variables your function will need rather than using the vague implicit linkage of a global variable.

Use meaningful variable names

The variable names a, and b are not at all descriptive. Better naming makes your code easier to read, understand and maintain.

Eliminate unused variables

Unused variables are a sign of poor code quality, so eliminating them should be a priority. In this code, b is declared but never actually used. My compiler also tells me that. Your compiler is probably also smart enough to tell you that, if you ask it to do so.