Sudoku Solver in C

Question

I had this code lying around, so I figured I would submit this as my first attempt at a weekend-challenge. I would prefer if reviews contained suggestions on how to improve the algorithm, but all suggestions are acceptable.

#include <stdio.h>

int isAvailable(int puzzle[][9], int row, int col, int num)
{
    int rowStart = (row/3) * 3;
    int colStart = (col/3) * 3;
    int i, j;

    for(i=0; i<9; ++i)
    {
        if (puzzle[row][i] == num) return 0;
        if (puzzle[i][col] == num) return 0;
        if (puzzle[rowStart + (i%3)][colStart + (i/3)] == num) return 0;
    }
    return 1;
}

int fillSudoku(int puzzle[][9], int row, int col)
{
    int i;
    if(row<9 && col<9)
    {
        if(puzzle[row][col] != 0)
        {
            if((col+1)<9) return fillSudoku(puzzle, row, col+1);
            else if((row+1)<9) return fillSudoku(puzzle, row+1, 0);
            else return 1;
        }
        else
        {
            for(i=0; i<9; ++i)
            {
                if(isAvailable(puzzle, row, col, i+1))
                {
                    puzzle[row][col] = i+1;
                    if((col+1)<9)
                    {
                        if(fillSudoku(puzzle, row, col +1)) return 1;
                        else puzzle[row][col] = 0;
                    }
                    else if((row+1)<9)
                    {
                        if(fillSudoku(puzzle, row+1, 0)) return 1;
                        else puzzle[row][col] = 0;
                    }
                    else return 1;
                }
            }
        }
        return 0;
    }
    else return 1;
}

int main()
{
    int i, j;
    int puzzle[9][9]={{0, 0, 0, 0, 0, 0, 0, 9, 0},
                      {1, 9, 0, 4, 7, 0, 6, 0, 8},
                      {0, 5, 2, 8, 1, 9, 4, 0, 7},
                      {2, 0, 0, 0, 4, 8, 0, 0, 0},
                      {0, 0, 9, 0, 0, 0, 5, 0, 0},
                      {0, 0, 0, 7, 5, 0, 0, 0, 9},
                      {9, 0, 7, 3, 6, 4, 1, 8, 0},
                      {5, 0, 6, 0, 8, 1, 0, 7, 4},
                      {0, 8, 0, 0, 0, 0, 0, 0, 0}};

    if(fillSudoku(puzzle, 0, 0))
    {
        printf("\n+-----+-----+-----+\n");
        for(i=1; i<10; ++i)
        {
            for(j=1; j<10; ++j) printf("|%d", puzzle[i-1][j-1]);
            printf("|\n");
            if (i%3 == 0) printf("+-----+-----+-----+\n");
        }
    }
    else printf("\n\nNO SOLUTION\n\n");

    return 0;
}

Test run:

$ ./SudokuSolver
+-----+-----+-----+
|7|4|8|6|3|5|2|9|1|
|1|9|3|4|7|2|6|5|8|
|6|5|2|8|1|9|4|3|7|
+-----+-----+-----+
|2|6|5|9|4|8|7|1|3|
|8|7|9|1|2|3|5|4|6|
|3|1|4|7|5|6|8|2|9|
+-----+-----+-----+
|9|2|7|3|6|4|1|8|5|
|5|3|6|2|8|1|9|7|4|
|4|8|1|5|9|7|3|6|2|
+-----+-----+-----+

Answer 1

Your solution is short and sweet. Hopefully my answer will be too since rolfl covered most of what I saw. :)

1. Perhaps solveSudoku will better convey the fact that it's solving the puzzle. fillSudoku sounds like a function that fills in the initial positions from a file or string or something.

2. You could shorten the "is the cell is filled" check by dropping the != 0 for maximum C-ness:

   if(puzzle[row][col])
   

3. You are duplicating the code that advances the cell indices in fillSudoku: once if the cell comes in already filled and again when you place the next guess. You can drop the latter and simply pass in the same cell indices since you're setting the cell's value first.

   if(isAvailable(puzzle, row, col, i+1))
   {
       puzzle[row][col] = i+1;
   
       if(fillSudoku(puzzle, row, col) return 1;
       else puzzle[row][col] = 0;
   }
   

Answer 2

I would love to go through and find all sorts of things that this code does badly... but, it's short, sweet, and works, and that in itself speaks to a measure of sophistication.

This solution is very lightweight on all resources other than CPU cycles, and it does not carry much through on the stack, either. All in all, it's neat, and well structured.

A few minor criticisms:

• in your isAvailable() method you declare j, but do not use it.
• the fancy modulo/divide mechanism (puzzle[rowStart + (i%3)][colStart + (i/3)] == num) for checking the block is just that, fancy... and probably needs some sort of comment. I have worked through the math, and I can see it is right, but some help there would have been useful.
• I don't like that you check values multiple times in isAvailable(), but I must admit that I cannot see a nice way to avoid the duplication without adding even more expensive complexity. By my calculation, you double-check 4 values, and triple-check 1. That is 5/27 checks are redundant... As I say, though, I think avoiding those checks will be more costly than the redundancy.
• in your fillSudoku method, you declare i and use it as for(i=0; i<9; ++i). Since, in this case, i is not actually an index to some array, or a simple loop limiter, but it is actually a puzzle digit, you should do two things:
  1. rename it to be something like digit
  2. change the loop to be: for(digit=1; digit<=9; ++digit), and then you can remove all the redundant +1 operations you do inside the loop (e.g. isAvailable(puzzle, row, col, i+1))