使用递归来求解, 从网上看到一种很好的棋盘表示方法, N = 4时, 棋盘为[1, 3, 0, 2], 即第1行的queen放在第2列, 第2行的queen放在第4列。Queen逐行放入棋盘, 每放入一个新的queen, 只需要检查她跟之前的queen是否列冲突和对角线冲突就可以了。如果两个queen的坐标为(i1, j1)和(i2, j2), 当abs(i1 - i2) = abs(j1 - j2)时就对角线冲突。

class Solution:
    # @return a list of lists of string
    def solveNQueens(self, n):
        self.res = []
        self.solve(n, 0, [-1 for i in xrange(n)])
        return self.res
    
    def solve(self, n, currQueenNum, board):
        if currQueenNum == n:
            oneAnswer = [ ['.' for j in xrange(n)] for i in xrange(n) ]
            for i in xrange(n): 
                oneAnswer[i][board[i]] = 'Q'
                oneAnswer[i] = ''.join(oneAnswer[i])
            self.res.append(oneAnswer)
            return
        # try to put a Queen in (currQueenNum, 0), (currQueenNum, 1), ..., (currQueenNum, n-1)
        for i in xrange(n):
            valid = True  # test whether board[currQueenNum] can be i or not
            for k in xrange(currQueenNum):
                # check column
                if board[k] == i: valid = False; break
                # check dianogal
                if abs(board[k] - i) == currQueenNum - k: valid = False; break
            if valid:
                board[currQueenNum] = i
                self.solve(n, currQueenNum + 1, board)