您应该利用每个皇后必须放在不同列中的事实。如果已经在前k列中放置了k个皇后,则将第k + 1个皇后号递归地放置在k + 1列中,并遍历第1到n行(而不是像现在那样遍历所有n * n个单元格)。为每个有效的位置继续k:= k + 1。这将避免任何重复的结果,因为该算法根本不会生成任何重复的板。
编辑:您如何避免对称性的问题:可以预先避免的一部分,例如,通过在列1到行1限制女王1,…n/2
。如果要完全避免对称解决方案的输出,则必须将找到的每个解决方案存储在列表中,每当找到新解决方案时,在打印出来之前,请测试列表中是否已存在对称解决方案之一。
为了提高效率,您可以使用每个板的“规范代表”,定义如下。生成给定板的所有对称板,将每块对称板包装到一个字节数组中,并保留其中的数组,该数组被解释为一个大数字,具有最小值。这种打包的表示形式是每个板对称类的唯一标识符,可以轻松地放入字典/哈希表中,这使测试该对称类是否已经非常有效。