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
returns 1
if there are still 0s in the sudoku and 0
if there are no more 0s.
isSafe
returns 1
if all rows, columns and 3x3 grid does not contain the number and 0
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;
}
}
}
A simple (but not the most efficient because of symmetries/rotations) way is to try all the possibilities trying to place the number 1 up to 9 on the successive positions (0,0 0,1 .. 0,8 1,0 ... ) recursively, each time a number can be put on 8,8 it is a solution
Few changes are needed from your code, just to remove the useless FindUnassignedLocation and add the recursion
If I replace 9 by SZ to also be able to search for the sizes 3, 6 or 9 and I add the draw of the solutions the code can be :
#include <stdio.h>
// 3, 6 or 9
#define SZ 9
/* Returns an int which indicates whether an assigned entry
in the specified row matches the given number. */
int UsedInRow(int grid[][SZ], int row, int num)
{
for (int col = 0; col < SZ; 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[][SZ], int col, int num)
{
for (int row = 0; row < SZ; 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[][SZ], 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[][SZ], int row, int col, int num)
{
/* Check if 'num' is not already placed in current row,
current column and current 3x3 box */
return (!UsedInRow(grid, row, num) &&
!UsedInCol(grid, col, num) &&
!UsedInBox(grid, row - row % 3, col - col % 3, num));
}
/* print a solution */
void draw(int sudoku[][SZ])
{
for (int row = 0; row != SZ; ++row) {
for (int col = 0; col != SZ; ++col)
printf("%d", sudoku[row][col]);
putchar('\n');
}
putchar('\n');
}
void solve_sudoku(int sudoku[][SZ], int row, int col)
{
for (int num = 1; num <= 9; num++) { //loop through numbers 1 to SZ
if (isSafe(sudoku, row, col, num) == 1) { //the number is safe
sudoku[row][col] = num;
if ((col + 1) == SZ) {
if ((row + 1) == SZ) {
// done
draw(sudoku);
}
else
solve_sudoku(sudoku, row + 1, 0);
}
else
solve_sudoku(sudoku, row, col + 1);
sudoku[row][col] = 0;
}
}
}
int main()
{
int sudoku[SZ][SZ] = {0};
solve_sudoku(sudoku, 0, 0);
}
first solutions found for SZ 3 (362880 possible solutions) :
123
456
789
123
456
798
123
456
879
123
456
897
123
456
978
123
456
987
123
457
689
First solutions found for SZ 6 :
123456
456789
789123
214365
365897
897214
123456
456789
789123
214365
365897
897241
123456
456789
789123
214365
365897
978214
123456
456789
789123
214365
365897
978241
123456
456789
789123
214365
365978
897214
123456
456789
789123
214365
365978
897241
First solutions found for SZ 9
123456789
456789123
789123456
214365897
365897214
897214365
531642978
642978531
978531642
123456789
456789123
789123456
214365897
365897214
897214365
531642978
648971532
972538641
123456789
456789123
789123456
214365897
365897214
897214365
531642978
672938541
948571632
123456789
456789123
789123456
214365897
365897214
897214365
531642978
678931542
942578631
123456789
456789123
789123456
214365897
365897214
897214365
531642978
942578631
678931542