37. Sudoku Solver

Sudoku Solver

Problem Description

Write a program to solve a Sudoku puzzle by filling in 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.

Approach) DFS Backtracking

Idea:

Create 3 tracking arrays:

•   1 - 9 occurs once in whole row, whole col, whole box.
•   [ith row][number] [ith col][number] [ith box][number]
•   ex: [ith row][N] = 1 means ith row already use number N

DFS/Backtracking

•   Travese the board from left to right, row by row
•   Try to fill 1-9, success return,
• if not success, recover data and try next element

/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var solveSudoku = function(board) {
    // 1 - 9 occur once in whole row, whole col, whole box
    // [ith row][number] [ith col][number] [ith box][number]
    // ex: [ith row][N] = 1 means ith row already use number N
    let rows = Array.from(new Array(9), () => new Array(10).fill(0));
    let cols = Array.from(new Array(9), () => new Array(10).fill(0));
    let boxes = Array.from(new Array(9), () => new Array(10).fill(0));
    
    for (let i = 0; i < 9; i++) {
        for (let j = 0; j < 9; j++) {
            const c = board[i][j];
            if (c !== '.') {
                let num = parseInt(c);
                let bx = Math.floor(j / 3);
                let by = Math.floor(i / 3);
                rows[i][num] = 1;
                cols[j][num] = 1;
                boxes[by * 3 + bx][num] = 1;
            }
        }
    }
    dfs(board, 0, 0, rows, cols, boxes);
};

function dfs(board, x, y, rows, cols, boxes) {
    // exit recursion condition, reach to the end;
    if (y === 9) return true;
    
    // traverse from left to right, then next row
    let nextX = (x + 1) % 9;
    let nextY = nextX === 0 ? y + 1 : y;
    
    // already has number, DFS next element
    if (board[y][x] !== '.') return dfs(board, nextX, nextY, rows, cols, boxes);
    
    // fill number from 1 - 9
    for (let i = 1; i <= 9; i++) {
        let bx = Math.floor(x / 3);
        let by = Math.floor(y / 3);
        let box_index = by * 3 + bx;
        // if not breaking the following 3 rules
        if (!rows[y][i] && !cols[x][i] && !boxes[box_index][i]) {
            // modify, fill the number
            rows[y][i] = 1;
            cols[x][i] = 1;
            boxes[box_index][i] = 1;
            board[y][x] = i.toString();
            // Try to fill next element, if success return true, or recover
            if (dfs(board, nextX, nextY, rows, cols, boxes)) return true;
            // recover data
            board[y][x] = '.';
            boxes[box_index][i] = 0;
            cols[x][i] = 0;
            rows[y][i] = 0;
        }
    }
    return false;
}

Conclusion

That’s all folks! In this post, we solved LeetCode problem #37. Sudoku Solver

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!