N-皇后问题

问题描述：有N个皇后，需要放在N*N的棋盘上，同一行、同一列、同一对角线不能同时出现两个及以上的皇后，一共有多少种方法？

思路：

• 使用长度为N的向量a保存第I行的皇后所在的列的位置。
• 判断第i行第j列是否可以放置皇后的条件：
  1、所在行所在列没有皇后，a的其他元素值没有为j的；
  2、所在对角线没有皇后，abs(a[i]-col) == abs(row-i)
• 逐行遍历

import numpy as np
def to_list(a):
    l = []
    for i in range(len(a)):
        p = list('.' * len(a))
        p[int(a[i])] = 'Q'
        l.append(''.join(p))
    return l
def is_valid(row, col, a, num_queen):
    for i in range(num_queen):
        if a[i] == col or (abs(a[i]-col) == abs(row-i)):
            return 0
    return 1
    
class Solution(object):
    def solveNQueens(self, n):
        """
        :type n: int
        :rtype: List[List[str]]
        """
        num_queen = n
        a = np.ones(num_queen)*(-888)
        
        i = j = 0
        num_result = 0
        result = []
        while i < num_queen:
            while j < num_queen:
                #如果i行j列可以放皇后, 第i行找到位置放皇后
                if is_valid(i, j, a, n):
                    a[i] = j
                    j = 0 
                    break
                else:
                    j += 1
            #如果i行没有找到位置放皇后
            if a[i] < 0:
                if i==0:
                    break
                else:
                    i -= 1
                    j = a[i] + 1
                    a[i] = -888
                    continue
            #如果i行找到位置，如果是最后一行，说明找到了一个结果
            if i == num_queen-1:
                b = a.copy()
                result.append(to_list(b))
                num_result += 1
                j = a[i] + 1
                a[i] = -888
                continue
            #如果找到位置，且不是最后一行，寻找下一行
            i += 1
        return result