N皇后问题摆法算法描述
2009-01-26 11:57:59 来源:WEB开发网题目说明:
在一个N×N的国际象棋棋盘中摆N个皇后,使这N个皇后不能互相被对方吃掉。
题目要求:
(1)依次输出各种成功的放置方法。
(2)最好能画出棋盘的图形形式,并动态的演示试探过程。
(3)程序能方便的移植到其它规格的棋盘上。
例如:在一个4×4的棋盘可以摆放的棋位置{(0,1)(1,3)(2,0)(3,2)},{(0,2)(1,0)(2,3)(3,1)}两种。
题目分析:
一、试探过程分析:
N×N皇后问题的求解过程就是一个试探回逆的过程。如图-1
(图1-1)
1、首先查找第一行的可放位置,第一行全部可以放,那么我们就先将第一个皇后放在(0,0)点。
(图1-2)
2、再查找第二行,由于第一行的(0,0)已经放了皇后,故第二行的(1,0)和(1,1)都能放皇后了,可放的就是(1,2)和(1,3)点,在(1,2)放上皇后。
(图1-3)
3、再查找第三行,查找所以发现第三行没有可放的位置了,回逆到第二行讲皇后放到(1,3)再查找第3行。如果还不行,就回到第一行将第一行的皇后放人下一个可放的点,依次类推,查找N×N上的所以可放的位置,直到第一行所以位置被放完,输出结果。
4、根据上面的规律可以发现,对于一个皇后放在坐标(x,y),它的下一行位置为(x-1,y)(x,y)(x+1,y)的坐标都不能再放皇后。我们用一个数组来存放本行能放皇后的点。用循环来查找上面行对本行的影响,将收到影响的点置FAlSE。
5、计算公式为:
iPlaceOver[col - (column - i)] = false;
iPlaceOver[col] = false;
iPlaceOver[col + (column - i)] = false;
其中col是上面行皇后的位置,column是当前的第N行。
6、跌代过程:
for (i = 0 ; i < m_iCount ; i ++)
{
if (iPlaceOver[i]) //如果是可以放皇后的位置
{
m_piSaveQPlace[column] = i;//保存位置
ComputQueenPlace(column + 1);//递归搜索下一行
}
}
7、为了动态保存计算结果,程序使用了一个整形的数组指针存放每次结果中每行的位置。为了方便和清晰的显示,我使用了一个结构保存。
8、增加了一个位图保存函数,用来保存希望保存为位图的结果。
赞助商链接