N-Queens II

N-Queens II实际上是N-Queens的缩小版实现，即它要求我们求出任意维度的N皇后可解数，但不要求我们把每一种方案都绘制出来，而此题的要点是要想到一个判断皇后之间不会互相攻击的办法，这里使用的是三个哈希表利用他们分别表示每一个合法的放置位在列数，左对角线以及右对角线上的位置，利用这三个部分以及数组的下标（代表行数）就可以是皇后的位置不会互相攻击，从而进行回溯并合法减枝，下面是代码

class Solution(object):
    def totalNQueens(self, n):
        """
        :type n: int
        :rtype: int
        """
        col, left_dia, right_dia = set([]), set([]), set([])
        res = [0]
        self.helper(0, n, col, left_dia, right_dia, res)
        return res[0]

    def helper(self, start, end, col, left_dia, right_dia, res):
        for i in xrange(end):
            if i in col:
                continue
            if start - i in left_dia:
                continue
            if start + i in right_dia:
                continue
            if start >= end - 1:
                res[0] += 1
            else:
                col.add(i)
                left_dia.add(start - i)
                right_dia.add(start + i)
                self.helper(start + 1, end, col, left_dia, right_dia, res)
                col.remove(i)
                left_dia.remove(start - i)
                right_dia.remove(start + i)

N-Queens

这道题就是把第二题的结果全部画出来，但是有一个需要注意的问题就是这里对于画棋盘的判断必须像传统的回溯题一样放到最开始了，因为如果放入循环中，我们得到的结果并不会被输出，下面是代码

class Solution(object):
    def solveNQueens(self, n):
        """
        :type n: int
        :rtype: List[List[str]]
        """
        tmp, res = [], []
        col, left_dia, right_dia = set([]), set([]), set([])
        self.helper(0, n, col, left_dia, right_dia, tmp, res)
        return res

    def helper(self, start, end, col, left_dia, right_dia, tmp, res):
        if start >= end:
            res.append(self.draw(tmp))

        for i in xrange(end):
            if i in col:
                continue
            if start - i in left_dia:
                continue
            if start + i in right_dia:
                continue
            col.add(i)
            left_dia.add(start - i)
            right_dia.add(start + i)
            tmp.append(i)
            self.helper(start + 1, end, col, left_dia, right_dia, tmp, res)
            col.remove(i)
            left_dia.remove(start - i)
            right_dia.remove(start + i)
            tmp.pop()

    def draw(self, indexList):
        n = len(indexList)
        result = [['.'] * n for _ in xrange(n)]
        for i in xrange(n):
            result[i][indexList[i]] = 'Q'
            result[i] = ''.join(result[i])
        return result