This article is included in the official account bigsai, follow more dry goods and learning resources

preface

Speaking of the eight Queens problem, it is a classic backtracking algorithm class problem, alsomayIt’s the hardest problem most of us have ever had in a data structure or algorithm class…

Encountered for the first time when it should be a big or a sophomore this period, this time for what all puzzled, what all want to learn to find like what all can be difficult, eight queen also put at that time I stop in the outside, I remember very clearly was a sophomore at the beginning of our academic advisor to when the class meeting we talk about a word is very clear: “How could he possibly solve the code of the eight Queens without a serious learning algorithm?”

Indeed, at that time, I did not understand recursion, had never heard of backtracking, and did not even understand Java collections. There was no logic at all.

But today, I can kick the eight queens, with you two thousand silver, thirty beauty.

Dip a recursive

For recursive algorithms, I thinkRecursion is the key to data structure and algorithm, because many operations to learn later involve recursion, such as some operations of linked lists, tree traversal and some operations, graph DFS, quick sorting, merge sort and so on.

The essence of recursion is to achieve some operations with the help of the stack. The operations that can be completed by recursion can be completed by the stack, and the use of the stack can be well controlled and stopped, which is more efficient (recursion is a back and forth process that needs special judgment when it comes back).

Recursive implementation and stack implementation of the difference between the operation, recursive for us more concise clever, and with more will find a lot of problems on the processing of recursive thinking more inclined to the way of thinking, and stack is the old honest practical computer (data structure characteristics) thinking to think about the problem. You can see how binary trees are traversed recursively and non-recursively, and you can see the complexity.

In terms of the characteristics of recursive algorithms, the problems of recursive algorithms are all parent problems that can be transformed into sub-problems by using certain relations. The process of working backwards, usually with a single parameter representing the current level.

The main characteristics of recursion are as follows:

  • Call yourself
  • Recursion usually doesn’t care about the actual operation, just the relationship between the initial conditions and the changes in the upper and lower levels.
  • Recursive functions need to have a critical stop point, that is, recursion cannot continue indefinitely. Usually this point is a number that you have to go through.
  • Recursion can be replaced by a stack. Some recursions can be optimized. For example, the repetition can be reduced by using spatial memory records.

Generally, a process of recursive algorithm is roughly as follows:

Define recursive algorithm and parameters - stop recursive algorithm condition - (exists) other logic - Recursive call (parameters need to change) - (exists) other logicCopy the code

Data Structures and Algorithms – Recursive algorithms (from factorial to Fibonacci to Hannotta recursion diagrams), written really well!

Backtracking algorithm

After recursion, you probably understand that there is a way to do this, but you might feel that recursion alone and the eight Queens are still hard to relate to, yes, that’s right, so I’m going to talk about backtracking.

Here’s a little interlude. One of my roommates was talking about backtracking algorithm when we were chatting in the dormitory the day before yesterday. He said back to shuo algorithm, but we corrected it differently and said back to su(prime) algorithm. He actually misread it for four years… I don’t know if any of you have read it wrong.

Let’s get back to the point. In the algorithm world, there are five commonly used algorithms: greedy algorithm, divide-and-conquer algorithm, dynamic programming algorithm, backtracking algorithm, branch and bound algorithm. Our backtracking algorithm is one of the five, because backtracking algorithm can solve many practical problems. Although the complexity may not be too small in most cases, it can get a good result in most cases.

For the definition of backtracking, Baidu Baike defines it as follows:

Backtracking algorithm is actually a search attempt process similar to enumeration, which is mainly to find the solution of the problem in the search attempt process. When it is found that the solution condition is not met, it will “backtrack” back and try another path. Backtracking is a kind of optimal search method, which searches forward according to the optimal conditions to reach the target. However, when a certain step is explored, it is found that the original choice is not good or fails to reach the target, so it takes a step back to make a new choice. The technology of going back and going again when there is no way is called backtracking method, and the point in a certain state that meets the backtracking condition is called “backtracking point”. Backtracking can be used for many complex, large-scale problems, and has the good name of being a “general solution.”

The core of backtracking is exploration and recovery. This automated process is to use recursion to execute, modify the attempt before the recursive function is executed, recurse downward after satisfying the condition, and restore the value after testing. In this heuristic process we find one or all of the solutions we need. This is what we call violence.

What? Don’t understand? Okay, so I’m going to talk a little bit more about, you know depth first search, right? The backtracking algorithm is a special kind of DFS. The reason it’s called backtracking is because it’s a recursive process, so it’s like a heuristic. These algorithms usually pair one or more Boolean arrays to mark the points used on the heuristic.

For example, we know that backtracking algorithms are used to find the order of all the numbers. Let’s analyze one of these orders. Let’s say the sequence 6, 8, 9, we use to figure out the order.

For blocks of code, this might be easy to implement:

import java.util.Arrays;

public class test {
    public static void main(String[] args) {
        int arr[]={6.8.9};// An array to arrange and combine
        int val[]={0.0.0};// Temporary storage array
        boolean jud[] = new boolean[arr.length];// Check whether it is used
        dfs(arr,val, jud,  0."");// Use a string length to visualize the result
    }

    private static void dfs(int[] arr, int val[],boolean[] jud, int index,String s) {
        System.out.println(s+Arrays.toString(val));
        if (index == arr.length){ }// Stop the recursive condition
        else{
            for (int i = 0; i < arr.length; i++) {
                if(! jud[i]) {// Not currently available
                    int team=val[index];
                    val[index] = arr[i];
                    jud[i] = true;// The lower layer is not in use
                    dfs(arr, val, jud, index + 1,s+"_");
                    jud[i] = false;/ / reduction
                    val[index]=team;
                }
            }
        }
    }
}
Copy the code

The result of execution is:

Here is another picture to understand:

Generally, a process of backtracking algorithm is roughly as follows:

Define backtracking algorithm and parameters - (qualified) jump out - (not qualified) Not jump out: - - walk through the list of operations to be done && the element is operable && Can continue to explore - - mark the element as used and other operations - - recursive call (parameter change) - - clear the element mark and other operationsCopy the code

When using an array for backtracking, you need to mark the subrecursion to prevent an infinite loop, and when you come back you need to unpack the position so that it can be used again after the number is used by other brothers! And if you’re using a List or a StringBuilder or something like that, you do the same undo, you add when you delete, you add when you subtract. Well, I’m sure backtracking is no problem for you.

Eight Queens problem

After mastering the key of backtracking algorithm, the eight queens problem can be thought out. The previous explanation is to solve the eight queens problem to pave the way. First, let’s look carefully at the description of the eight Queens problem.

The Eight Queens problem, proposed by chess player Max Bethel in 1848, is a typical example of backtracking algorithms.

The question is expressed as: put 8 queens on 8×8 squares of chess, so that they can not attack each other, that is, any two queens can not be in the same row, the same column or the same diagonal line, ask how many positions. Gauss thinks there are 76 options. In 1854, different authors published 40 different solutions in the Chess Journal of Berlin, and later someone solved 92 results using graph theory. If after ±90 degrees, ±180 degrees rotation, and diagonal symmetry transformation pendulum method as a class, a total of 42 classes. After the invention of computers, various computer languages could be programmed to solve this problem.

How do we think about this? So where do you start?

  • Start with the constraints

The eight Queens problem has the following limitations:

  • Eight by eight squares
  • One for each row, a total of eight rows (0-7)
  • One for each column, a total of eight columns (0-7)
  • One left slash for each 15 left slashes (0-14)
  • Fifteen right slashes, one for each right slash (0-14)

When you look at these constraints, you must think that there are so many constraints that need to be judged. To determine this, of course, use Boolean arrays. So we first use four Boolean arrays to determine if each condition is satisfied.

So to represent this graph we can use an array of ints, 0 for none, 1 for queens.

So how do you design this algorithm? This is not every grid Numbers, so when carries on the back should not be down each grid in each grid recursive (peer mutex), that is, when the recursion to the current layer, loop through the layer of the eight test (test) every kind of circumstance, if does not meet the conditions of not operating and terminated, But every row that satisfies this condition has to go to the next row when you recurse.

Of course, you need to know in advance how the current position horizontal and vertical coordinates know the corresponding Boolean position (the position starts at 0). For example, the corresponding position in p(x,y) is:

  • hang[] : xEach row is the corresponding I.
  • lie[] : yEach of these columns is the corresponding j.
  • zuoxie[] : x+yThe order is from top left to bottom right
  • youxie[] : x+(7-y)Set the order from top right to bottom left (personal habit)

Well, the implementation code of this algorithm is:

import java.util.Arrays;

public class EightQueens {
    static  int allnum=0;
    public static void main(String[] args) {
        boolean hang[]=new boolean[8];/ / line
        boolean lie[]=new boolean[8];/ / column
        boolean zuoxie[]=new boolean[15];/ / the left forward slash
        boolean youxie[]=new boolean[15];/ / right slash
        int map[][]=new int[8] [8];/ / map
        dfs(0,hang,lie,zuoxie,youxie,map);// Go ahead
    }

    private static void dfs(int hindex, boolean[] hang, boolean[] lie, boolean[] zuoxie, boolean[] youxie, int[][] map) {
        if(hindex==8){
            allnum++;
            printmap(map);/ / output map
        }
        else{
            //hindex is row I is a specific column
            for(int i=0; i<8; i++) {if(! hang[hindex]&&! lie[i]&&! zuoxie[hindex+i]&&! youxie[hindex+(7-i)])
                {
                    hang[hindex]=true;/ / test
                    lie[i]=true;
                    zuoxie[hindex+i]=true;
                    youxie[hindex+(7-i)]=true;
                    map[hindex][i]=1;
                    dfs(hindex+1,hang,lie,zuoxie,youxie,map);//dfs
                    hang[hindex]=false;/ / reduction
                    lie[i]=false;
                    zuoxie[hindex+i]=false;
                    youxie[hindex+(7-i)]=false;
                    map[hindex][i]=0; }}}}// Output the map
    private static void printmap(int[][] map) {
        System.out.println("The first"+allnum+"The permutations are");
        for(inta[]:map) { System.out.println(Arrays.toString(a)); }}}Copy the code

You can see how many queens there are, and it ends up being 92, and I have to say it’s really nice to be able to do it mathematically.

Eight queens variety

At this time, I think the eight queens problem has been made clear, but the wise people always come up with all kinds of methods to change the topic is difficult to us, this eight queens problem has many variations, such as N queen, sudoku and other problems.

Here are two variants of sudoku problems.

Force buckle 36 effective sudoku

So you have to think about things like this, which is very similar to the eight queens, which is 9 by 9, but you have to think about things like horizontal, vertical and 3×3 squares.

Of course, this problem is relatively simple, there is a problem is more trouble buckle 37 solution sudoku.

The difficulty of this problem is that we have data at every position and we have to test it.

There are a couple of things to think about in this kind of two-dimensional backtracking, and we’re going to think about it line by line. Each row is already marked with some data in advance, and after the initial test value is put, the condition is satisfied and the recursive test goes down. All the way to the end and if that happens then we can end and return the array.

Two points need to be noted here:

  • It’s a bit of a hassle to do a recursive backtracking with two parameters in two dimensions to figure out who is adding and subtracting, so let’s take one parameter index and use it to calculate the horizontal and vertical coordinates to do the conversion, so it’s a little bit less of a hassle in two dimensions recursion.
  • Backtracking is a back and forth process. Normally, the data needs to be changed back during the backtracking process, but if the result is already known, there is no need to go back. You can simply stop placing backtracking and change the value (I used an ISFinish Boolean type here).

The code can be referred to as:

conclusion

Ok, I wonder if I can master the backtracking algorithm and thought of the eight queens after the end of this topic, and clarify the relationship between recursion, backtracking, deep search and the eight queens?

On the whole

  • Recursion is more about one way, calling yourself.
  • Backtracking is more exploratory and restorative, a process that is usually mediated by recursion.
  • DFS depth-first search is generally implemented by stack or recursion. If recursion is used, data may or may not be recovered, so backtracking is a kind of deep search.
  • Eight queens is the problem solved by the classical backtracking algorithm. You said depth-first search is actually no problem, but backtracking can more accurately describe the characteristics of the algorithm.

Well, don’t say, I bigsai to get 30 and ten thousand silver! (Good words remember a key triple, wechat search Bigsai, reply Bigsai marry Queen Medusa next time!)