Backtracking Sudoku Solver in C

[QuantumPebbel]

Hey. So for my Computer Science class I had to write a program that reads input from a file. Blank spaces on the sudoku board are represented by a period. Output is supposed to print the original blank puzzle out followed by the solved puzzle and a new line. The output prints to a single line and looks like this:

85...24..72......9..4.........1.7..23.5...9...4...........8..7..17..........36.4.
859612437723854169164379528986147352375268914241593786432981675617425893598736241

 

I have the code solving some puzzles, but the harder ones can take quite a while to solve, so I was wondering if anyone had any tips on how to make it run faster.
This is the code for the recursive solving algorithm. 46 is ASCII for period and 49 - 57 are the ASCII codes for 1-9. The puzzle must be solved by a recursive backtracking search.

/* This function recursively calls itself to perform a backtracking search
 * in order to find the solution to the Sudoku puzzle.
 */
int solve(int row, int col)
{
  char n = 0;

  if (col == 9)
  {
    col = 0;
    row++;
  }
  
  /* Return true if the puzzle is solved */
  if (row == 9)
  {
    return 1;
  }
  if (board[row][col] != 46)
  {
    if (solve(row, col+1)) return 1;
  }
  else
  {
    for (n = 49; n < 58; n++)
    {   
      /* If no repeated current value is valid, put it on the board. */
      if (redundancy() == FALSE)
      {
        board[row][col] = n; /*new test value */
        if (solve(row, col+1)) return 1;
      }
      board[row][col] = 46;
    }
  }
  return 0;
}

[Tamschi]

Tracking possibilities is a lot faster, so if you just mark things as impossible there's a chance only one option will be left and you won't have to backtrack (as much).

There are also a few additional rules you can apply: If a number is the only possible in one row or column in a cell, it becomes impossible in the same one in other cells along that direction (and the inverse, if it's impossible in two other cells along that line, it must be the right area in the final cell).

I made one in C# that's pretty much interactive (solving while you type, in a console GUI) years ago as my first actually useful program.
(The was a lottery that required you to solve these puzzles each weak etc.)

I think with those rules you still have to guess once or twice on the more difficult ones, but most of the backtracking will disappear.
My program has one manual save state and it was never few enough to be inconvenient.

[NilsFG]

[URL]http://norvig.com/sudoku.html[/URL]

Constraint propagation is your friend.

If you don't know who Peter Norvig is: he is/was quite a big name in AI and wrote one of the most important books on the subject (AIMA). He's now some honcho at Google.

[Egonny]

You can try [url=http://en.wikipedia.org/wiki/Backmarking]backmarking[/url], which is a variant of backtracking but eliminates a lot of redundant checks.