Sudoku solver in c crashes

Question

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;
        }
    }
}

Answer 1

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('
');
  }
  putchar('
');
}

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