Topic describes

This is LeetCode 37. Solve sudoku.

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

A sudoku solution must follow the following rules:

  • The numbers 1-9 can appear only once in each line.
  • The numbers 1-9 May appear only once in each column.
  • The numbers 1-9 can occur only once in each 3×3 palace separated by a thick solid line.

Blank cells are represented by ‘.’.

A Sudoku.

The answers are marked in red.

Tip:

  • A given sudoku sequence contains only the numbers 1-9 and the characters ‘.’.
  • You can assume that a given sudoku has only one solution.
  • Sudoku is always 9×9.

Back in the solution

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 certain number will lead to failure in solving sudoku, then backtrack:

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)

review

Why is sudoku a classic problem? Why do sudoku questions often come up in job interviews?

Because sudoku is a problem that is solved according to “rules”. It’s very similar to our project.

And the solution method is very uniform, that is, DFS + backtracking is used for explosive search.

“Solving sudoku” is one of the hot questions that need to be mastered.

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.

  • This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign