Please explain the code line by line with comments. #include <stdio.h> int isAva
ID: 3734307 • Letter: P
Question
Please explain the code line by line with comments.
#include <stdio.h>
int isAvailable(int puzzle[][9], int row, int column, int num)
{
int rowStart = (row/3) * 3;
int colStart = (column/3) * 3;
int i, j;
for(i=0; i<9; ++i)
{
if (puzzle[row][i] == num) return 0;
if (puzzle[i][column] == num) return 0;
if (puzzle[rowStart + (i%3)][colStart + (i/3)] == num) return 0;
}
return 1;
}
int fillSudoku(int puzzle[][9], int row, int column)
{
int i;
if(row<9 && column<9)
{
if(puzzle[row][column] != 0)
{
if((column+1)<9) return fillSudoku(puzzle, row, column+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, column, i+1))
{
puzzle[row][column] = i+1;
if((column+1)<9)
{
if(fillSudoku(puzzle, row, column +1)) return 1;
else puzzle[row][column] = 0;
}
else if((row+1)<9)
{
if(fillSudoku(puzzle, row+1, 0)) return 1;
else puzzle[row][column] = 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))
{
for(i=1; i<10; ++i)
{
for(j=1; j<10; ++j)
printf("%d ", puzzle[i-1][j-1]);
printf(" ");
}
}
else printf(" not possilbe to solve ");
return 0;
}
Explanation / Answer
Here is the explaination:
As from the code it is clear that it is a SUDOKU puzzle solver. Puzzle is a 2-dimentional array of integers which contains the initial value of the puzzle.
#include <stdio.h>
int isAvailable(int puzzle[][9], int row, int column, int num)
{
int rowStart = (row/3) * 3; // calculate the start row value of the 3x3 box in which the location [row][column] belongs
int colStart = (column/3) * 3; // calculate the start column value of the 3x3 box in which the location [row][column] belongs
int i, j;
for(i=0; i<9; ++i)
{
if (puzzle[row][i] == num) return 0; //checking if the row have the num already, if it does then we cant add this number in the location [row][column]
if (puzzle[i][column] == num) return 0; // checking if the column have the num already, if it does then we cant add this number in the location [row][column]
if (puzzle[rowStart + (i%3)][colStart + (i/3)] == num) return 0;// checking the 3x3 square in which the location [row][column] belongs, if it does then we cant add this number in the location [row][column]
}
return 1;
}
int fillSudoku(int puzzle[][9], int row, int column) // this is a recursive function to fill sudoku puzzle which takes the 2 dimantional array and initial value to start from which is 0,0
{ // think this function as a solver which fills one blank space at a time with appropiate value which starts from 0,0 location and fills one row at a time.
int i;
if(row<9 && column<9)
{
if(puzzle[row][column] != 0) //this will check if the given location [row][column] is zero or not , if not zero then we dont need to fill it so we should move to next space
{
if((column+1)<9) return fillSudoku(puzzle, row, column+1); // we will first fill the row, so we will check if any column in the row is empty or not, if so we will try to fill it recursively
else if((row+1)<9) return fillSudoku(puzzle, row+1, 0); //if the row is full, then we will move to next row, and call this function recursively
else return 1; // if none of them is true then the the matrix is filled
}
else // if the location [row][column] is not filled then we have to fill it.
{
for(i=0; i<9; ++i) // check for all possible number from 1 to 9 to fill the location
{
if(isAvailable(puzzle, row, column, i+1)) // isAvailable function will tell us if the number i+1 can be put in the location [row][column] without violating SUDOKU game conditions.
{
puzzle[row][column] = i+1; // if the number is available then we can put i+1 in that location.
if((column+1)<9) // as we filled this location then we will move to next column in same row if it is not the last column of the row
{
if(fillSudoku(puzzle, row, column +1)) return 1; // again recursively call fillSudoku function for the new location it will only return 1 if all of its values are satisfied
else puzzle[row][column] = 0; // if we cant satisfy constraints guessed on this assumptions we will remove our assumption
}
else if((row+1)<9)
{
if(fillSudoku(puzzle, row+1, 0)) return 1; // similarly if it was the last column of the row we will increase row and recursively call the fill sudoku function to check it satisfies current valuation
else puzzle[row][column] = 0; // otherwise we will mark it zero
}
else return 1; // the puzzle if full
}
}
}
return 0; // we will come to this line if and only if we cant get any satisfiable solution
}
else return 1;
}
int main()
{
int i, j;
int puzzle[9][9]={{0, 0, 0, 0, 0, 0, 0, 9, 0}, // this is the initial value of the sudoku puzzle 0 is empty space and 1 to 9 are the initial entries in the puzzle
{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)) // if we can fill the sudoku puzzle with appropiate numbers then print the solution
{
for(i=1; i<10; ++i)
{
for(j=1; j<10; ++j)
printf("%d ", puzzle[i-1][j-1]);
printf(" ");
}
}
else printf(" not possilbe to solve "); // if we cant then say that the current puzzle can not be solved.
return 0;
}
P.S: If you like this solution please give a thumbs up. Also please give us feedback so that we can find better ways to help you.
Happy Chegging!