Sudoku Solver — LeetCode #37

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

1. Each of the digits 1-9 must occur exactly once in each row.
2. Each of the digits 1-9 must occur exactly once in each column.
3. Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

The '.' character indicates empty cells.

Example 1:

Input: board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
Output: [["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
Explanation: The input board is shown above and the only valid solution is shown below:

Constraints:

• board.length == 9
• board[i].length == 9
• board[i][j] is a digit or '.'.
• It is guaranteed that the input board has only one solution.

Solutions:

Python

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        def is_valid(i, j, c):
            for k in range(9):
                if board[i][k] == c or board[k][j] == c:
                    return False
            for k in range(3):
                for l in range(3):
                    if board[(i // 3) * 3 + k][(j // 3) * 3 + l] == c:
                        return False
            return True

        def dfs(board):
            for i in range(9):
                for j in range(9):
                    if board[i][j] == '.':
                        for c in '123456789':
                            if is_valid(i, j, c):
                                board[i][j] = c
                                if dfs(board):
                                    return True
                                board[i][j] = '.'
                        return False
            return True

        dfs(board)

C#

public class Solution {
    public void SolveSudoku(char[][] board) {
        bool Dfs(int i, int j) {
            if (i == 9) {
                i = 0;
                if (++j == 9) {
                    return true;
                }
            }
            if (board[i][j] != '.') {
                return Dfs(i + 1, j);
            }
            for (int val = 1; val <= 9; ++val) {
                char c = (char)(val + '0');
                if (IsValid(i, j, c)) {
                    board[i][j] = c;
                    if (Dfs(i + 1, j)) {
                        return true;
                    }
                }
            }
            board[i][j] = '.';
            return false;
        }

        bool IsValid(int i, int j, char c) {
            for (int k = 0; k < 9; ++k) {
                if (board[i][k] == c || board[k][j] == c) {
                    return false;
                }
            }
            int boxRow = i - i % 3, boxColumn = j - j % 3;
            for (int k = 0; k < 3; ++k) {
                for (int l = 0; l < 3; ++l) {
                    if (board[boxRow + k][boxColumn + l] == c) {
                        return false;
                    }
                }
            }
            return true;
        }

        Dfs(0, 0);
    }
}

Java

class Solution {
    public void solveSudoku(char[][] board) {
        if (board == null || board.length == 0) return;
        solve(board);
    }
    
    private boolean solve(char[][] board) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == '.') {
                    for (char c = '1'; c <= '9'; c++) {
                        if (isValid(board, i, j, c)) {
                            board[i][j] = c;
                            if (solve(board)) return true;
                            else board[i][j] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
    
    private boolean isValid(char[][] board, int row, int col, char c) {
        for (int i = 0; i < 9; i++) {
            if (board[i][col] != '.' && board[i][col] == c) return false; // check row
            if (board[row][i] != '.' && board[row][i] == c) return false; // check column
            if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] != '.' && 
                board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) return false; // check 3*3 block
        }
        return true;
    }
}

Javascript

/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var solveSudoku = function(board) {
    function dfs(i, j) {
        if (i == 9) {
            i = 0;
            if (++j == 9) {
                return true;
            }
        }
        if (board[i][j] != '.') {
            return dfs(i + 1, j);
        }
        for (let val = 1; val <= 9; ++val) {
            let c = String(val);
            if (isValid(i, j, c)) {
                board[i][j] = c;
                if (dfs(i + 1, j)) {
                    return true;
                }
            }
        }
        board[i][j] = '.';
        return false;
    }

    function isValid(i, j, c) {
        for (let k = 0; k < 9; ++k) {
            if (board[i][k] == c || board[k][j] == c) {
                return false;
            }
        }
        let boxRow = i - i % 3, boxColumn = j - j % 3;
        for (let k = 0; k < 3; ++k) {
            for (let l = 0; l < 3; ++l) {
                if (board[boxRow + k][boxColumn + l] == c) {
                    return false;
                }
            }
        }
        return true;
    }

    dfs(0, 0);
};

Typescript

/**
 Do not return anything, modify board in-place instead.
 */
function solveSudoku(board: string[][]) {
    function dfs(i: number, j: number): boolean {
        if (i == 9) {
            i = 0;
            if (++j == 9) {
                return true;
            }
        }
        if (board[i][j] != '.') {
            return dfs(i + 1, j);
        }
        for (let val = 1; val <= 9; ++val) {
            let c = String(val);
            if (isValid(i, j, c)) {
                board[i][j] = c;
                if (dfs(i + 1, j)) {
                    return true;
                }
            }
        }
        board[i][j] = '.';
        return false;
    }

    function isValid(i: number, j: number, c: string): boolean {
        for (let k = 0; k < 9; ++k) {
            if (board[i][k] == c || board[k][j] == c) {
                return false;
            }
        }
        let boxRow = i - i % 3, boxColumn = j - j % 3;
        for (let k = 0; k < 3; ++k) {
            for (let l = 0; l < 3; ++l) {
                if (board[boxRow + k][boxColumn + l] == c) {
                    return false;
                }
            }
        }
        return true;
    }

    dfs(0, 0);
}

I hope this helps! Let me know if you have any questions. Don’t forget to follow and give some claps to support my content