皇后问题与回溯法

皇后问题与回溯法

  -- 一个经典问题与一个经典算法

---

# 故事
这些天，工作上有些空余翻翻书本，看看代码，不经意间地回忆起皇后问题的算法求解。最后翻出陈旧的程序代码，大学时期二年级写过皇后问题求解的代码……记得当时学院组织了次测试设计比赛，低年级题目（皇后问题）我获得了二等奖，高年级题目（五子棋）我获得了一等奖……犹记得那时，自己感觉挺满足的，自豪啊。


其实，现在看回去早前的代码，有很多不规范的地方，好像这是必然情况，每个还在继续努力的程序员都如此吧，不断在进步着，每当你回顾过去的代码时总有些这样的感慨。所以，索性自己抽些时间整理了一番规范之，同时也自己重新完成了另一实现。在此博文一篇记录，分享之吧。


# 八皇后问题

首先，转一段关于经典八皇后问题的说明，如下：

八皇后问题，是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。计算机发明后，有多种方法可以解决此问题。

# 分享
简要概括一句，应用回溯法求解出皇后问题的所有摆法。众所周知，回溯法是解决皇后问题的经典算法，随便你网上搜搜比比皆是。

接着，引用“回溯法百科”的说明，如下：
回溯法(探索与回溯法)是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

然后，具体实现的算法逻辑描述：
 1. 先将第一个皇后Q1固定在第一列第一行的位置pos[1][1]。
 2. 跳至下一列，寻找合理位置摆放皇后，即任意两个皇后都不能处于同一行、同一列或同一斜线上。
 2.1 若找到合理位置，则记录“回溯点”于栈容器，继续寻找下一列摆放下一皇后的合理位置，
 直至最后一列为止，这时就找到了一组满足条件的皇后排列，然后进行步骤2.2。
 2.2 若找不到合理位置，则从栈容器出栈“回溯点”，再寻找下一合理位置，再进行步骤2。
 直至回溯到第一列的位置，然后开始步骤3。
 3. 继续将Q1固定在下一位置pos[x+1][1]，继续开始步骤2，循环直至Q1固定在pos[n+1][1]。

# 附

 还有，另一种实现算法可参见以下链接的页面源码与说明。

 最后，关于文章描述的“皇后问题与回溯法”，涉及的完整示例代码不妨参见github的这里，还有这里。