preface

Long time no talk about algorithms! Let’s talk about queen N this time. The n Queens problem is the study of how to place n queens on an n by n board so that queens cannot attack each other. A lot of students on such questions are more panic, feel that the rules burn brain resistance, pray not to encounter in the interview, don’t worry, we will try to put this logic to say today.

A queen can move horizontally, vertically, and diagonally, and if a queen appears in the same row, column, or diagonally with another queen, it can be attacked by that queen.

So one of the rough things that we can do intuitively, is to list all the things that are on the board, and then we decide whether or not each of these combinations meets our criteria. But actually we don’t have to try all the combinations, we know that once we put one queen in one column, the other queens can’t be in that column, nor can they be in the same horizontal line with four diagonal angles. In this way, we can find the “road closed” first.

When we find that one path isn’t working, we quickly go back and try a different option, which we call backtracking.

What is this lofty backtrace

For the n queen problem, let’s expand this idea again:

  1. Put a queen in the first column of the first row
  2. Then we find a position in the second row where the second queen can’t be attacked by the queen in the first row
  3. If we can’t find such a place, we go back to the previous row and try to put the queen in the next column of that row
  4. Repeat this process until we find the right place for the last queen in the last row, and then we have a solution
  5. Once a solution has been found, we go back to the previous line and try to find the next solution

Still a little abstract?

Let’s take a look at one of the scenarios:

  1. We start at x=0,y=0, the first queen A is safe here,
  2. Then queen B in the second row has to start in the third column to avoid being attacked
  3. So now on the third row we find that we can’t put the queen, because wherever we put it, queen A or Queen B will attack us, right
  4. So we’re just going to go back to the second row, and we’re going to keep looking for a good column to put queen B in
  5. When the second row finds a condition that the last column does not satisfy, we can only go back to the first row, continue to find the column where queen A can be placed, and repeat the process

Take two steps?

Do you think your eyes will now? 🤔, next we can let the hand to try.

First we need a way to determine if a position can be placed with a queen, so that if a position is attacked by a queen already on the board, we can skip it:

// This method is used to determine whether the queen to be placed next is horizontal, vertical, or diagonal of an already placed queen, // If neither is true, Static Boolean isValidPosition(int proposedRow, int proposedCol, static Boolean isValidPosition(int proposedRow, int proposedCol, List<Integer> solution) {// For (int oldRow = 0; oldRow < proposedRow; ++oldRow) { int oldCol = solution.get(oldRow); int diagonalOffset = proposedRow - oldRow; if (oldCol == proposedCol || oldCol == proposedCol - diagonalOffset || oldCol == proposedCol + diagonalOffset) { return false; } } return true; }Copy the code

With this method in place, we need to implement a line-by-line search and go back to the previous line-by-line search if all paths are blocked and continue looking for other possibilities. Each line is searched the same way, so recursion is a good way to implement our logic:

Static void solveNQueensRec(int n, List<Integer> solution, int row, List<List<Integer>> results) {// If (row == n) {results.add(new ArrayList<Integer>(solution)); return; } // Start with the first column of each row for (int I = 0; i < n; ++ I) {// In the case of the last column and no suitable point is found, the current recursion ends and the stack is called back to the recursive flow of the previous layer, If (isValidPosition(row, I, solution)) {solution.set(row, I); solveNQueensRec(n, solution, row + 1, results); }}}Copy the code

When one path fails, the current recursion in the call stack ends and it goes back to the logic of the previous recursion, thus implementing our backtracking. Our goal is simple: at the end of the walk, we run out of paths, so we go back to the previous line and keep going until everything has been tried.

Finally, execute our recursive function:

static int solveNQueens(int n, List<List<Integer>> results) {
        List<Integer> solution = new ArrayList<Integer>(n);
        for (int i = 0; i < n; ++i) {
            solution.add(-1);
        }
        solveNQueensRec(n, solution, 0, results);
        return results.size();
    }
Copy the code

This is the same thing as picking N numbers out of an N by N array, order N to the N in time, order N factorial in space. .

Continue to spread

In the process of searching above, we go up line by line to find the appropriate position, and then return to the previous line under certain conditions, which is kind of like the operation of pushing on and out of the stack. In fact, we can also use the stack to realize the whole backtracking process. When we find a suitable position in a row, we push its column onto the stack, and pop it out when we go back to the previous row.

Static int solveNQueens(int n, List<List<Integer>> results) { List<Integer> solution = new ArrayList<Integer>(n); Stack<Integer> solStack = new Stack<Integer>(); for (int i = 0; i < n; ++i) { solution.add(-1); } int row = 0; int col = 0; If (isValidPosition(row, col, solution)){solstack.push (col); if(isValidPosition(col, solution)){solstack.push (col); solution.set(row, col); row++; col = 0; break; } // the current position is not good, try to put queen col++ in the next column; If (col == n){if(col == n){if(col == n) solStack.empty()){ col = solStack.peek() + 1; solStack.pop(); row--; } else{// only the first line has reached the last column, and all paths have been tried. }} if(row == n){results.add(new ArrayList<Integer>(solution)); // Go back to the previous row--; col = solStack.peek() + 1; solStack.pop(); } } return results.size(); }Copy the code

Time is O(n^n), space is O(n!). . The whole logic here is relatively straightforward, we still need the auxiliary method isValidPosition to judge whether a certain position can place the queen or not, and then judge each position one by one, and use the stack to coordinate the backtracking operation in the search process. The core idea remains the same.

conclusion

In both cases, we write down all the places that fit the rules, and if we just want to figure out how many possibilities there are at the end, we can actually change the array to a variable to count them, so that our spatial complexity can be optimized to O(n).

Ok, I believe you now have a perceptual understanding of the backtracking algorithm, and you can understand that backtracking is just a conventional way of thinking when we face problems, not a noble concept, we do not have to fear it ~