题目来源
https://leetcode.com/problems/n-queens-ii/
Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.
题意分析
Input: n
Output: n of number of the result
Conditions:n 皇后问题，但是返回数目
题目思路
上题采用递归方法，这次采用非递归方法做，主要是弄清楚非递归什么时候回溯即可。同上题，采用一维数组存储第i行的位置，然后每一次判断条件也是跟上题一样（一维表示不会同行，board[i] != board[j]表示同列，abs（i- j）!= abs（list[i] - list[j]）表示不会同斜线）。
回溯的方法是，如果在本行没找到把row -= 1，然后把board[row] = -1(注意row已经更新了)，col = board[row] + 1（从新的一行的已有结果的下一列开始找）
row的判断：
当row等于0并且还需要回溯时，即可终止寻找
当row等于n-1时，此时说明有一个答案（前提是这一行已经找到了）
AC代码（Python）
__author__ = 'YE' class Solution(object):
def totalNQueens(self, n):
"""
:type n: int
:rtype: int
"""
def check(k, j):
for i in range(k):
if board[i] == j or abs(k - i) == abs(board[i] - j):
return False
return True board = [-1 for i in range(n)] row = 0
col = 0
count = 0 while row < n:
while col < n:
if check(row, col):
board[row] = col
col = 0
break
else:
col += 1
if board[row] == -1:
if row == 0:
break
else:
row -= 1
col = board[row] + 1
board[row] = -1
continue
if row == n - 1:
count += 1
col = board[row] + 1
board[row] = -1
continue
row += 1
return count n = 4
print(Solution().totalNQueens(n))