今天是紀錄LeetCode解題的第五十二天
是一題困難題

第五十二題題目：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.

n皇后問題是指在n * n的棋盤上放置n個皇后，使得任兩個皇后不會互相攻擊的問題
給定一個整數n，傳回n皇后問題的所有不同解的數量

解題思路

在昨天的文章中有講解n皇后的規則及如何放置皇后在棋盤上(如果還不清楚的可以去看上一篇文章)，今天是傳回解的數量，所以我們不需要去建構board來儲存棋盤，和昨天類似的概念，一列一列去放置，只要在放置過程中，紀錄該行和兩個斜線，接著放下一個皇后時，檢查該皇后的位置是否和之前儲存的位置同一行或同個斜線上即可

程式碼

class Solution:
    def totalNQueens(self, n: int) -> int:
        count = [0]
        cols = set()
        diag1 = set() #存r - c(左上到右下)方向的斜線
        diag2 = set() #存r + c(右上到左下)方向的斜線
        def backtracking(row):
            if row == n:
                count[0] += 1
                return
            for col in range(n):
                if col in cols or (row - col) in diag1 or (row + col) in diag2:
                    continue
                cols.add(col)
                diag1.add(row - col)
                diag2.add(row + col)
                backtracking(row + 1)
                cols.remove(col)
                diag1.remove(row - col)
                diag2.remove (row + col)
         backtracking(0)
         return count[0]        

左上到右下的斜線為什麼是r - c?
假設已經放置在(0,0)的位置，那它的左上到右下的斜線分別是(1,1)、(2,2)、(3,3)，r - c都等於0，所以只要當r - c的值相同時，就代表在同一條左上到右下的斜線上

右上到左下的斜線為什麼是r + c?
假設已經放置在(0,3)的位置，那它的左上到右下的斜線分別是(1,2)、(2,1)、(3,0)，r + c都等於3，所以只要當r + c的值相同時，就代表在同一條右上到左下的斜線上