对八皇后问题的拓展探究
至繁归于至简,这次自己仍然用尽可能易理解和阅读的解决方式。
1、问题说明:
西洋棋中的皇后可以直线前进,吃掉遇到的所有棋子,如果棋盘上有八个皇后,则这八个皇后如何相安无事的放置在棋盘上,1970年与1971年,E.W.Dijkstra与N.Wirth曾经用这个问题来讲解程式设计之技巧。
2、解法:
关于棋盘的问题,都可以用递回求解,然而如何减少递回的次数?在八个皇后的问题中,不必要所有的格子都检查过,例如若某列检查过,该该列的其它格子就不用再检查了,这个方法称为分支修剪。下面自己写的的具体代码,以棋盘上的八皇后为例,修改下面的N = 8,即可从八皇后问题拓展至此类所有的棋盘问题。
3、具体代码:
/**
* @Title 对八皇后问题的拓展探究
* @Author 孙琨
* @Date 2013-11-18
* @At XUST
* @All Copyright by 孙琨
*
*/
#include <iostream>
using namespace std;
#define N 8
int column[N + 1]; // 同栏是否有皇后,1表示有
int rup[2 * N + 1]; // 右上至左下是否有皇后
int lup[2 * N + 1]; // 左上至右下是否有皇后
int queen[N + 1] = {0};
int num; // 解答编号
void backtrack(int); // 递归求解
int main(void)
{
int i;
num = 0;
for(i=1; i<=N; i++)
column[i] = 1;
for(i=1; i<=2*N; i++)
rup[i] = lup[i] = 1;
backtrack(1);
cout <<endl << N << "个皇后在棋盘上总共有" << num << "种排法" << endl;
return 0;
}
void showAnswer()
{
int x,y;
cout << endl << "解答 " << ++num << endl;
for(y=1; y<=N; y++)
{
for(x=1; x<=N; x++)
{
if(queen[y] == x) // 放置皇后
cout << "●";
else
cout << "○";
}
cout << endl;
}
}
void backtrack(int i)
{
int j;
if(i > N)
{
showAnswer();
}
else
{
for(j=1; j<=N; j++)
{
if(column[j]==1 && rup[i+j]==1 && lup[i-j+N]==1)
{
queen[i] = j;
// 设定为占用
column[j] = rup[i+j] = lup[i-j+N] = 0;
backtrack(i+1);
column[j] = rup[i+j] = lup[i-j+N] = 1;
}
}
}
}
4、结果部分截图:
分享到:
相关推荐
基于深度优先算法的八皇后问题的实现及消除重复的拓展,内容包括文档和代码
八皇后问题八皇后问题八皇后问题八皇后问题八皇后问题八皇后问题八皇后问题八皇后问题八皇后问题
八皇后问题的拓展,可以输出任意N*N棋盘上N个皇后的摆放位置
八皇后问题 c++ 八皇后问题 c++ 八皇后问题 c++
作业代码,汇编写八皇后问题,自己写了一份,在网上找的也在里面
linux c语言实现八皇后问题。希望对你的学习
解决八皇后问题。利用mfc加了界面,输出结果放在一个文档中。
解决八皇后问题的源码,带有注释,由于数据结构即算法的学习,如有其他需要,请留言
八皇后问题课程设计论文
求解八皇后问题的一种算法,是用二维数组模拟了一个棋盘,每种结果都会输出来其中皇后的位置用"2"表示,其他位置用0或1表示。
八皇后问题 数据结构八皇后问题 数据结构八皇后问题 数据结构八皇后问题 数据结构八皇后问题 数据结构八皇后问题 数据结构八皇后问题 数据结构
八皇后问题 递归算法 可以输入皇后的值 输出排列的结果
经典的算法,八皇后问题,c++实现,回溯法
C语言八皇后问题
一个C语言编写的求解八皇后问题,用回朔法实现
个人写的一个八皇后问题,有需要的,可以下载。用C++编写的!
八皇后问题 ,程序代码 八皇后问题 ,程序代码 八皇后问题 ,程序代码
八皇后问题的两种解法,包含c方式和c++方式
八皇后问题 最简单dfs模板代码八皇后问题 最简单dfs模板代码八皇后问题 最简单dfs模板代码八皇后问题 最简单dfs模板代码八皇后问题 最简单dfs模板代码八皇后问题 最简单dfs模板代码八皇后问题 最简单dfs模板代码八...