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的形式，具体实现方法参见如下程序：

最终的结果：