# Question

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

https://leetcode.com/static/images/problemset/8-queens.png

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

Example:

Input: 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown below.
[
[".Q..",  // Solution 1
"...Q",
"Q...",
"..Q."],

["..Q.",  // Solution 2
"Q...",
"...Q",
".Q.."]
]


# Solution

Use backtracking. See N-Queen for explanation.

class Solution(object):
def totalNQueens(self, n):
"""
:type n: int
:rtype: int
"""
self.col = [True] * n
self.diag1 = [True] * (2 * n - 1)
self.diag2 = [True] * (2 * n - 1)
self.queens = [-1] * n
self.n = n

return self.__solve(0)

def __solve(self, row): # backtracking
if row == self.n:
return 1
else:
res = 0
for col in range(self.n):
if self.__isAvailable(row, col):
self.__place(row, col)
res += self.__solve(row + 1)
self.__remove(row, col)
return res

def __isAvailable(self, row, col):
return self.col[col] and self.diag1[row + col] and self.diag2[row - col + self.n - 1]

def __place(self, row, col):
self.queens[row] = col
self.col[col] = False
self.diag1[row + col] = False
self.diag2[row - col + self.n - 1] = False

def __remove(self, row, col):
self.queens[row] = -1
self.col[col] = True
self.diag1[row + col] = True
self.diag2[row - col + self.n - 1] = True