10
\$\begingroup\$

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

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

protected by Jamal Jun 16 '14 at 6:22

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.