N皇后问题算法

N皇后问题的两种主要算法是试探回溯法和位运算法。前一种是经典算法，后一种是目前公认的最高效算法，后者比前者效率提高了至少一个数量级。很多问题可以借鉴位运算的思想。
以下是转载的我认为写的比较好的一篇N皇后问题算法分析。转载地址：<a href="http://blog.csdn.net/hackbuteer1/article/details/6657109" rel="noopener noreferrer" target="_blank">http://blog.csdn.net/hackbuteer1/article/details/6657109</a>
 

 N皇后问题是一个经典的问题，在一个N*N的棋盘上放置N个皇后，每行一个并使其不能互相攻击（同一行、同一列、同一斜线上的皇后都会自动攻击）。
 一、求解N皇后问题是算法中回溯法应用的一个经典案例
 回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。
 在现实中，有很多问题往往需要我们把其所有可能穷举出来，然后从中找出满足某种要求的可能或最优的情况，从而得到整个问题的解。回溯算法就是解决这种问题的“通用算法”，有“万能算法”之称。N皇后问题在N增大时就是这样一个解空间很大的问题，所以比较适合用这种方法求解。这也是N皇后问题的传统解法，很经典。
 下面是算法的高级伪码描述，这里用一个N*N的矩阵来存储棋盘：
 1) 算法开始, 清空棋盘，当前行设为第一行，当前列设为第一列
 2) 在当前行，当前列的位置上判断是否满足条件(即保证经过这一点的行,列与斜线上都没有两个皇后)，若不满足，跳到第4步
 3) 在当前位置上满足条件的情形：
 在当前位置放一个皇后，若当前行是最后一行，记录一个解；
 若当前行不是最后一行，当前行设为下一行, 当前列设为当前行的第一个待测位置；
 若当前行是最后一行，当前列不是最后一列，当前列设为下一列；
 若当前行是最后一行，当前列是最后一列，回溯，即清空当前行及以下各行的棋盘，然后，当前行设为上一行，当前列设为当前行的下一个待测位置；
 以上返回到第2步
 4) 在当前位置上不满足条件的情形：
 若当前列不是最后一列，当前列设为下一列，返回到第2步;
 若当前列是最后一列了，回溯，即，若当前行已经是第一行了，算法退出，否则，清空当前行及以下各行的棋盘，然后，当前

N皇后问题算法

浏览过的版块