Sudoku solver – The Coding Interview Blog

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)