# Leetcode: N-Queens II

N-Queens II

Now, instead outputting board configurations, return the total number of distinct solutions.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

```## Blog link: https://code.dennyzhang.com/n-queens-ii
## Basic Ideas: backtracking
##              Place queen row by row
##              For the position we have tried, examine conflict for rows and triangles
## Complexity: Time ? Space ?
class Solution(object):
def totalNQueens(self, n):
"""
:type n: int
:rtype: int
"""
if n <= 0:
return 0
self.board = [] * n
for i in xrange(n):
self.board.append(['.']*n)
self.res = 0
self.myTotalNQueens(n, 0)
return self.res

def myTotalNQueens(self, n, row):
"""
:type n: int
:rtype: int
"""
if row == n:
self.res += 1
return

for col in xrange(n):
self.board[row][col] = 'Q'
if self.validQueeens(n, row, col):
self.myTotalNQueens(n, row+1)
self.board[row][col] = '.'

def validQueeens(self, n, row, col):
# check column
for index in xrange(n):
if index == row: continue
if self.board[index][col] == 'Q':
return False

# Check triangle
for i in xrange(n):
for j in xrange(n):
if i == row and j == col: continue
if abs(i-row) == abs(j-col) and self.board[i][j] == 'Q':
return False
return True

# s = Solution()
# print s.totalNQueens(1) # 1
# print s.totalNQueens(4) # 2
```

Share It, If You Like It.