N皇后问题摆法算法描述

题目说明:

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

时间: 2025-01-24 23:39:22

N皇后问题摆法算法描述的相关文章

dfs-图,DFS,8皇后问题 思路或者算法

问题描述 图,DFS,8皇后问题 思路或者算法 必须用C或C++,用图结构和DFS解决8皇后问题,需要思路或者算法设计,刚学数据结构这门课,有些问题不会 解决方案 #include <iostream> #include <math.h> #include <stdio.h> #include <string.h> using namespace std; int mat[8][8]; int ans = 0; bool check(int row,int

c-八皇后问下 ,算法题目

问题描述 八皇后问下 ,算法题目 帮忙看下这个八皇后的错哪里了 #include int nodanger(int row,int n,int (*a)[8]) { int i; int k,flag1=0,flag2=0,flag3=0,flag4=0,flag5=0; //列 5个flag判断5个方向有没有危险 for( i=0; i { if (*(*(a+i)+n)!=0) { flag1=1; break; } } //左上 for(i=row,k=n;i>0&&k>

MD5算法之C#程序 MD5算法描述

程序|算法 当我要写一个MD5算法的程序时,发现中英文的语言描述都有一些不确切的地方,某些个细节讲得不清楚,或者说很费解.最后不得不拿出C语言的源程序来调试,这对于理解算法是很不利的.于是就总结了一下我摸索到的一些要点. 1.来历MD5的全称是message-digest algorithm 5(信息-摘要算法,在90年代初由mit laboratory for computer science和rsa data security inc的ronald l. rivest开发出来,经md2.md

MD5算法描述的C#描述程序

MD5算法描述 当我要写一个MD5算法的程序时,发现中英文的语言描述都有一些不确切的地方,某些个细节讲得不清楚,或者说很费解.最后不得不拿出C语言的源程序来调试,这对于理解算法是很不利的.于是就总结了一下我摸索到的一些要点. 1.来历 MD5的全称是message-digest algorithm 5(信息-摘要算法,在90年代初由mit laboratory for computer science和rsa data security inc的ronald l. rivest开发出来,经md2

纹理-完成下面任意一个可视化功能模块的详细设计,包括数据模型的选择、功能设计、算法描述、实现过程

问题描述 完成下面任意一个可视化功能模块的详细设计,包括数据模型的选择.功能设计.算法描述.实现过程 完成下面任意一个可视化功能模块的详细设计,包括数据模型的选择.功能设计.算法描述.实现过程 1. 三维地质体建模功能(可基于钻孔数据.剖面数据或者混合数据展开设计) 2. 三维地形多层次细节(LOD)显示功能(可基于TIN地形或者GRID地形展开设计) 3. 复杂地物(建筑物)建模功能设计(造型.插值.贴纹理等) 4. 地质体三维矢量剪切分析功能(可基于BSP树体剪切或者B-Rep模型面剪切展开

紧急求助-国际象棋马的极小满覆盖!!急求算法描述!

问题描述 国际象棋马的极小满覆盖!!急求算法描述! 有兄弟知道国际象棋马的极小满覆盖算法的吗,希望能介绍下算法!先谢过了!! 解决方案 http://bbs.csdn.net/topics/300248542

EM算法之一 ———— EM算法描述与推论,应用

      机器学习十大算法之一:EM算法.能评得上十大之一,让人听起来觉得挺NB的.什么是NB啊,我们一般说某个人很NB,是因为他能解决一些别人解决不了的问题.神为什么是神,因为神能做很多人做不了的事.那么EM算法能解决什么问题呢?或者说EM算法是因为什么而来到这个世界上,还吸引了那么多世人的目光.        我希望自己能通俗地把它理解或者说明白,但是,EM这个问题感觉真的不太好用通俗的语言去说明白,因为它很简单,又很复杂.简单在于它的思想,简单在于其仅包含了两个步骤就能完成强大的功能,复

php 二分查找法算法详解

一.概念:二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好:其缺点是要求待查表为有序表,且插入删除困难.因此,折半查找方法适用于不经常变动而查找频繁的有序列表.首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功:否则利用中间位置记录将表分成前.后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表.重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功. 二.代

PB动态创建菜单的核心算法描述

作者:达通兴电脑科技公司(www.study01job.com) 郭宝利 总体思路是,首先设计一个MenuBar,也就是菜单横向的项目,然后各个下拉菜单可以使用程序来实现.程序实现的思路是,根据指定的内容(text和tag)向菜单中追加.程序主要算法如下: /*----------------------------------------------------------------- * 函数名称:none gf_add_menuItem(menu am_menu,string as_It