Backtracking: N-Queen Problem and Sudoku (2024)

As a search algorithm, the Backtracking method can find a general algorithm for all or part of the solutions, and it is especially suitable for constraint satisfaction problems, such as N queens, solving Sudoku, and so on today.

Backtracking uses the idea of Trial And Error. It tries to solve a problem step by step. In the process of solving the problem step by step, when it can’t get an effective and correct solution by trying to find the existing step-by-step answer, it will cancel the calculation of the previous step or even the previous step, and then pass other possible steps. Step by step to try again to find the answer to the question.

The backtracking method is usually implemented by the simplest Recursive method. After repeating the above steps repeatedly, two situations may occur:

• Find a possible correct answer
• Declaring the question unanswered after trying every possible step-by-step approach

In the worst case, backtracking results in a computation of exponential time complexity.

The backtracking method is actually a kind of DFS (depth-first search algorithm). The difference is that the backtracking method has the ability to prune. The following two examples are used to analyze the backtracking algorithm in detail:

The N-queen problem is a further development based on the Eight Queens Puzzle. How can n queens be placed on an n*n chessboard so that no queen can directly capture other queens? To achieve this, no two queens can be on the same horizontal, vertical, or diagonal line. The figure below shows one of the solutions to the Eight Queens Puzzle:

Here’s an analysis of the problem:

Each position on the board contains two states: with a queen and without a queen. Listing all combinations without considering constraints, we will obtain a binary tree of depth N * N.

The diagram above depicts the possibilities of the top two positions on the board.

The easiest way is to exhaustively enumerate all possibilities, and then filter out the matching solutions. This binary tree can be traversed by the DFS algorithm, and there will be two N * N power possibilities for an N * N chessboard, which is obviously unacceptable.

But we can prune through rules. The rules that can be used are as follows:

• A total of N queens need to be placed
• There can only be one queen per row
• There can only be one queen per column
• There can only be one queen per slash

With the above four conditions, we can subtract most of the paths.

Now, go back to the backtracking method to look at this question. The backtracking method uses the idea of ​​trial and error to solve the problem step by step.

We can first assume that the queen is placed in the first position, and then according to the rules, find the second legal position and then place the second one. If a suitable position cannot be found, it means that the path is wrong, backtracking to the previous position to continue.

One of the characteristics of backtracking is that it uses arrays or other data structures to store traversal information, thereby skipping illegal paths.
This question uses three arrays to store the column, the upper left to the lower right hypotenuse, and the upper right to the seated hypotenuse of the queen placement data.

Since there can only be one queen per row, we traverse row by row, trying to place queens in every position on the current row. Then skip to the next line to continue.

• Time complexity: O(N!): The first queen has N placements, the second queen must not be in the same column as the first as well as at an oblique angle, so the second queen has N-1 possibilities, and so on, with a time complexity of O(N!).
• Spatial Complexity: O(N): Need to use arrays to save information.

The Sudoku game is the one we commonly see solving sudoku.

• The numbers 1–9 can only appear once in each row.
• Numbers 1–9 can only appear once in each column.
• Numbers 1–9 can only appear once in each 3x3 box separated by a thick solid line.

The idea is the same as for the N queens. Traverse all the spaces, place the 1–9 arrays one by one in the spaces, use the rules to determine if they are legal, and finally find the solution.

Here again, three arrays are defined to hold the traversed data: each row, each column, and each 3x3 cell.

Alternatively, if Sn represents the nth 3x3 cell, then Sn = (row / 3) * 3 + column / 3.

• Time Complexity

The input for this problem is a fixed nine-box grid, so it is straightforward to count the actual number of times.

The first line has no more than nine spaces to be filled with numbers, and since this cannot be repeated, there are 9! ways to do this, and there are nine lines in total, so it takes at most (9!)⁹ times.

• Space complexity

We have defined three arrays, each with 81 elements, for a total of 3x81=243 elements.

I have put the above code on GitHub, and there is a lot of other data structure- and algorithm-related code in there if you need it:

https://github.com/0xZhangKe/Algorithms/tree/master/src/com/zhangke/algorithms/leetcode