Sudoku Solver Editorial

Practice Problem Link: Sudoku Solver

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

You are given a 9 X 9 sudoku board where some cells are filled. You need to solve the sudoku.

A correctly solved sudoku has the following properties:

• Each row must contain all integers from 1 to 9.
• Each column must contain all integers from 1 to 9.
• Each of the nine 3 X 3 sub-boxes must contain all integers from 1 to 9.

Naive Approach

The naive approach is to fill all the empty cells with all the possible values from 0 - 9 and check if the final configuration of the board is valid or not. If it is valid, we return, else we go over to the next configuration.

Analysis

• Time Complexity: O(9^{(n * n)})
• Space Complexity: O(n * n)

Optimal Approach

The optimal approach will be the same as the naive approach, but we will cut off many possible impossible configurations as soon as we find them to occur, instead of making the entire configuration and checking it at the end. Before assigning a number, we check if it is safe to assign.  Check, if the current number is not present in the current row, current column, and current 3 X 3 subgrid, only then assign that number, else backtrack to the previous state.

Analysis

• Time Complexity: O(9^{(n * n)}) // The worst case is the same but the average case will be much better
• Space Complexity: O(n * n)

Implementation

C++

bool isValid(int value, int row, int col, vector<vector<char>> &board){
	bool rowIsValid = true;
	bool colIsValid = true;
	char digit = to_string(value).back();
	for(int i = 0; i < 9; i++){
		if(digit == board[row][i]){
			rowIsValid = false;
			break;
		}
		if(digit == board[i][col]){
			colIsValid = false;
			break;
		}
	}
	if(rowIsValid == false || colIsValid == false){
		return false;
	}
	int subgridrow = row / 3;
	int subgridcol = col / 3;
	for(int i = 0; i < 3; i++){
		for(int j = 0; j < 3; j++){
			int currRow = subgridrow * 3 + i;
			int currCol = subgridcol * 3 + j;
			if(digit == board[currRow][currCol]){
				return false;
			}
		}
	}
	return true;
}
bool solve(int row, int col, vector<vector<char>> &board){
	if(col == board.size()){
		if(row == board.size() - 1){
			return true;
		}
		row++;
		col = 0;
	}
	if(board[row][col] != '.'){
		return solve(row, col + 1, board);
	}
	for(int i = 1; i < 10; i++){
		if(isValid(i, row, col, board)){
			board[row][col] = to_string(i).back();
			if(solve(row, col + 1, board)){
				return true;
			}
		}
	}
	board[row][col] = '.';
	return false;
}
void sudokuSolver(vector<vector<char>> &sudoku) {
	solve(0, 0, sudoku);
}

Java

class Solution {
	boolean isValid(int value, int row, int col, char[][] board){
		boolean rowIsValid = true;
		boolean colIsValid = true;
        char digit = Character.forDigit(value, 10);
		for(int i = 0; i < 9; i++){
			if(digit == board[row][i]){
				rowIsValid = false;
				break;
			}
			if(digit == board[i][col]){
				colIsValid = false;
				break;
			}
		}
		if(rowIsValid == false || colIsValid == false){
			return false;
		}
		int subgridrow = row / 3;
		int subgridcol = col / 3;
		for(int i = 0; i < 3; i++){
			for(int j = 0; j < 3; j++){
				int currRow = subgridrow * 3 + i;
				int currCol = subgridcol * 3 + j;
				if(digit == board[currRow][currCol]){
					return false;
				}
			}
		}
		return true;
	}
	boolean solve(int row, int col, char[][] board){
		if(col == board.length){
			if(row == board.length - 1){
				return true;
			}
			row++;
			col = 0;
		}
		if(board[row][col] != '.'){
			return solve(row, col + 1, board);
		}
		for(int i = 1; i < 10; i++){
			if(isValid(i, row, col, board)){
				board[row][col] = Character.forDigit(i, 10);
				if(solve(row, col + 1, board)){
					return true;
				}
			}
		}
		board[row][col] = '.';
		return false;
	}
	void sudokuSolver(char[][] sudoku) {
	    solve(0, 0, sudoku);
	}
}