科学网―皇后也疯狂：如何在1分钟内摆放300万个皇后 - 江贺的博文

科学网―皇后也疯狂：如何在1分钟内摆放300万个皇后 - 江贺的博文

我们知道，在国际象棋中，皇后可以在行、列和对角线上行走。那么考虑一下：如何在一个N * N 的棋盘上放置 N个皇后，使得每行、每列和每条对角线上不存在2个或2个以上的皇后。这实际上就是经典的N-皇后问题。N-皇后问题是人工智能领域中一个经典的组合问题，在包括VLSI和交通控制等问题上具有广泛的应用。图1 给出了包含4个皇后的4-皇后问题的例子。图1 (a)给出了一个违反了约束的解的例子。可以发现，每一行、每一列上均只有1个皇后，但是第1列和第2列的两个皇后在正对角线方向上违反了约束。而图1 (b)给出了一个合法解，在每一行、每一列均只有1个皇后，而且在正对角线、负对角线方向上最多只有一个皇后。

N-皇后问题是我们在数据结构和算法类的课程上经常遇到的一个问题，它的经典求解方法是采用回溯的方法，可以产生所有的可行解，但是实际上运行时间非常长，能够解决的问题规模相对非常小。有没有一种方法，可以在极短的时间内求解上百万个皇后的N-皇后问题？答案是可以，用局部搜索！Rok Sosic和Jun Gu （顾钧）在20余年前提出的系列快速局部搜索算法可以在极短的时间内，求解百万量级的N-皇后问题。

Read full article from 科学网―皇后也疯狂：如何在1分钟内摆放300万个皇后 - 江贺的博文