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

Topic describes

The n-queen problem is the study of how to place n queens on an n-by-n chess board, and make the queens unable to attack each other.

The figure above shows a solution to the 8 queens problem.

Given an integer n, return the number of different solutions for n queens.

Example:

Input: 4 Output: 2 Explanation: 4 There are two different solutions to the queen problem. [[" Q.. ", / / solution 1... "Q", "Q...", ".. Q. "], [".. Q., / / solution 2 "Q...", "... Q ", ". Q.. "]]Copy the code

Tip:

  • The queen“Is a chess piece, which means the king’s wife. The queen does only one thing, and that is to eat. When she came across a piece she could eat, she quickly rushed to take it. Of course, she can walk horizontally, vertically or diagonallyN-1Step, can advance or go back. (quoted fromBaidu Encyclopedia – Queen)

Source: LeetCode link: leetcode-cn.com/problems/n-… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.

Backtracking algorithm based on set judgment

In the international chess, the king’s woman is very powerful, horizontal, vertical, oblique can attack to, now to N harem beauty set a stage to perform, in order to ensure the stability of the harem, the following four conditions need to be met:

  • There can only be one queen per row
  • Each column can have only one queen
  • There can be only one queen on the main diagonal from top left to bottom right
  • There can be only one queen in the secondary diagonal from upper right to lower left

Since we can control the placement of a queen in each row during backtracking, and then enter the placement process of the next row, there will only be one queen in each row. The first condition is naturally met, and only the next three conditions need to be met.

You can use three sets named cols, D1, and d2 to record previously used columns, primary diagonals, and secondary diagonals, respectively. The number of columns for the new queen, primary diagonals, and secondary diagonals cannot appear in COLs, D1, and d2.

Cols keeps the number of columns that we’ve used before, so it makes sense to just store 0 through n minus 1. But what about the primary diagonal and the secondary diagonal?

Through observation, we found that:

  • For all elements on the same principal diagonal, the difference between the number of rows and the number of columns is equalrow - colCan be
  • The sum of the number of rows and the number of columns of all elements located on the same sub-diagonal is equalrow + colCan be

Here, the idea is basically out, before releasing the final solution, let’s compare my backtracking algorithm template:

def backtrack(path, state, opts) :
    if base:  # Baseline conditions
        res.append(path)
        return
    for opt in opts:
        if prune:  # Pruning conditions
            continue/break
        # Save live (make a selection)
        path.append(opt)
        state = change(state)
        opts.remove(opt)
        # recursive
        backtrack(path, state, opts)
        # Restore the scene (unselect)
        path.remove(opt)
        state = unchange(state)
        opts.append(opt)
Copy the code

For this question:

  • pathPaths are not needed because you don’t need to keep track of the board placement, you just need to count the numbers
  • stateThe state is required to userowTo record the current line to be placed
  • optsThe selection set is also required. It’s made up ofcols,d1 和 d2Three sets

The following is the solution to the problem:

class Solution:
    def totalNQueens(self, n: int) - >int:
        res = 0
        cols, d1, d2 = set(), set(), set(a)def backtrack(row) :
            # Baseline conditions
            if row == n:
                nonlocal res
                res += 1
            for col in range(n):
                # Pruning conditions
                if (col in cols
                or row - col in d1
                or row + col in d2):
                    continue
                # Save the scene
                cols.add(col)
                d1.add(row - col)
                d2.add(row + col)
                # recursive
                backtrack(row + 1)
                # Restore site
                cols.remove(col)
                d1.remove(row - col)
                d2.remove(row + col)
        return backtrack(0) or res
Copy the code

Running result:

Result: Passed execution time: 56 ms, beating 79.96% of users in all Python3 commits memory consumption: 13.5 MB, beating 9.69% of users in all Python3 commits

The time complexity is order n! O(n!) O(n!) , there are n levels of recursion, and the number of columns that can be selected for each level of recursion is n, n-1, n-2… One, so at most n! n! n! So the time complexity is O(n!). O(n!) O(n!) .

In addition, the problem can also be done based on bit operation, can refer to the official problem solution method two.