** Question 58. Implement a Sudoku solver **

The Sudoku grid is square of size 9 * 9. The rules of Sudoku are as follows:

1. Each cell contains a number from 1 to 9

2. A number should not be repeated in the same row or the same column

3. The grid is further sub-divided into squares of 3*3 called boxes. A number should also not be repeated in the same box.

In the Sudoku puzzle, the puzzle writer fills up some of the cells with numbers and we have to fill up the remaining cells. To solve Sudoku, we make use of recursion and back-tracking. Given a cell, we recursively try out all possible numbers that can be filled up in the cell. So we fill a cell with a possible number and then move to the next cell. Suppose we hit a dead-end at a cell and can’t fill it with any number, then we back-track to the previous cell, try out the next possible number in the previous cell and proceed. To distinguish between the cells filled up by the puzzle writer and the other cells, we initialize the other cells with -1.

## C/C++

/* Helper function which checks if it is possible to place a number in a cell grid: the 2d sudoku matrix row_nr: row number of the cell we are checking col_nr: column number of the cell we are checking num: the number which we want to place in the cell Returns: 1 if we can place num in the cell, 0 otherwise */ int can_fill_cell(int grid[][NUM_COLS], int row_nr, int col_nr, int num) { int i, j; int region_start_row, region_start_col; /*Ensure that the number is not present in any row of requested column*/ for (i = 0; i < NUM_ROWS; ++i) if (grid[i][col_nr] == num) return 0; /*Ensure that the number is not present in any column of requested row*/ for (j = 0; j < NUM_COLS; ++j) if (grid[row_nr][j] == num) return 0; /*Ensure that the number is not present in the 3*3 box it belongs to*/ region_start_row = (row_nr / 3) * 3; region_start_col = (col_nr / 3) * 3; for (i = region_start_row; i < region_start_row + 3; ++i) for (j = region_start_col; j < region_start_col + 3; ++j) if (grid[i][j] == num) return 0; return 1; } /*Main function for solving the sudoku puzzle grid: the 2d sudoku matrix row_nr: row number of the current cell being processed col_nr: column number of the current cell being processed */ void solve_sudoku(int grid[][NUM_COLS], int row_nr, int col_nr) { int next_row, next_col, num; if (row_nr >= NUM_ROWS) { /*We have found a solution. print the grid and terminate the recursion*/ print_grid(grid, 1); return; } /*Pre-compute the row and column of the next cell*/ next_row = row_nr; next_col = col_nr + 1; if (next_col >= NUM_COLS) { next_col = 0; next_row = row_nr + 1; } if (grid[row_nr][col_nr] == -1) { /*The puzzle writer has not assigned a number to this cell. So try assigning numbers 1-9 to the cell*/ for (num = 1; num <= 9; ++num) { if (can_fill_cell(grid, row_nr, col_nr, num)) { grid[row_nr][col_nr] = num; solve_sudoku(grid, next_row, next_col); } } /*Once we are done trying all numbers from 1-9 assign the cell back to -1 to indicate puzzle writer has not assigned a number to the cell*/ grid[row_nr][col_nr] = -1; } else { /*The puzzle writer has already assigned a value to the cell. So proceed to the next cell*/ solve_sudoku(grid, next_row, next_col); } }

## Java

/* Helper function which checks if it is possible to place a number in a cell grid: the 2d sudoku matrix rowNr: row number of the cell we are checking colNr: column number of the cell we are checking num: the number which we want to place in the cell Returns: true if we can place num in the cell, false otherwise */ public static boolean canFillCell(int[][] grid, int rowNr, int colNr, int num) { /*Ensure that the number is not present in any row of requested column*/ int i, j; for (i = 0; i < NUM_ROWS; ++i) if (grid[i][colNr] == num) return false; /*Ensure that the number is not present in any column of requested row*/ for (j = 0; j < NUM_COLS; ++j) if (grid[rowNr][j] == num) return false; /*Ensure that the number is not present in the 3*3 box it belongs to*/ int regionStartRow = (rowNr / 3) * 3; int regionStartCol = (colNr / 3) * 3; for (i = regionStartRow; i < regionStartRow + 3; ++i) for (j = regionStartCol; j < regionStartCol + 3; ++j) if (grid[i][j] == num) return false; return true; } /*Main function for solving the sudoku puzzle grid: the 2d sudoku matrix rowNr: row number of the current cell being processed colNr: column number of the current cell being processed */ public static void solveSudoku(int[][] grid, int rowNr, int colNr) { if (rowNr >= NUM_ROWS) { /*We have found a solution. print the grid and terminate the recursion*/ printGrid(grid, true); return; } /*Pre-compute the row and column of the next cell*/ int nextRow = rowNr; int nextCol = colNr + 1; if (nextCol >= NUM_COLS) { nextCol = 0; nextRow = rowNr + 1; } if (grid[rowNr][colNr] == -1) { /*The puzzle writer has not assigned a number to this cell. So try assigning numbers 1-9 to the cell*/ for (int num = 1; num <= 9; ++num) { if (canFillCell(grid, rowNr, colNr, num)) { grid[rowNr][colNr] = num; solveSudoku(grid, nextRow, nextCol); } } /*Once we are done trying all numbers from 1-9 assign the cell back to -1 to indicate puzzle writer has not assigned a number to the cell*/ grid[rowNr][colNr] = -1; } else { /*The puzzle writer has already assigned a value to the cell. So proceed to the next cell*/ solveSudoku(grid, nextRow, nextCol); } }

## Python

#Helper function which checks if it is possible to place a number in a cell #grid: the 2-D sudoku matrix #row_nr: row number of the cell we are checking #col_nr: column number of the cell we are checking #num: the number which we want to place in the cell #Returns: True if we can place num in the cell, False otherwise def can_fill_cell(grid, row_nr, col_nr, num) : #Ensure that the number is not present in any row of requested column for i in range(0, NUM_ROWS): if (grid[i][col_nr] == num): return False #Ensure that the number is not present in any column of requested row for j in range(0, NUM_COLS): if (grid[row_nr][j] == num): return False #Ensure that the number is not present in the 3*3 box it belongs to region_start_row = (row_nr // 3) * 3 region_start_col = (col_nr // 3) * 3 for i in range(region_start_row, region_start_row + 3): for j in range(region_start_col, region_start_col + 3): if (grid[i][j] == num): return False return True #Main function for solving the sudoku puzzle #grid: the 2-D sudoku matrix #row_nr: row number of the current cell being processed #col_nr: column number of the current cell being processed def solve_sudoku(grid, row_nr, col_nr) : if (row_nr >= NUM_ROWS) : #We have found a solution. print the grid and #terminate the recursion print_grid(grid, True) return #Pre-compute the row and column of the next cell next_row = row_nr next_col = col_nr + 1 if (next_col >= NUM_COLS) : next_col = 0 next_row = row_nr + 1 if (grid[row_nr][col_nr] == -1) : #The puzzle writer has not assigned a number to this cell. #So try assigning numbers 1-9 to the cell for num in range(1, 10): if (can_fill_cell(grid, row_nr, col_nr, num)) : grid[row_nr][col_nr] = num solve_sudoku(grid, next_row, next_col) #Once we are done trying all numbers from 1-9, assign the cell #back to -1 to indicate puzzle writer has not assigned a number #to the cell grid[row_nr][col_nr] = -1 else : #The puzzle writer has already assigned a value to the cell. #So proceed to the next cell solve_sudoku(grid, next_row, next_col)