I am trying to figure out what is wrong with my code which is supposed to solve a 9x9 sudoku which crashes when I run it with the example in the Wikipedia for sudoku.
I have also tried using recursion but am not very familiar with it so it did not work either.
findunassignedlocation
returns1
if there are still 0s in the sudoku and0
if there are no more 0s.isSafe
returns1
if all rows, columns and 3x3 grid does not contain the number and0
otherwise.
If the problem is probably in one of the other functions, please let me know, I will send code. Ignore the depth
variable.
Below is my code:
/* Returns an int which indicates whether if the sudoku has any
more empty entries (which shows as a 0) */
int FindUnassignedLocation(int grid[9][9]) {
for (int row = 0; row < 9; row++)
for (int col = 0; col < 9; col++)
if (grid[row][col] == 0)
return 1;
return 0;
}
/* Returns an int which indicates whether an assigned entry
in the specified row matches the given number. */
int UsedInRow(int grid[9][9], int row, int num) {
for (int col = 0; col < 9; col++)
if (grid[row][col] == num)
return 1;
return 0;
}
/* Returns an int which indicates whether an assigned entry
in the specified column matches the given number. */
int UsedInCol(int grid[9][9], int col, int num) {
for (int row = 0; row < 9; row++)
if (grid[row][col] == num)
return 1;
return 0;
}
/* Returns an int which indicates whether an assigned entry
within the specified 3x3 box matches the given number. */
int UsedInBox(int grid[9][9], int boxStartRow, int boxStartCol, int num) {
for (int row = 0; row < 3; row++)
for (int col = 0; col < 3; col++)
if (grid[row + boxStartRow][col + boxStartCol] == num)
return 1;
return 0;
}
/* Returns an int which indicates whether it will be legal to assign
num to the given row,col location. */
int isSafe(int grid[9][9], int row, int col, int num) {
/* Check if 'num' is not already placed in current row,
current column and current 3x3 box */
if (!UsedInRow(grid, row, num) &&
!UsedInCol(grid, col, num) &&
!UsedInBox(grid, row - row % 3, col - col % 3, num) &&
grid[row][col] == 0) {
return 1;
} else {
return 0;
}
}
void solve_sudoku(int sudoku[9][9]) {
int row = 0;
int col = 0;
if (FindUnassignedLocation(sudoku) == 0) { //if sudoku is completely filled
return;
}
for (int num = 1; num <= 9; num++) {
if (isSafe(sudoku, row, col, num) == 1) {
sudoku[row][col] = num;
solve_sudoku(sudoku, depth);
sudoku[row][col] = 0;
}
}
}
See Question&Answers more detail:os