八皇后问题,是一个古老而著名的问题,是利用回溯算法求解的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于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的形式,具体实现方法参见如下程序:
最终的结果:
领取专属 10元无门槛券
私享最新 技术干货