各大计算机公司 笔试及面试 题目 - 深信服(八皇后问题)

八皇后问题是一个以国际象棋为背景的问题:如何能够在 8×8 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题:这时棋盘的大小变为n×n,而皇后个数也变成n。当且仅当 n = 1 或 n ≥ 4 时问题有解。


在n×n格的棋盘上摆放n个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,求解满足条件的棋盘布局。

n-皇后问题是典型的可以使用回溯算法求解的问题。如果你明白了问题的具体执行过程,也就对该问题的特点有了把握,从而选择合适的算法去求解。

以8-皇后问题为例,假设皇后所在的行用变量row表示,对应的列使用数组column[row]表示。

使用回溯算法执行的过程如下:

(1)第一次放置第1个皇后

将第1个皇后放在第0行第0列,即row=0,column[row]=column[0],如图所示:

各大计算机公司 笔试及面试 题目 - 深信服(八皇后问题)

第1个皇后放置在坐标(0,0)处。

(2)第一次放置第2个皇后

因为第1个皇后已经放好,第1个皇后放置到第0行第0列,从第1个皇后下方的格子开始判断。第2个皇后位于第1行,则row=1:

当column[row]=column[1]=0时,与第1个皇后在同一列上,冲突,继续后移到下一列(即column[row]++);

当column[row]=column[1]=1时,与第1个皇后在同一对角线上,冲突,继续后移到下一列(即column[row]++);

当column[row]=column[1]=2时,与第1个皇后不在同一行、同一列、同一对角线上,故放置第2个皇后。

如图所示:

各大计算机公司 笔试及面试 题目 - 深信服(八皇后问题)

第2个皇后放置在坐标(1,2)处。

(3)第一次放置第3个皇后

因为第2个皇后已经放好,第2个皇后放置到第1行第2列,从第2个皇后下方的格子开始判断。第3个皇后位于第2行,则row=2:

当column[row]=column[2]=0时,与第1个皇后在同一对角线上,冲突,继续后移到下一列(即column[row]++);

当column[row]=column[2]=1时,与第2个皇后在同一对角线上,冲突,继续后移到下一列(即column[row]++);

当column[row]=column[2]=2时,与第2个皇后在同一列上,冲突,继续后移到下一列(即column[row]++);

当column[row]=column[2]=3时,与第2个皇后在同一对角线上,冲突,继续后移到下一列(即column[row]++);

当column[row]=column[1]=4时,与第1、2个皇后不在同一行、同一列、同一对角线上,故放置第3个皇后。

如图所示:

各大计算机公司 笔试及面试 题目 - 深信服(八皇后问题)

第3个皇后放置在坐标(2,4)处。

(4)第一次放置第4个皇后

如图所示:

各大计算机公司 笔试及面试 题目 - 深信服(八皇后问题)

第4个皇后放置在坐标(3,1)处。

(5)第一次放置第5个皇后

如图所示:

各大计算机公司 笔试及面试 题目 - 深信服(八皇后问题)

第4个皇后放置在坐标(4,3)处。其余依次类推。


代码如下:



备注:转载于 http://hi.baidu.com/shirdrn/blog/item/2720311b5cc970108618bfb1.html
上一篇:(二十四)mongodb中group的问题二


下一篇:使用JUnit高效完成功能测试