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;
}

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.