This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

This is LeetCode 37. Solve sudoku, difficulty is difficult.

Tag: “Backtracking algorithm”, “DFS”, “Sudoku Problem”

Write a program to solve a sudoku problem by filling in the blanks.

The solution of sudoku must follow the following rules:

  1. The numbers 1-9 can appear only once in each line.
  2. The numbers 1-9 May appear only once in each column.
  3. The numbers 1-9 can occur only once in each 3×3 palace separated by a thick solid line. (See sample diagram)

Numbers have been filled in the blank space of sudoku, and the blank space is represented by ‘.’.

Example:

Input: board = [["5","3",".",".","7",".",".",".","."], ["6",".",".","1","9","5",".",".","."], [". ", "9", "eight" and ". ", ""," ", ""," 6 ", ""], [" 8", ""," ", ""," 6 ", ""," ", ""," 3 "], [" 4 ", ""," ", "eight" and ". ", "3", ""," ", "1"]. [" 7 ", ". ", ""," ", "2", ""," ", ""," 6 "], [". ", "6", ""," ", ""," ", "2", "eight", ""], [".", ""," ", "4", "1", "9", ""," ", "5"]. [". ", ". ", ""," ", "eight" and ". ", ""," 7 ", "9"]] output: [[" 5 ", "3", "4", "6", 7 ", "eight" and "9", "1", "2"], [" 6 ", "7", "2", "1", "9", "5", "3", "4", "eight"], [" 1 ", "9", "eight", "3", "4", "2", "5", "6", "7"]. [" 8 ", "5", "9", "7", "6", "1", "4", "2", "3"], [" 4 ", "2", "6", "eight" and "5", "3", "7", "9", "1"], [" 7 ", "1", "3", "9", "2", "4", "eight" and "5", "6"]. [" 9 ", "6", "1", "5", "3", "7", "2", "eight", "4"], [" 2 ", "eight", "7", "4", "1", "9", "6", "3", "5"], [" 3 ", "4", "5", "2", "eight" and "6", "1", "7", "9"]] : The input sudoku is shown above, and the only valid solution is as follows:Copy the code

Tip:

  • board.length == 9
  • board[i].length == 9
  • Board [I][j] is a digit or ‘.’
  • The problem data guarantees that the input sudoku has only one solution

Back in the solution

Same as queen N, is a backtracking solution naked problem.

The previous question “36. Valid Sudoku (medium)” asks us to determine whether a given Borad is valid sudoku.

This problem asks us to solve sudoku for a given board. Since the board is always 9*9, we can use backtracking algorithm to do it.

This kind of questions, like QUEEN N, belong to the classical backtracking algorithm bare questions.

Such questions have an obvious feature that the data range is not very large. For example, the range of this question is limited to 9*9, while the N of queen N generally does not exceed 13.

Fill in each position where a number needs to be filled in. If it is found that filling in a number will lead to failure in solving sudoku, it will be backtracked.

Code:

class Solution {
    boolean[][] row = new boolean[9] [9];
    boolean[][] col = new boolean[9] [9];
    boolean[][][] cell = new boolean[3] [3] [9];
    public void solveSudoku(char[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if(board[i][j] ! ='. ') {
                    int t = board[i][j] - '1';
                    row[i][t] = col[j][t] = cell[i / 3][j / 3][t] = true;
                }
            }
        }
        dfs(board, 0.0);
    }
    boolean dfs(char[][] board, int x, int y) {
        if (y == 9) return dfs(board, x + 1.0);
        if (x == 9) return true;
        if(board[x][y] ! ='. ') return dfs(board, x, y + 1);
        for (int i = 0; i < 9; i++) {
            if(! row[x][i] && ! col[y][i] && ! cell[x /3][y / 3][i]) {
                board[x][y] = (char)(i + '1');
                row[x][i] = col[y][i] = cell[x / 3][y / 3][i] = true;
                if (dfs(board, x, y + 1)) {
                    break;
                } else {
                    board[x][y] = '. ';
                    row[x][i] = col[y][i] = cell[x / 3][y / 3][i] = false; }}}returnboard[x][y] ! ='. '; }}Copy the code
  • Time complexity: fixed9 * 9(In the extreme case, if our board is empty at the beginning, every cell should be enumerated. Each cell could be enumerated from 1 to 9, so the enumeration count is 999 = 729), that is, complexity does not vary with data. Complexity of
    O ( 1 ) O(1)
  • Space complexity: fixed9 * 9Complexity does not change with the data. Complexity of
    O ( 1 ) O(1)

The last

This is the 37th article in our “Brush through LeetCode” series, which started on 2021/01/01. As of the start date, there are 1916 questions in LeetCode, some of which have lock questions. We will finish all the questions without lock first.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour…

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.