基于C++实现的N皇后问题

FullHouse

发布日期: 2018-11-04 17:09:36 浏览量: 852
评分:
star star star star star star star star star_border star_border
*转载请注明来自write-bug.com

一、使用说明

1.1 项目简介

八皇后问题是一个古老而著名的问题,是回溯算法的经典问题。该问题是十九世纪著名的数学家高斯在1850年提出的:在8*8的国际象棋棋盘上,安放8个皇后,要求没有一个皇后能够“吃掉”任何其它一个皇后,即任意两个皇后不能处于同一行,同一列或者同一条对角线上,求解有多少种摆法。

高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解,后来有人用图论的方法得到结论,有92种摆法。

本实验拓展了N皇后问题,即皇后个数由用户输入。

1.2 项目要求

八皇后在棋盘上分布的各种可能的格局数目非常大,约等于2的32次方种,但是,可以将一些明显不满足问题要求的格局排除掉。由于任意两个皇后不能同行,即每行只能放置一个皇后,因此将第i个皇后放在第i行上,这样在放置第i个皇后时,只要考虑它与前i-1个皇后处于不同列和不同对角线位置上即可。

解决这个问题采用回溯法,首先将第一个皇后放置在第一行第一列,然后,依次在下一行上放置一个皇后,直到八个皇后全部放置安全。在放置每个皇后时,都依次对每一列进行检测,首先检测放在第一列是否与已放置的皇后冲突,如不冲突,则将皇后放置在该列,否则,选择该行的下一列进行检测。如整行的八列都冲突,则回到上一行,重新选择位置,依此类推。

1.3 操作手册

运行程序后,首先要输入皇后的个数N:

这里输入4为皇后个数后出现该问题的2种解法:

同样输入6时,会出现4种解法:

每次完成一次解法后可以考虑是否重新输入皇后个数:

1.4 注意事项

  • 每次输入的皇后的个数不要太大,且不能小于等于0

  • 再判断是否重新输入皇后个数时只能输入“Y”或“N”

二、概述

2.1 基本思路

基本思想是采用了提示中的回溯和递归,但并未采用二维数组而是用了一维数组。回溯算法的基本思想是:从一条路往前走,能进则进,不能进则退回来,换一条路再试。而用一维数组的原因是,这样做不仅压缩了空间规模,判断冲突也十分简单。首先每行只有一个皇后,且在数组中只占据一个元素的位置,行冲突就不存在了,其次是列冲突,判断一下是否有a[i]与当前要放置皇后的列j相等即可。至于斜线冲突,通过观察可以发现所有在斜线上冲突的皇后的位置都有规律即它们所在的行列互减的绝对值相等,即| row – i | = | col – a[i] | 。这样某个位置是否可以放置皇后的问题已经解决。

2.2 文件目录

  1. test.cpp (主文件)
  2. test.exe (程序可执行文件)
  3. 设计报告.doc (项目文档)
  4. NQueen.h(头文件)
  5. NQueen.cpp(迷宫相关函数实现)

三、具体实现

3.1 几个全局变量

  1. int sum; // 解法种类数
  2. int Queen[20]; // 各皇后所在行号

3.2 N皇后问题主函数(void NQueen(int iQueen))

将sum置0,并且开始搜寻问题的解决方案。

3.3 放置皇后到棋盘上(void place(int row, int iQueen))

首先进行判断,如果此时的行数row已经大于iQueen皇后个数,则已经找到一种解法,直接展示该解法。否则开始试探row行的每一列,完成该列之后开始进行下一次递归。

3.4 检验第i行的k列上是否可以摆放皇后 (int find(int i, int k))

j=1~i-1是已经放置了皇后的行,当j<i时,判断第j行的皇后是否在k列或(j,Queen[j])与(i,k)是否在斜线上,如果不在,继续检测下一行,如果存在,返回0。

3.5 展示每种解法(void print(int n))

先打印出每种解法中皇后所在位置,从iX=1开始,对应Queen[iX]所存列数,之后通过“X”表示皇后的位置,其余位置用“0”表示,展示棋盘。

上传的附件 cloud_download N皇后问题.7z ( 64.21kb, 15次下载 )
error_outline 下载需要4点积分

发送私信

人生百年,转眼成空。幸福靠的不是缘分,而是珍惜

7
文章数
8
评论数
最近文章
eject