跳至主要內容

回溯算法最佳实践：解数独

labuladong原创回溯算法设计约 3816 字

37. 解数独 https://leetcode.cn/problems/sudoku-solver

37. Sudoku Solver https://leetcode.com/problems/sudoku-solver

Info

已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCodeDifficulty
37. Sudoku Solver🔴

Prerequisites

Before reading this article, you should learn:

People often use backtracking algorithms to discuss the Eight Queens Problem and Sudoku. Today, we will explain how to use backtracking to solve the Sudoku problem through practical and interesting examples.

I. Intuitive Understanding

Honestly, when I was a kid, I tried playing Sudoku games, but I never completed one. Solving Sudoku requires techniques. I remember some professional Sudoku game software that would teach you these techniques, but in my opinion, they were too complicated, and I had no interest in learning them.

However, since I learned algorithms, no Sudoku puzzle is too difficult for me. Here's an example of solving Sudoku using a program:

This is a Sudoku game on an Android phone. I used a script engine called Auto.js, combined with a backtracking algorithm, to automatically fill in the numbers, and the algorithm recorded the number of executions.

You can observe that the first two attempts executed over 10,000 times, while the last one only took about 100 executions to find the solution. This shows that for different board states, the time taken by the backtracking algorithm to find the solution varies.

So, how does a computer solve the Sudoku problem? It's actually very simple: brute force. Look at this brute force process, can you visualize the decision tree in your mind?

The core idea of the algorithm is very simple: for each empty cell, try numbers 1 to 9. If an invalid number is encountered (a number that already exists in the same row, column, or 3x3 region), skip it. If a valid number is found, continue to the next empty cell.

For Sudoku games, there might be a common misconception: we subconsciously think that fewer given numbers make the puzzle harder.

This might be true for humans, but for computers, fewer given numbers mean fewer steps to brute force, and thus a faster solution. We'll discuss why this is the case when we delve into the code implementation later.

The previous GIF was for the last level, level 70. The image below is for level 52, which has more numbers and seems easier, but let's look at the algorithm's execution process:

You can see that the algorithm struggled to make progress in the first two rows. Due to time constraints, I didn't continue recording, but in fact, the number of brute force attempts for this board state is about 10 times that of the previous one.

Getting back on track, let's now discuss how to use algorithms to solve Sudoku problems, and I'll also explain how I visualized this solving process.

II. Code Implementation

First, we don't need to worry about the game's UI; let's focus solely on the backtracking algorithm. LeetCode problem #37 "Sudoku Solver" is exactly this issue. The algorithm function signature is as follows:

java 🟢
void solveSudoku(char[][] board);

The input is a 9x9 chessboard where empty cells are represented by the dot character .. The algorithm needs to modify the board in place, filling the empty cells with numbers to obtain a valid solution.

Everyone is likely familiar with the requirements of Sudoku: no identical numbers can appear in any row, column, or 3x3 subgrid. So, we can directly apply the backtracking framework to solve it.

Recalling the GIF image, our approach to solving Sudoku is straightforward and brute-force: we exhaustively try all possible numbers for each cell. For each position, how should we enumerate the possibilities? How many choices are there?

It's simple: the choices are from 1 to 9. Just try them all:

java 🟢
// try to enumerate board[i][j]
void backtrack(char[][] board, int i, int j) {
    int m = 9, n = 9;
    for (char ch = '1'; ch <= '9'; ch++) {
        // make a choice
        board[i][j] = ch;
        // continue to enumerate the next
        backtrack(board, i, j + 1);
        // undo the choice
        board[i][j] = '.';
    }
}

Hmm, let's refine this further. It's not like we can use any number from 1 to 9, right? Some numbers don't meet the valid Sudoku conditions. Also, currently, we're just incrementing j. What if j reaches the last column? What should we do then?

It's quite simple. When j exceeds the last index of a row, we switch to incrementing i to start exhaustively checking the next row. Additionally, we add a condition to skip numbers that don't meet the requirements before we start the exhaustive search:

java 🟢
class Solution {
    public void backtrack(char[][] board, int i, int j) {
        int m = 9, n = 9;
        if (j == n) {
            // if we've exhausted the last column, move to the next row and start over.
            backtrack(board, i + 1, 0);
            return;
        }
        
        // if the current position is a preset number, we don't need to worry about it.
        if (board[i][j] != '.') {
            backtrack(board, i, j + 1);
            return;
        } 

        for (char ch = '1'; ch <= '9'; ch++) {
            // if we encounter an invalid number, skip it.
            if (!isValid(board, i, j, ch))
                continue;
            
            board[i][j] = ch;
            backtrack(board, i, j + 1);
            board[i][j] = '.';
        }
    }

    // determine if n can be placed in board[i][j]
    boolean isValid(char[][] board, int r, int c, char n) {
        for (int i = 0; i < 9; i++) {
            // check if there is a duplicate in the row
            if (board[r][i] == n) return false;
            // check if there is a duplicate in the column
            if (board[i][c] == n) return false;
            // check if there is a duplicate in the 3x3 box
            if (board[(r/3)*3 + i/3][(c/3)*3 + i%3] == n)
                return false;
        }
        return true;
    }
}

Well, we're almost there. There's just one last issue: this algorithm doesn't have a base case, so it will never stop recursing. This is easy to fix. When should the recursion end? Obviously, when r == m, it means we've exhausted the last row and completed all the possibilities, which is our base case.

Additionally, as mentioned earlier, to reduce complexity, we can make the backtrack function return a boolean value. If a feasible solution is found, it returns true, which stops further recursion. Finding just one feasible solution is also the intent of the problem.

The final code is modified as follows:

java 🟢
class Solution {
    public void solveSudoku(char[][] board) {
        backtrack(board, 0, 0);
    }

    boolean backtrack(char[][] board, int i, int j) {
        int m = 9, n = 9;
        if (j == n) {
            // if we have exhausted the last column, move to the next row and start over.
            return backtrack(board, i + 1, 0);
        }
        if (i == m) {
            // find a feasible solution, trigger the base case
            return true;
        }

        if (board[i][j] != '.') {
            // if there is a preset number, we don't need to enumerate it
            return backtrack(board, i, j + 1);
        } 

        for (char ch = '1'; ch <= '9'; ch++) {
            // if we encounter an invalid number, skip it
            if (!isValid(board, i, j, ch))
                continue;
            
            board[i][j] = ch;
            // if a feasible solution is found, end immediately
            if (backtrack(board, i, j + 1)) {
                return true;
            }
            board[i][j] = '.';
        }
        // after enumerating 1 to 9, still no feasible solution is found, this path is blocked
        return false;
    }

    boolean isValid(char[][] board, int r, int c, char n) {
        for (int i = 0; i < 9; i++) {
            // check if there is a duplicate in the row
            if (board[r][i] == n) return false;
            // check if there is a duplicate in the column
            if (board[i][c] == n) return false;
            // check if there is a duplicate in the 3 x 3 box
            if (board[(r/3)*3 + i/3][(c/3)*3 + i%3] == n)
                return false;
        }
        return true;
    }
}

Now, let's answer the previous questions: Why does the number of algorithm executions vary sometimes? Why does a computer find answers faster when there are fewer given numbers?

We have implemented the algorithm once and understand its principles. Backtracking starts from 1 and exhaustively tries each cell. As soon as a feasible solution is found, it stops further recursive attempts. Therefore, the number of attempts to find a solution by brute force is highly dependent on the randomly generated board, which is unpredictable.

You might ask, if the number of executions is unpredictable, what is the time complexity of this algorithm?

For such time complexity calculations, we can only provide the worst-case scenario, which is O(9^M), where M is the number of empty cells in the board. Think about it: for each empty cell, we try 9 numbers, resulting in exponential growth.

This complexity is very high, but upon closer inspection, we realize that we don't actually try 9 numbers for every empty cell. Some numbers are skipped, and some are not even tried because we stop as soon as we find a feasible solution, without expanding further recursive calls.

The O(9^M) complexity actually represents complete exhaustion, or the time complexity to find all feasible solutions.

If there are fewer given numbers, it means there are fewer constraints. For a computer using an exhaustive strategy, it is easier to proceed without having to backtrack frequently. Therefore, if we only need to find one feasible solution, the exhaustive process can be faster in this case.

With this, the backtracking algorithm is complete. You can use the above code to pass LeetCode's judging system. Next, let's briefly discuss how I visualized this backtracking process.

III. Algorithm Visualization

The core of letting the algorithm play the game for me is the algorithm itself. If you understand this algorithm, the rest is just using the Android script engine Auto.js to call APIs and control the phone. I have placed the tools in the background, and you can download them shortly.

To explain the idea simply in pseudocode, I can write two functions:

void setNum(Button b, char n) {
    // Input a cell, set the cell to the number n
}

void cancelNum(Button b) {
    // Input a cell, cancel the number on the cell
}

The core framework of the backtracking algorithm is as follows. By adding the corresponding operations at the appropriate positions in the framework, you can fully demonstrate the process of making and undoing choices in the algorithm. This might be the charm of using a systematic framework:

for (char ch = '1'; ch <= '9'; ch++) {
    Button b = new Button(r, c);
    // make a choice
    setNum(b, ch);
    board[i][j] = ch;
    // continue to enumerate the next
    backtrack(board, i, j + 1);
    // cancel the choice
    cancelNum(b);
    board[i][j] = '.';
}

The above approach can simulate the exhaustive process of the algorithm:

上次编辑于: