# Backtracking: N-Queen Problem and Sudoku | by ZhangKe | Mar, 2022

## To solve a problem step by step

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.