N皇后问题

分析

这是一个我初中就在书上看过的问题,但是从来没自己写过。
我一开始的想法是搞一个二维列表,把所有的位置存成012三种状态,分别是:皇后,可用,不可用。
每次遍历一个位置就重新判断一下整个棋盘哪些地方可以遍历。

后来我发现可以用数学的方法计算是否在同一条斜线上,在同一个正斜线上的点差是相同的,在同一个反斜线上的点和是相同的。
可以用一个很简单的递归解决问题。

N皇后解的数量

N解的个数
42
510
64
740
892
9352
10724
112680
1214200

再往下就有点慢了

代码

class eight_queen:
    def __init__(self, param_num):
        if param_num > 20:
            exit()
        self.param_num = param_num
        self.num = 0
        self.loop([])
        print(self.num)
    
    #循环
    def loop(self, queen):
        
        x = len(queen)
        if x == self.param_num:
            print(queen)
            self.num += 1
            return
        
        for y in range(self.param_num):
            #判断列
            if y in [x[1] for x in queen]:
                continue
            #判断正斜线
            if (x - y) in [x[0]-x[1] for x in queen]:
                continue
            #判断反斜线
            if (x + y) in [x[0]+x[1] for x in queen]:
                continue
            queen_ = queen[:]
            queen_.append((x,y))
            self.loop(queen_)

if __name__ == '__main__':
    eight_queen(8)
最后修改:2019 年 06 月 05 日 06 : 26 PM

1 条评论

  1. 心灵博客

    嗯,挺简单的,可惜我不会 5555555555

发表评论