[backtracking based on bit operation] queen n problem 2

Link to the original title ：https://leetcode-cn.com/problems/n-queens-ii/
This topic is related to leetcode 51 The only difference is the output , This problem only requires output of several solutions
51 The problem requires the output of the specific form of each solution
Last article Use backtracking and set based backtracking to solve 51 topic , This time we use bit operation to solve
In order to better understand the post code annotation 1,2,3 Show steps , The following will simulate the program execution process and explain it step by step .

class Solution:
    def solveNQueens(self, n: int):
        def dfs(row, col, pie, na):
        	"position  in  1  Indicates where the queen can be placed "
        	"p  in  1  It means where to put the queen "
        	"col,pie,na,  in  1  Indicates that the queen of the previous line cannot be placed in this line due to the influence of the queen of the previous line "
        	"pie,na  Inconsistent with naming rules , But it's easy to understand   skimming , si "
        	"pie  Top right corner to bottom left corner ,na  Top left to bottom right "
            if row == n:  # 1
                return 1
            res = 0  # 2
            position = (~(col | pie | na)) & ((1 << n) - 1)  # 3
            while position:  # 4
                p = position & (-position)  # 5
                position &= position - 1  # 6
                res += dfs(row + 1, col | p, (pie | p) << 1, (na | p) >> 1)  # 7
            return res
        return dfs(0, 0, 0, 0)

"""  And  &  Meet  0  by  0  or  |  Meet  1  by  1  Take the opposite  ~ 1  change  0, 0  change  1  Move left  <<  Move right  >>  With  4  For example  4  Binary system  0100 1  Binary system  0001 4 & 1 -> 0100 & 0001 = 0000 4 | 1 -> 0100 | 0001 = 0101 ~4 -> ~0100 = 1011 4 << 1 -> 0100 << 1 = 1000 4 >> 1 -> 0100 >> 1 = 0010  With  n=4 For example ： dfs（0,0,0,0） From step 1 Start  1.  The number of rows is not equal to n, Do not enter  2. res=0 3. position = (~( 0 | 0 | 0 )) & (( 1 << n )-1) (~0) & (1 0000 - 0000 1) -> 1111 & 1111 -> 1111 position = 1111  meaning ： Queens can be placed in all four positions in the first row  |√|√|√|√| |-|-|-|-| |-|-|-|-| |-|-|-|-| 4. position  Not for 0  Into the loop  5. p = 1111 & 0001 p = 0001  meaning ： At this time, the queen is placed at the last position of the first line  |-|-|-|Q| |-|-|-|-| |-|-|-|-| |-|-|-|-| 6. position &= position - 1 1111 & (1111 - 0001) -> 1111 & 1110 position = 1110  meaning ： The first row also has the first three places to place the queen  |√|√|√|Q| |-|-|-|-| |-|-|-|-| |-|-|-|-| 7.  Go to the second level  dfs(1, 0001, 0010, 0000)  here  col pie na  Just make a detailed calculation , Not shown in detail below  col | p = 0000 & 0001 = 0001 (pie | p) = (0000 & 0001) <<1 = 0001 << 1 = 0010 (na | p) = (0000 & 0001) >> 1 = 0001 >> 1 = 0000 dfs( The second line , Last position , The third position ,  Fifth position （ Beyond so is 0）） 1.  The number of rows is not equal to n, Do not enter  2. res = 0 3. position = (~(0001 | 0010 | 0000)) & (( 1 << n)-1)  adopt  |  Overlap the second line with the case where the queen cannot be placed  0011 The queen cannot be placed in the last two positions of the second row  |-|-|×|×| (~0011) & (1111) -> 1100 & 1111 position = 1100  meaning ： The first two positions of the second line can be used to place queens  |√|√|√|Q| |√|√|×|×| |-|-|-|-| |-|-|-|-| 4. position  Not zero   Into the loop  5. p = 1100 & 1011 p = 1000  meaning ： The queen is placed in the first position of the second line  |√|√|√|Q| |Q|√|×|×| |-|-|-|-| |-|-|-|-| 6. position &= position - 1 1100 & 1011 -> 0100 position = 0100  meaning ： The queen can be placed in the second position of the second row  7.  Go to the third floor  dfs(2, 1001, 0100, 0100) 1. Do not enter  3. position = (~(1001 | 0100 | 0100)) & ((1 << n)-1)  adopt  |  Overlap the third line with the case where the queen cannot be placed  1101 Represents the third row. Only the third position of the row can be placed  |×|x|√|x| (~1101) & (1111) -> 0010 & 1111 position = 0010  meaning ： Only the third position can hold  |√|√|√|Q| |Q|√|×|×| |×|x|√|x| |-|-|-|-| 5. p = 0010 & 1110 p = 0010  meaning ： Place the queen in the third position on the third line  |√|√|√|Q| |Q|√|×|×| |×|x|Q|x| |-|-|-|-| 6. position &= position - 1 0010 & (0010 -1 ) -> 0010 & 0001 position = 0000  meaning ： There is no place for the queen in the third row  7.  Go to the fourth floor  dfs(3, 1011, 1100, 0011) 3. position = (~(1011 | 1100 | 0011)) & ((1 << n)-1)  At this point, it can be seen that   There is no suitable place for the queen in the fourth line   because ,col | pie | na = 1111 |×|x|x|x| (~1111) & (1111) position = 0000  meaning ： There is no place for the queen  |√|√|√|Q| |Q|√|×|×| |×|x|Q|x| |×|x|x|x| 4. position = 0  Don't go into the cycle   At this point, you begin to exit recursion   Return to the third line   But in the third line position = 0000  It means there is no place to put it  （ Or there is only one place to put , I've let it go ）, Continue back to the second floor   At this time, the second floor position = 0100  It means there is another place on the second floor where the queen can be placed ,  Return to the second layer to return to the original Q Put it in the second position  |√|√|√|Q| |√|√|√|Q| |Q|√|×|×| |x|Q|×|×| |-|-|-|-| |-|-|-|-| |-|-|-|-| |-|-|-|-|  The second layer is the original method   Go back to the second replay   And then the cycle goes on  """

s = Solution()
print('n = 4  From time to tome ', s.solveNQueens(4), ' Seed solution ')
print('n = 5  From time to tome ', s.solveNQueens(5), ' Seed solution ')
print('n = 8  From time to tome ', s.solveNQueens(8), ' Seed solution ')