Leetcode 37. Sudoku Solver

Problem Explanation

In the game of Sudoku, you are given a partially filled 9x9 grid, and the goal is to fill it in a way such that each row, column, and 3x3 box contains the digits 1-9 each digit exactly once. In this problem, we are required to write a program to solve a given Sudoku puzzle we receive as an input.

Example:

Let's take an example to demonstrate the problem.

Input Sudoku Grid:

1[
2      ['5','3','.','.','7','.','.','.','.'],
3      ['6','.','.','1','9','5','.','.','.'],
4      ['.','9','8','.','.','.','.','6','.'],
5      ['8','.','.','.','6','.','.','.','3'],
6      ['4','.','.','8','.','3','.','.','1'],
7      ['7','.','.','.','2','.','.','.','6'],
8      ['.','6','.','.','.','.','2','8','.'],
9      ['.','.','.','4','1','9','.','.','5'],
10      ['.','.','.','.','8','.','.','7','9']
11]

Output:

1[
2    ['5','3','4','6','7','8','9','1','2'],
3    ['6','7','2','1','9','5','3','4','8'],
4    ['1','9','8','3','4','2','5','6','7'],
5    ['8','5','9','7','6','1','4','2','3'],
6    ['4','2','6','8','5','3','7','9','1'],
7    ['7','1','3','9','2','4','8','5','6'],
8    ['9','6','1','5','3','7','2','8','4'],
9    ['2','8','7','4','1','9','6','3','5'],
10    ['3','4','5','2','8','6','1','7','9']
11]

In the above example, the first grid is the given Sudoku grid where '.' represents empty cells. We fill in the empty cells with numbers from 1-9 following the rules mentioned. The fully filled grid becomes the output.

Solution Approach

We will use backtracking to solve this Sudoku problem. The idea is simple:

11. Try every digit for each empty cell.
22. When trying a digit for a cell, check if it is a valid choice. Check the row, column and 3x3 box of the cell to see if the same digit already exists or not. If it does not, then it is a valid choice, else not.
33. Recursively try to fill the next empty cell. If no valid choices exist for a cell, then backtrack and change the previous cells. This is the core concept of backtracking.

Python Solution

The following solution is written in Python:

1
2python
3class Solution:
4    def solveSudoku(self, board):
5        self. board = board
6        self.solve()
7        
8    def solve(self):
9        for i in range(9):
10            for j in range(9):
11                if self.board[i][j] == '.':
12                    for c in '123456789':
13                        if self.isValid(i, j, c):
14                            self.board[i][j] = c
15                            if self.solve():
16                                return True
17                            self.board[i][j] = '.' 
18                    return False
19        return True
20
21    def isValid(self, row, col, c):
22        for i in range(9):
23            if self.board[i][col] == c: 
24                return False
25            if self.board[row][i] == c:
26                return False
27            if self.board[3*(row//3)+i//3][3*(col//3)+i%3] == c: 
28                return False
29        return True

Explanation of the Python solution:

We first provide the solveSudoku function with the Sudoku board as its parameter and then call the helper function solve to start filling the cells.

In the solve function, we use a nested for loop to iterate over each cell. If a cell is empty (denoted by '.'), we try placing every possible digit from 1-9 ('123456789') in that cell. We use the helper function isValid to check if placing the digit in the current cell is valid or not.

If the move is valid, we place the digit and then recursively call solve to fill in the next cells. If a valid digit cannot be found for a forthcoming cell, the solve function will return False, and the previous cell's value will be reset back to '.', allowing us to try the next possible digit.

If all digits have been tried and none works, it means the previous cell's value is wrong (because it leads to an impossibility for the next cells), so we then move to the previous cell (backtrack) and try the next digit. This back and forth continues until a valid configuration is found for all cells.

The isValid function is used to check if the current cell's value is valid according to the Sudoku rules. We use three checks for each row, column, and the current 3x3 box to ensure no duplicate exists. If a duplicate is found, we return False; else, we return True, meaning the current choice of digit for the cell is valid.

By using the backtracking approach in this way, we can efficiently solve the Sudoku puzzle problem.## JavaScript Solution

Here's how you would solve the Sudoku puzzle problem using JavaScript:

1
2javascript
3class Solution {
4    constructor(board) {
5        this.board = board;
6        this.solve();
7    }
8
9    solve() {
10        for (let i = 0; i < 9; i++) {
11            for (let j = 0; j < 9; j++) {
12                if (this.board[i][j] === ".") {
13                    for (let c = 1; c <= 9; c++) {
14                        if (this.isValid(i, j, c)) {
15                            this.board[i][j] = `${c}`;
16                            if (this.solve()) return true;
17                            this.board[i][j] = ".";
18                        }
19                    }
20                    return false;
21                }
22            }
23        }
24        return true;
25    }
26
27    isValid(row, col, c) {
28        for (let i = 0; i < 9; i++) {
29            if (this.board[i][col] === `${c}`) return false;
30            if (this.board[row][i] === `${c}`) return false;
31            if (
32                this.board[Math.floor( row / 3 ) * 3 + Math.floor( i / 3 )][Math.floor( col / 3 ) * 3 + i % 3] === `${c}`
33            )
34                return false;
35        }
36        return true;
37    }
38}
39
40let sudoku = new Solution(board);
41console.log(sudoku.board);

In JavaScript, we create the Solution class with board as an input and call the solve function inside the constructor. The logic for solve and isValid function is almost similar to that of Python.

To translate the Python solution into JavaScript solution involves mainly using JavaScript syntax and string interpolation where Python uses string concatenation. The rest of the logic remains consistent across the two languages.

Java Solution

Following is a similar solution in Java:

1
2java
3class Solution {
4    private char[][] board;
5
6    public void solveSudoku(char[][] board) {
7        this.board = board;
8        if(solve()) {
9            for(int i = 0; i<9; i++) {
10                for(int j = 0; j<9; j++) {
11                    System.out.print(board[i][j]+" ");
12                }
13                System.out.println("");
14            }
15        }
16    }
17    
18    public boolean solve() {
19        for(int i = 0; i<9; i++) {
20            for(int j = 0; j<9; j++) {
21                if(board[i][j] == '.') {
22                    for(char c='1'; c<='9'; c++) {
23                        if(isValid(i, j, c)) {
24                            board[i][j] = c;
25                            if(solve()) 
26                                return true;
27                            else              
28                                board[i][j] = '.'; 
29                        }
30                    }
31                    return false;
32                }
33            }
34        }
35        return true;
36    }
37    
38    public boolean isValid(int row, int col, char c) {
39        for(int i = 0; i<9; i++) {
40            if(board[i][col] == c) 
41                return false;
42            if(board[row][i] == c)
43                return false;
44            if(board[3*(row/3)+i/3][3*(col/3)+i%3] == c)
45                return false;
46        }
47        return true;
48    }
49}

The structure of this Java program is similar to those of the previous Python and JavaScript scripts.

Conclusion:

Through implementing this problem across three programming languages (Python, JavaScript, and Java), we're able to understand how the process of Backtracking can be used as an effective tool to solve complex puzzle problems such as Sudoku. Furthermore, it is also a good exercise in learning how to translate the same logic-across multiple programming languages.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫