This is the 10th day of my participation in the August More Text Challenge. For details, see:August is more challenging

If you want to keep writing, write a series. What can I write about? Program = algorithm + data structure, which shows the importance of algorithm. This series of old poems tries to explain the algorithm clearly in the simplest language, from shallow to deep, if you are interested, you can pay attention to the column.

The last article introduced the basic backtracking method, pruning. And then we did the whole permutation example. Now let’s dig a little deeper into how this algorithm should go deeper. Remember I gave you a homework assignment for the last article if you’re interested in doing it, because it’s a classic.

Title: five stars

Fill in the five star nodes: 1 to 12, excluding 7 and 11. We want the sum of the numbers on each line to be equal.

This is the right way to fill it out.

Please use your computer to search for all the possible forms. Note: the same method of filling after rotation or mirroring.

Please submit an integer representing the number of schemes and do not enter anything else.

This question needs to be deweighted, because it is a pentacle star * 5 (because each Angle can be rotated, so these can be assumed to be the same), and the mirror image * 2, so directly after the search /10 is the amount after the deweighting.

Then we’ll focus on the burst search.

#include <iostream> #include <cstdio> #include <cstdlib> using namespace std; int a[11]; // Int n; Int isUse[110]; / / record whether the number of used void DFS (int s) {if (s = = 11) {int f = a [2] [3] a + + a + a, [5]. [4] int b = a[1] + a[3] + a[6] + a[9]; int c = a[1] + a[4] + a[7] + a[10]; int d = a[2] + a[6] + a[8] + a[10]; int e = a[5] + a[7] + a[8] + a[9]; if(f==b && b==c && c==d && d==e){ n++; return ; } return ; } for(int i=1; i<=12; i++){ if(i==7||i==11||isUse[i]){ continue; } isUse[i] = 1; a[s] = i; dfs(s+1); isUse[i] = 0; } return ; } int main() { dfs(1); cout<<n/10; //5*2 return 0; }Copy the code

In general, it’s not too hard to get to the problem if you know what the algorithm is, you just plug it into the template. I’m going to fill in every number in the DFS, which is sort of like the full perscription, and then I’m going to add the pruning number here so that it doesn’t equal 7 and 11, or the number can’t be used. Use isUse to record whether the number has been used. isUse[i] = 1; IsUse [I] = 0; It’s not used. That’s what backtracking is all about.

This backtracking can be used in a number of ways, for example, in pathfinding algorithms, where you’re trying to figure out which direction the grid is going to go better.

More dry content, project source code, you can pay attention to the public number: like the code poem

Now that I’m in, it’s not easy to be original. Let’s go with a “like”.