This is the ninth day of my participation in the August More text Challenge. For details, see: August More Text Challenge

Hi, today we’re going to look at backtracking algorithms.

Before we get started, let’s review the greedy algorithm. For those of you who are not familiar with this article what did we learn from Huffman coding? .

Greedy algorithm can only according to the current state, choose the optimal way, to the next step, just like people’s life, can only choose a fork in the road under the current conditions of the optimal way to go, the past is gone, can not go back, only a way to black. And backtracking algorithm, can have the chance to start again, such as choosing a road, found that the road is not suitable for them, and then back to the fork in the road, to choose again. This is the idea of backtracking (as in being able to travel through time).

Backtracking algorithms are essentially enumerations, where we enumerate all the solutions, and then we find the solution that satisfies our expectations. In order to enumerate all possible solutions regularly and avoid omissions and repetition, we divide the problem solving process into several stages. At each stage, we will face a fork in the road. We first choose a road at will. When we find that the road is not working (it does not meet the expected solution), we will go back to the last fork in the road and choose another way to continue to go.

The theory is too abstract, so let’s take a classic example – the eight Queens problem – to get a deeper understanding of the idea of backdating. First let’s look at the title:

We have an 8×8 board, and we want to put eight pieces (queens) in it, and each piece cannot have another piece in the row, column, or diagonal. As shown in the figure below: The circle in the figure represents the queen, obviously the following placement method does not meet the conditions.

The eight Queens problem is expected to find all the ways to place the pieces that meet this requirement. The way to think about it is, we divide the problem into eight stages, and we place the eight pieces in the first row, the second row… All the way to the last row. During the placement process, we constantly check whether the current placement method meets the requirements. If so, jump to the next line to continue to place pieces; If that doesn’t work, try another placement and try again. Let’s take a look at how the code implements this.

class Cal8Queens: result=[0 for i in range(8)] count=0 def findResult(self,row): if row==8: Self.printresult (self.result) return for col in range(8): Self.findresult (row+1) def isResult(self,row,col): self.findresult (row+1) def isResult(self,row,col): Leftup =col-1 rightup=col+1 for I in range(row-1,-1,-1): If self.result[I]==leftup: return False if rightup<8: If self.result[I]==rightup: return False leftup=leftup-1 rightup=rightup+1 return True def printResult(self,result): self.count=self.count+1 for row in range(8): for col in range(8): if result[row]==col: print("Q",end=" ") else: print("*",end=" ") print() print("===============") print() cal=Cal8Queens() cal.findResult(0) print(cal.count)Copy the code

Although the principles of backtracking algorithms are well understood, they can solve many problems at the time. For example, depth first search, 0-1 backpack problem, etc., if you want to fully master, still need a lot of practice.

That’s all for today’s share, more hardcore knowledge, please follow.