51. N-Queens

这一题的写法是模仿discussion中的Java的。总的来说分为以下几个部分，初始化board的时候把所有的点的值都初始化为'.'，在遍历的时候按照列索引，判断列中行坐标的点是否可以放置，直到列索引达到最后，这样可以确定一种答案

class Solution(object):
    def solveNQueens(self, n):
        """
        :type n: int
        :rtype: List[List[str]]
        """
        board = [['.' for i in range(n)] for i in range(n)]
        res = []
        self.dfs(0, board, res)
        return res
        
    def dfs(self, curcol, board, res):
        if curcol == len(board):
            res.append(self.construct(board))
            return
        for i in range(len(board)):
            if self.check(board, i, curcol):
                board[i][curcol] = 'Q'
                self.dfs(curcol+1, board, res)
                board[i][curcol] = '.'       
    
    def check(self, board, x, y):
        for i in range(len(board)):
            for j in range(y):
                if board[i][j] == 'Q' and ((x+j == y+i) or (x+y == i+j) or (x==i)):
                    return False
        return True
    def construct(self, board):
        res = []
        for i in range(len(board)):
            s = ''
            for j in range(len(board)):
                s += board[i][j]
            res.append(s)
        return res