频道栏目
首页 > 考试 > 其他 > 正文
python编程练习题之N-Queens八皇后问题
2017-10-11 09:22:10      个评论    来源:Rude3Knife的博客  
收藏   我要投稿

N-Queens

题目大意

经典的八皇后问题的一般情况
注意点:
皇后用”Q”表示,空白用”.”表示

解题思路

方法很多,见总结

代码

回溯法

class Solution(object):
    def solveNQueens(self, n):
        """
        :type n: int
        :rtype: List[List[str]]
        """
        self.n = n  # 由于之后还要用到n,n作为类变量
        result = []
        columns = [-1 for i in range(n)]  # [-1, -1, -1, -1]
        self.solve(columns, 0, result)
        return result

    def make_string_list(self, columns):
        sol = []  # 一个完整的棋盘
        row = ['.' for i in range(self.n)]  # ['.', '.', '.', '.']
        for c in columns:
            new_row = row[:] 
            new_row[c] = 'Q'
            sol.append(''.join(new_row))  # 将row转为new_row, 将Q加入,然后转为字符串
        return sol

    def is_valid(self, columns, row, col):
        # print columns, 'hang', row, 'lie', col
        for r in range(row):
            c = columns[r]
            # print c, col
            if c == col:  # 在同一列,放弃
                return False
            if abs(c - col) == row - r:  # 对角线,放弃
                return False
        return True

    def solve(self, columns, row, result):
        if row == self.n:  # 所有列处理完毕
            # print 'columns:', columns # [1, 3, 0, 2], [2, 0, 3, 1]
            result.append(self.make_string_list(columns))
        else:
            for col in range(self.n):  # 依次遍历列,每个数字就代表每列皇后放在了第几行
                if self.is_valid(columns, row, col):
                    columns[row] = col
                    self.solve(columns, row + 1, result)

总结

每个方法我都尽量详细注释,并且把重要变量print出来便于理解。

点击复制链接 与好友分享!回本站首页
上一篇:编程开发排序问题:Saruman's Army
下一篇:编程开发练习刷题记录
相关文章
图文推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站