3
\$\begingroup\$

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;
}
\$\endgroup\$

migrated from stackoverflow.com Mar 6 '14 at 16:39

This question came from our site for professional and enthusiast programmers.

  • 3
    \$\begingroup\$ @parsaporahmad Why should threads make anything faster? \$\endgroup\$ – Till Feb 28 '14 at 20:04
  • 6
    \$\begingroup\$ Please format your code correctly, even if it takes you 3 minutes more ! \$\endgroup\$ – Michael Walz Feb 28 '14 at 20:04
  • 6
    \$\begingroup\$ if ( board[x][y] = a; xxx;? (The code requires a bit more than just formatting) \$\endgroup\$ – Aki Suihkonen Feb 28 '14 at 20:05
  • 3
    \$\begingroup\$ 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. \$\endgroup\$ – Jongware Feb 28 '14 at 20:08
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – KarlP Feb 28 '14 at 20:17
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

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