After reading this article, you can go to Li Kou and take the following questions:

37. Solving Sudoku

-----------

The backtracking algorithm is often referred to as the eight queens problem and Sudoku problem. Let's talk about how to use backtracking algorithm to solve Sudoku problem through practical and interesting examples today.

1, Intuitive feeling

To be honest, I tried to play Sudoku when I was a child, but I never finished it once. There are skills to do Sudoku. I remember some professional Sudoku game software. They will teach you the skills of playing Sudoku. However, in my opinion, these skills are too complex and I am not interested in watching them at all.

But since I learned the algorithm, how difficult Sudoku problems can't stop me. The following is an example of Sudoku I completed by program:

PS: GIF may have a bug. If it is stuck, click open to view it, the same below. ​

This is a Sudoku game in Android mobile phone. I use a script engine called Auto.js and a backtracking algorithm to complete the filling automatically, and the algorithm records the execution times.

It can be observed that the first two times are executed more than 10000 times, and the last time is only executed more than 100 times, which means that the time for the backtracking algorithm to get the answer is different for different situations.

So how does the computer solve the Sudoku problem? In fact, it's very simple. It's exhaustive. I've visualized the solution process below:

The core idea of the algorithm is very, very simple. It is to enumerate 1 to 9 for each empty lattice. If you encounter illegal numbers (in the same row, column or 3) × If the same number exists in the area of 3), skip. If a valid number is found, continue to enumerate the next empty grid.

For Sudoku games, perhaps we will have another misunderstanding: subconsciously think that if the given number is less, the more difficult the situation will be.

This conclusion should be OK for people, but for computers, the fewer numbers given, the fewer steps enumerated, and the faster the answer can be obtained. As for why, we will talk about code implementation later.

The last GIF is level 70, and the following figure is level 52. There are many numbers, which seems not difficult, but let's take a look at the process of algorithm execution:

It can be seen that the algorithm has been exhausted for half a day in the first two lines, and I didn't continue recording due to time reasons. In fact, the number of times of this situation is about 10 times that of the previous situation.

To get back to business, let's specifically discuss how to use algorithms to solve Sudoku problems. By the way, how do I visualize this solution process.

PS: I have carefully written more than 100 original articles. I have brushed 200 Daoli buttons with my hands, all of which are published in labuladong's algorithm , continuously updated. It is suggested to collect, brush the questions in the order of my articles, master various algorithm routines, and then throw them into the sea of questions, which is like a fish in water.

2, Code implementation

First of all, we don't care about the UI of the game. First, we simply solve the backtracking algorithm. LeetCode question 37 is to solve the Sudoku problem. The signature of the algorithm function is as follows:

void solveSudoku(char[][] board);

The input is a 9x9 chessboard, and the blank grid is represented by a dot character. The algorithm needs to modify the chessboard in place, fill the blank grid with numbers, and get a feasible solution.

As for the requirements of Sudoku, everyone must be very familiar with each row, column and each 3 × No small square of 3 can have the same number. Then, we can solve it directly by using a backtracking framework.

Above Detailed explanation of backtracking algorithm , I have written the routine framework of backtracking algorithm. If I haven't read that article, I suggest you take a look first.

Recalling the GIF picture just now, our idea of solving Sudoku is very simple and rough, that is to enumerate all possible numbers in each grid. For each position, how should we enumerate? How many choices are there? It's very simple. From 1 to 9 is the choice. Just try it all:

// Make an exhaustive attempt on 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;
        // Go on to the next one
        backtrack(board, i, j + 1);
        // Undo selection
        board[i][j] = '.';
    }
}

emmm, if you continue to refine, you can't get from 1 to 9. Don't some numbers meet the legal conditions of Sudoku? And now I just add one to j. what if j is added to the last column?

Very simply, when j reaches the last index of each row, increase i to start enumerating the next row, and add a judgment before enumerating to skip the numbers that do not meet the conditions:

void backtrack(char[][] board, int i, int j) {
    int m = 9, n = 9;
    if (j == n) {
        // If you are exhausted to the last column, change to the next line and start again.
        backtrack(board, i + 1, 0);
        return;
    }
    
    // If the position is a preset number, we don't have to worry
    if (board[i][j] != '.') {
        backtrack(board, i, j + 1);
        return;
    } 

    for (char ch = '1'; ch <= '9'; ch++) {
        // If you encounter illegal numbers, skip
        if (!isValid(board, i, j, ch))
            continue;
        
        board[i][j] = ch;
        backtrack(board, i, j + 1);
        board[i][j] = '.';
    }
}

// Judge whether board[i][j] can be filled with n
boolean isValid(char[][] board, int r, int c, char n) {
    for (int i = 0; i < 9; i++) {
        // Determine whether there are duplicates in the row
        if (board[r][i] == n) return false;
        // Determine whether there are duplicates in the column
        if (board[i][c] == n) return false;
        // Determine whether the 3 x 3 box is duplicated
        if (board[(r/3)*3 + i/3][(c/3)*3 + i%3] == n)
            return false;
    }
    return true;
}

emmm, it's almost now. There's one last problem left: this algorithm has no base case and will never stop recursion. This is easy. When will the recursion end? Obviously, when r == m, it means that the last line has been exhausted and all the exhausts have been completed, which is base case.

In addition, as mentioned earlier, in order to reduce the complexity, we can make the return value of the backtrack function boolean, and return true if a feasible solution is found, so as to prevent subsequent recursion. Only finding a feasible solution is also the original intention of the problem.

The final code is modified as follows:

boolean backtrack(char[][] board, int i, int j) {
    int m = 9, n = 9;
    if (j == n) {
        // If you are exhausted to the last column, change to the next line and start again.
        return backtrack(board, i + 1, 0);
    }
    if (i == m) {
        // Find a feasible solution and trigger the base case
        return true;
    }

    if (board[i][j] != '.') {
        // If there are preset numbers, we don't have to enumerate them
        return backtrack(board, i, j + 1);
    } 

    for (char ch = '1'; ch <= '9'; ch++) {
        // If you encounter illegal numbers, skip
        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 1 ~ 9, there is still no feasible solution. This road is impassable
    return false;
}

boolean isValid(char[][] board, int r, int c, char n) {
    // See above
}

Now you can answer the previous question, why do algorithms sometimes execute more and sometimes less? Why is it that for a computer, the fewer certain numbers, the faster it can calculate the answer?

We have implemented the algorithm once and mastered its principle. Backtracking is to enumerate each lattice from 1. Finally, as long as we try to find a feasible solution, we will immediately stop the subsequent recursive enumeration. Therefore, the number of violent attempts has a lot to do with the randomly generated chessboard, which is uncertain.

So you may ask, since the number of runs is uncertain, what is the time complexity of this algorithm?

For the calculation of this time complexity, we can only give a worst-case, that is, O(9^M), where M is the number of empty lattices on the chessboard. If you want to enumerate 9 numbers for each empty grid, the result is exponential.

This complexity is very high, but after a little thinking, we can find that in fact, we do not really enumerate each space 9 times. Some numbers will be skipped, and some numbers are not exhaustive at all, because when we find a feasible solution, it ends immediately, and the subsequent recursion is not expanded.

The complexity of this O(9^M) is actually completely exhaustive, or the time complexity of finding all feasible solutions.

If the given number is less, it is equivalent to the given constraint conditions are less. For the exhaustive strategy of computer, it is easier to go on, and it is not easy to go back. Therefore, if only a feasible solution is found, the speed of exhaustive is faster in this case.

So far, the backtracking algorithm has been completed. You can use the above code to pass the problem judgment system of LeetCode. Let's briefly talk about how I visualize the backtracking process.

PS: I have carefully written more than 100 original articles. I have brushed 200 Daoli buttons with my hands, all of which are published in labuladong's algorithm , continuously updated. It is suggested to collect, brush the questions in the order of my articles, master various algorithm routines, and then throw them into the sea of questions, which is like a fish in water.

3, Algorithm visualization

The core of letting the algorithm help me play the game is the algorithm. If you understand the algorithm, the rest is to use the Android script engine Auto.js to call the API to operate the mobile phone. I put all the tools in the background and you can download them later.

Using pseudo code, I can write two functions:

void setNum(Button b, char n) {
    // Enter a square and set it to the number n
}

void cancelNum(Button b) {
    // Enter a square to undo the number on the square
}

The core framework of the backtracking algorithm is as follows. As long as the corresponding operation is added at the corresponding position of the framework, the process of selecting and canceling the selection of the algorithm can be fully displayed. Perhaps this is the charm of the routine framework:

for (char ch = '1'; ch <= '9'; ch++) {
    Button b = new Button(r, c);
    // Make a choice
    setNum(b, ch);
    board[i][j] = ch;
    // Go on to the next one
    backtrack(board, i, j + 1)
    // Undo selection
    cancelNum(b);
    board[i][j] = '.';
}

The above ideas can simulate the process of algorithm exhaustion:

＿＿＿＿＿＿＿＿＿＿＿＿＿

my Online ebook There are 100 original articles, hand-held brush 200 Daoli buckle topics, it is recommended to collect! Corresponding GitHub Algorithm warehouse Has obtained 70k star, welcome to Biao Xing!