# Solving Sudoku using backtracking

This is a solver for Sudoku using backtracking. How can I make it more optimized and clean?

#include <stdio.h>

int isAvailable(int sudoku[][9], int row, int col, int num)
{
int i, j;
for(i=0; i<9; ++i)
if( (sudoku[row][i] == num) || ( sudoku[i][col] == num )  )//checking in row and col
return 0;

//checking in the grid
int rowStart = (row/3) * 3;
int colStart = (col/3) * 3;

for(i=rowStart; i<(rowStart+3); ++i)
{
for(j=colStart; j<(colStart+3); ++j)
{
if( sudoku[i][j] == num )
return 0;
}
}

return 1;
}

int fillsudoku(int sudoku[][9], int row, int col)
{
int i;
if( row<9 && col<9 )
{
if( sudoku[row][col] != 0 )//pre filled
{
if( (col+1)<9 )
return fillsudoku(sudoku, row, col+1);
else if( (row+1)<9 )
return fillsudoku(sudoku, row+1, 0);
else
return 1;
}
else
{
for(i=0; i<9; ++i)
{
if( isAvailable(sudoku, row, col, i+1) )
{
sudoku[row][col] = i+1;

if( (col+1)<9 )
{
if( fillsudoku(sudoku, row, col +1) )
return 1;
else
sudoku[row][col] = 0;
}
else if( (row+1)<9 )
{
if( fillsudoku(sudoku, row+1, 0) )
return 1;
else
sudoku[row][col] = 0;
}
else
return 1;
}
}
}
return 0;
}
else
{
return 1;
}
}

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

if( fillsudoku(sudoku, 0, 0) )
{

for(i=0; i<9; ++i)
{
for(j=0; j<9; ++j)
printf("%d ", sudoku[i][j]);
printf("\n");
}
}
else
{
printf("\n\nNO SOLUTION\n\n");
}

return 0;
}

Very nice:

Few minor changes I would make.

In isAvailable() I would check row/col/box all at the same time.

int isAvailable(int sudoku[][9], int row, int col, int num)
{
//checking in the grid
int rowStart = (row/3) * 3;
int colStart = (col/3) * 3;

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

return 1;
}

Which brings my to my first comment:
I prefer to have sub statments of while/for/if inside block quotes.

if( sudoku[i][j] == num )
return 0;

// I prefer this:
if( sudoku[i][j] == num )
{   return 0;
}

This way there is not chance of accidentally putting a macro that expands and is not all executed.

Your code for moving to the next square is in multiple places in the code:

if( (col+1)<9 )
STUFF(row, col+1);
else if( (row+1)<9 )
STUFF(row+1, 0);
else
WIN

Because it is multiple places you have redundancy. I would move this check to one location. The easiest way to do that is move it to the first few lines of code in the function. Then you always make a recursive call like this fillsudoku(sudoku, row, col+1).

int fillsudoku(int sudoku[][9], int row, int col)
{
if (col >= 9)
{
col = 0;
++row;
if (row >= 9)
{
return 1;
}
}

// Original code.
// When doing a recursive call use  fillsudoku(sudoku, row, col+1)
// You know the start of the code will test it.

Next I would exit early rather than have nested code.
This is a debatable point on style but I don;t think having to scroll down a long way to see a one lineer for failure helps in readability. And since you already exit early that is not a problem.

if( sudoku[row][col] != 0) //pre filled
{
return fillsudoku(sudoku, row, col+1);
}
else
{
for(i=0; i<9; ++i)
{
if( isAvailable(sudoku, row, col, i+1) )
{
sudoku[row][col] = i+1;

int good = fillsudoku(sudoku, row, col +1);
if (good)
{   return 1;
}
sudoku[row][col] = 0;
}
}
}
return 0;
}