N皇后:回溯+尾递归优化解决

八皇后问题,是一个古老而著名的问题,是利用回溯算法求解的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处同一行、同一列或同一斜线上,问有多少种摆法。之后陆续有许多数学家对其进行研究,其中包括高斯和康托,并且将其推广为N皇后问题

  本文利用Python3实现回溯算法,通过遍历搜索得到N皇后问题的所有解,在根据规则删除掉本质相同的解,最后得到该问题的不同的解。此方法相比纯粹的暴力搜索,虽然程序复杂,但是可移植性较高。

  下面开始程序的实现,首先定义皇后的个数,以及一些输出设置。

利用numpy数组的形式代替棋盘,首先获取与已经选择的坐标相冲突的坐标集合,其中冲突包含两种:一是斜线方向上;二是同行同列方向上。然后再得出下一个选择坐标的可行的集合。

因为采用的是回溯算法搜索,因此这里用字典形式实时记录选择的情况,也就是记录当前选择的是可行坐标集合中的第几个元素。例如:

下面给出实现回溯算法函数的程序:

下面给出运算的结果:

下面是对本质相同的解的说明:如果解A通过主、副对角线对称转换,或者通过旋转90度的倍数的转换, 或者经过以上的组合转换可以得到解B,则认为解A与解B是本质一样的解。

下面给出关于副对角线对称解的说明:求解A关于副对角线对称的解A副,就相当于先将A顺时针移动90度得到A1,然后求A1关于主对角线对称的解A1主,也就是A副=A1主。详细展示看下图:

下面给出删除本质一样的解的程序:

下面给出从1-12个皇后问题的相关解数的结果:

重点说明:一般来说,Python和Java,C#一样,并没有尾递归自动优化的能力,递归调用会受到调用栈长度的限制。因此当设置皇后的数量大于9时,程序会崩溃。解决办法有很多种,本文采取尾递归优化方法。

下面给出尾递归优化的函数:

在使用了递归的函数前,也就是本文中的回溯算法函数huifu前添加装饰器语句@tail_call_optimized即可。如此设置之后,当皇后的个数大于9时,程序依然运行良好,因为是遍历搜索,运行可能较慢。

为了更好的展示皇后问题的解,本文依然采用图片合成gif的形式,具体实现方法参见如下程序:

最终的结果:

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180723G0CHAE00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励