N皇后问题

LintCode题目地址

def isConflict(self,index):
        nextY = len(self.result)
        for i in range(nextY):
            if abs(self.result[i] - index) in (0, nextY - i):
                return True
        return False


    def drawChess(self):
        cols = []
        n = len(self.result)
        for i in range(n):
            r = ['.'] * n
            r[self.result[i]] = 'Q'
            cols.append(''.join(r))
        return cols

    def searchNQueens(self, n):
        if len(self.result) == n:
            self.resultAll.append(self.drawChess())
            return

        for index in range(n):
            if self.isConflict(index) == True:
                continue
            self.result.append(index)
            self.searchNQueens(n)
            self.result.pop()

    def solveNQueens(self, n):
        self.resultAll = []
        self.result = []
        self.searchNQueens(n)
        return self.resultAll

注释版本

# 判断新加入的index，是否与已存在的冲突
    def isConflict(self,index):
        nextY = len(self.result)
        for i in range(nextY):
            if abs(self.result[i] - index) in (0, nextY - i):
                return True
        return False

    #将数组画出来
    def drawChess(self):
        cols = []
        n = len(self.result)
        for i in range(n):
            r = ['.'] * n
            r[self.result[i]] = 'Q'
            cols.append(''.join(r))
        return cols

    def searchNQueens(self, n):
        #符合条件就加入到self.resultAl
        if len(self.result) == n:
            self.resultAll.append(self.drawChess())
            return

        for index in range(n):
            #先判断将要加入的元素，是否和已存在的冲突
            if self.isConflict(index) == True:
                continue
            self.result.append(index)
            self.searchNQueens(n)
            self.result.pop()

    def solveNQueens(self, n):
        self.resultAll = []
        self.result = []
        self.searchNQueens(n)
        return self.resultAll