[LeetCode] 37. Sudoku Solver

Posted on | In

Problem

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 the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

Empty cells are indicated by the character '.'.

37. Valid Sudoku A sudoku puzzle…

37. Valid Sudoku …and its solution numbers marked in red.

Note:

  • The given board contain only digits 1-9 and the character '.'.

  • You may assume that the given Sudoku puzzle will have a single unique solution.

  • The given board size is always 9x9.

Explanation

  1. Before we start, check if the board is valid. To solve this problem, We can use backtracking, and the base case is the row is greater than 9 (index 8).

  2. First, start from position row=0, col=0 and pass it to the helper function, we need to find out the empty cell we need to fill in. Then, loop from 1 to 9, pass it to the empty cell to check if the number is valid. If it is valid, then we start from the empty cell’s next position and recursivly call the helper function. If the next position is also valid, then we finish and return true. If the next position is not valid, we need to backtrack by resetting the cell to empty and iterate to the next number.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
    boolean isValid(char[][] board, int row, int col, int num) {
        char c = (char)(num+'0');
        for (int i = 0; i < 9; i++) {
            if (board[row][i] == c || board[i][col] == c) {
                return false;
            }
        }
        int rowOff = row/3 * 3;
        int colOff = col/3 * 3;
        for (int ro = rowOff; ro < rowOff+3; ro++) {
            for (int co = colOff; co < colOff+3; co++) {
                if (board[ro][co] == c) {
                    return false;
                }
            }
        }
        board[row][col] = c;
        return true;
    }
    boolean helper(char[][] board, int row, int col) {
        while (row < 9 && col < 9) {
            if (board[row][col] == '.') break;
            if (col == 8) {
                col = 0;
                row += 1;
            } else {
                col += 1;
            }
        }
        
        if (row > 8) return true;
        
        for (int i = 1; i <= 9; i++) {
            if (isValid(board, row, col, i)) {
                int nextRow = col == 8 ? row+1 : row;
                int nextCol = col == 8 ? 0 : col+1;
                if (helper(board, nextRow, nextCol)) {
                    return true;
                } else {
                    board[row][col] = '.';
                }
            }
        }
        return false;
    }
    public void solveSudoku(char[][] board) {
        if (board == null || board.length != 9 || board[0].length != 9) return;
        helper(board, 0, 0);
    }
}