動機

如果兩點在對角線上x,y軸的差值會一樣!!

Problem

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return the number of distinct solutions to the n-queens puzzle.

 

Example 1:

Input: n = 4Output: 2Explanation: There are two distinct solutions to the 4-queens puzzle as shown.

Example 2:

Input: n = 1Output: 1

 

Constraints:

  • 1 <= n <= 9

Sol

如果兩點在對角線上x,y軸的差值會一樣

利用上面這一點，可以用n驗證有沒有攻擊

class Solution:
    def totalNQueens(self, n: int) -> int:
        def good(taken, j):
            return not any([abs(taken[dep] - j) in [0, len(taken)-dep] for dep in range(len(taken))])
        
        def bt(i,taken=[]):
            if i == n:
                return 1
            else:
                ret = 0
                for x in range(n):
                    if good(taken, x):
                        ret += bt(i+1, taken+[x])
                return ret
        return bt(0)