当前位置: 老葡京网站娱乐 > 编程语言 > 算法 > 正文

N皇后问题摆法算法描述

时间:2009-01-27 本站整理 赵宏伟

老葡京网站娱乐 www.sdguanhua.com 题目说明:

在一个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、增加了一个位图保存函数,用来保存希望保存为位图的结果。