# Algorithmic thinking -- backtracking algorithm

### Backtracking algorithm

Backtracking is actually a search attempt process similar to enumeration. It is mainly to find the solution of the problem in the search attempt process. When it is found that the solution conditions have not been met, it will "backtrack" and try other paths. Backtracking is a search method of selecting the best, which searches forward according to the conditions of selecting the best to achieve the goal. However, when a certain step is explored, it is found that the original choice is not optimal or fails to reach the goal, so it is necessary to go back one step and make a new choice. This technique is called backtracking method, and the point satisfying the backtracking condition is called "backtracking point".

After all, in fact, the backtracking algorithm is an N-tree's pre order traversal plus post order traversal.

```//Binary tree traversal framework
func traverse(root) {
if root is nil {
return
}
//Preamble traversal code
traverse(root.left)
//Middle order traversal code
traverse(root.right)
//Sequential traversal code

}

//N-tree traversal framework
func traverse(root) {
if root is nil {
return
}

for child := range root.children {
//Preamble traversal code
traverse(child)
//Sequential traversal code
}
}
```

### Backtracking framework

Backtracking algorithm is the traversal of N-tree, which is equal to the total number of currently available choices. At the same time, make the current choice at the location of the previous traversal (choose process), then start the recursion, and finally cancel the current choice at the location of the later traversal (choose process). The pseudo code is as follows:

```/**
* choiceList: Currently available selection list
* track : It can be understood as a decision path, that is, a series of choices have been made
* answer : Used to store the decision path that we meet the conditions
*/

if track is OK {
} else {
for choice as range choiceList {
// choose: select a choice to join the track
// Uncheck: undo the above selection from track
}
}
}
```

It can be seen that the core of the backtracking algorithm is actually the traversal of an N-tree. The backtracking algorithm is equivalent to a decision-making process, recursively traversing a decision tree, exhausting all decisions, and picking out the qualified decisions at the same time.

### An example

If you want to eat, but where do you want to eat? What do you want to eat? This is a decision-making issue. So how will computers choose? The way for computers to deal with problems is to exhaust. Here, computers will exhaust and compare all the decisions, and then choose an optimal strategy, such as: eat meal, take out, KFC, family bucket.

How to make the computer exhaust and compare all the decisions correctly is the design skill of backtracking algorithm. The core of backtracking algorithm is how to design the logic of choose and uncheck.

### Permutation problem The total permutation problem is a typical backtracking algorithm problem. Our idea is to fix the first number as 1, then arrange 2 and 3 in full; then fix the first number as 2, arrange 1 and 3 in full; then fix the first number as 3, arrange 1 and 2 in full. This is a decision-making process. It is transformed into a decision tree to represent: It can be found that each level down is to select a "choice" in the "selection list" to add "decision path", and then delete this choice from the "selection list" (to avoid repeated selection later); when a decision branch exploration is completed, we need to backtrack up, take the "choice" of the branch from the "decision list", and then take this "choice" Rejoin the selection list (for use by other decision branches).

The above is the process of choose and unchoose in the template. The choose process is to explore down and make a choice. The unchoose process is to backtrack up and undo the just choice. Now we can specify the template of backtracking algorithm for the problem of Full Permutation:

```/**
* choiceList: Selection list, currently available selection list
* track : Decision path, a series of choices have been made
* answer : Used to store the complete permutation
*/

if track is OK {
} else {
for choice as range choiceList {
// choose process
// Move choice out of choiceList
// unchoose process
// Move the choice out of the track
// Add the choice back to the choiceList
}
}
}
```

Here is the specific code (golang):

```func permute(nums []int) [][]int {
track := []int{}
ans := [][]int{}
backTrack(nums, &track, &ans)
return ans
}

func backTrack(nums []int, track *[]int, ans *[][]int) {
if len(*track) == len(nums) {
tmp := make([]int, len(*track))
copy(tmp, *track)
*ans = append(*ans, tmp)
} else {
for _, v := range nums {
if isIn(v, *track) {
continue
}
*track = append(*track, v)
backTrack(nums, track, ans)
*track = (*track)[:len(*track)-1]
}
}
}

func isIn(i int, arr []int) bool {
for _, v := range arr {
if v == i {
return true
}
}

return false
}
``` ### N-queens problem It is also the idea of backtracking. The code is as follows:

```func solveNQueens(n int) [][]string {
board := []string{}
ans := [][]string{}
initBoard(&board, n)
backTrack(0, n, &board, &ans)
return ans

}

//Initialize chessboard
func initBoard(board *[]string, n int) {
var s string
for i := 0; i < n; i++ {
s += "."
}
for i := 0; i < n; i++ {
*board = append(*board, s)
}
}

func backTrack(row int, n int, board *[]string, ans *[][]string) {
if row == len(*board) {
tmp := make([]string, len(*board))
copy(tmp, *board)
*ans = append(*ans, tmp)
} else {
for col := 0; col < n; col++ {
//If you choose this location, you will be attacked. Skip this location
if !isPlace(board, row, col, n) {
continue
}
//choose process
(*board)[row] = strRex((*board)[row], col, 'Q')
//Select next line
backTrack(row + 1, n, board, ans)
//unchoose process
(*board)[row] = strRex((*board)[row], col, '.')
}
}
}

func strRex(s string, i int, b byte) string {
bytes := []byte(s)
bytes[i] = b
s = string(bytes)
return s
}

//Judge whether board[row][col] can place Q
func isPlace(board *[]string, row, col, n int) bool {
//Check directly above
for i := 0; i < row; i++ {
if (*board)[i][col] == byte('Q') {
return false
}
}
//Check upper right skew
for i, j := row - 1, col + 1; i >= 0 && j < n; i, j = i-1, j+1 {
if (*board)[i][j] == byte('Q') {
return false
}
}
//Check upper left skew
for i, j := row - 1, col - 1; i >= 0 && j >= 0; i, j = i-1, j-1 {
if (*board)[i][j] == byte('Q') {
return false
}
}
//No need to check the bottom, because there is no queen under
return true
}
```

"Decision path": board. Every step of decision-making is every line of board. row variable records the step of current decision-making path.
"Selection list": for a given row (i.e. every step in the decision-making), each column may be placed with a "Q", which is all the choices. The for loop in the code is to exhaust the "selection list" to determine whether the queen can be placed.  ### summary

Review the algorithm framework of backtracking

``` func backtrack(choiceList, track, answer) {
if track is OK {  