最近在学习C语言,随便编写实现了一个8-皇后问题,同时他程序也可以扩展为N-皇后问题.
8-皇后问题描述:八皇后问题是一个古老而著名的问题,是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解,后来有人用图论的方法解出92种结果。
源代码:
#include <stdio.h>
#include <math.h>
#define N 8
int X[N];
int NUM=0;
int main()
{
void print();
int canPlace(int);
int i;
int k = 0;
X[0] = -1;
while(k>=0)
{
X[k] = X[k]+1;
while(X[k] < N && !canPlace(k))
X[k] = X[k]+1;
if(X[k] < N)//找到位置
{
if(k==N-1)//是否为完整的解
print();
else
{
k++;
X[k] = -1;
}
}
else
k--;
}
return 0;
}
void print()
{
int i;
NUM++;
printf("the %dth answer is :",NUM);
for(i=0;i<N;i++)
{
printf("%d ",X[i]);
}
printf("\n");
}
int canPlace(int k)
{
int i;
for(i=0;i<k;i++)
{
if(X[k] == X[i] || abs(i-k) == abs(X[k]-X[i]))
break;
}
if(i >= k)
return 1;
else
return 0;
}
结果:
the 1th answer is :0 4 7 5 2 6 1 3
the 2th answer is :0 5 7 2 6 3 1 4
the 3th answer is :0 6 3 5 7 1 4 2
the 4th answer is :0 6 4 7 1 3 5 2
the 5th answer is :1 3 5 7 2 0 6 4
the 6th answer is :1 4 6 0 2 7 5 3
the 7th answer is :1 4 6 3 0 7 5 2
the 8th answer is :1 5 0 6 3 7 2 4
the 9th answer is :1 5 7 2 0 3 6 4
the 10th answer is :1 6 2 5 7 4 0 3
the 11th answer is :1 6 4 7 0 3 5 2
the 12th answer is :1 7 5 0 2 4 6 3
the 13th answer is :2 0 6 4 7 1 3 5
the 14th answer is :2 4 1 7 0 6 3 5
the 15th answer is :2 4 1 7 5 3 6 0
the 16th answer is :2 4 6 0 3 1 7 5
the 17th answer is :2 4 7 3 0 6 1 5
the 18th answer is :2 5 1 4 7 0 6 3
the 19th answer is :2 5 1 6 0 3 7 4
the 20th answer is :2 5 1 6 4 0 7 3
the 21th answer is :2 5 3 0 7 4 6 1
the 22th answer is :2 5 3 1 7 4 6 0
the 23th answer is :2 5 7 0 3 6 4 1
the 24th answer is :2 5 7 0 4 6 1 3
the 25th answer is :2 5 7 1 3 0 6 4
the 26th answer is :2 6 1 7 4 0 3 5
the 27th answer is :2 6 1 7 5 3 0 4
the 28th answer is :2 7 3 6 0 5 1 4
the 29th answer is :3 0 4 7 1 6 2 5
the 30th answer is :3 0 4 7 5 2 6 1
the 31th answer is :3 1 4 7 5 0 2 6
the 32th answer is :3 1 6 2 5 7 0 4
the 33th answer is :3 1 6 2 5 7 4 0
the 34th answer is :3 1 6 4 0 7 5 2
the 35th answer is :3 1 7 4 6 0 2 5
the 36th answer is :3 1 7 5 0 2 4 6
the 37th answer is :3 5 0 4 1 7 2 6
the 38th answer is :3 5 7 1 6 0 2 4
the 39th answer is :3 5 7 2 0 6 4 1
the 40th answer is :3 6 0 7 4 1 5 2
the 41th answer is :3 6 2 7 1 4 0 5
the 42th answer is :3 6 4 1 5 0 2 7
the 43th answer is :3 6 4 2 0 5 7 1
the 44th answer is :3 7 0 2 5 1 6 4
the 45th answer is :3 7 0 4 6 1 5 2
the 46th answer is :3 7 4 2 0 6 1 5
the 47th answer is :4 0 3 5 7 1 6 2
the 48th answer is :4 0 7 3 1 6 2 5
the 49th answer is :4 0 7 5 2 6 1 3
the 50th answer is :4 1 3 5 7 2 0 6
the 51th answer is :4 1 3 6 2 7 5 0
the 52th answer is :4 1 5 0 6 3 7 2
the 53th answer is :4 1 7 0 3 6 2 5
the 54th answer is :4 2 0 5 7 1 3 6
the 55th answer is :4 2 0 6 1 7 5 3
the 56th answer is :4 2 7 3 6 0 5 1
the 57th answer is :4 6 0 2 7 5 3 1
the 58th answer is :4 6 0 3 1 7 5 2
the 59th answer is :4 6 1 3 7 0 2 5
the 60th answer is :4 6 1 5 2 0 3 7
the 61th answer is :4 6 1 5 2 0 7 3
the 62th answer is :4 6 3 0 2 7 5 1
the 63th answer is :4 7 3 0 2 5 1 6
the 64th answer is :4 7 3 0 6 1 5 2
the 65th answer is :5 0 4 1 7 2 6 3
the 66th answer is :5 1 6 0 2 4 7 3
the 67th answer is :5 1 6 0 3 7 4 2
the 68th answer is :5 2 0 6 4 7 1 3
the 69th answer is :5 2 0 7 3 1 6 4
the 70th answer is :5 2 0 7 4 1 3 6
the 71th answer is :5 2 4 6 0 3 1 7
the 72th answer is :5 2 4 7 0 3 1 6
the 73th answer is :5 2 6 1 3 7 0 4
the 74th answer is :5 2 6 1 7 4 0 3
the 75th answer is :5 2 6 3 0 7 1 4
the 76th answer is :5 3 0 4 7 1 6 2
the 77th answer is :5 3 1 7 4 6 0 2
the 78th answer is :5 3 6 0 2 4 1 7
the 79th answer is :5 3 6 0 7 1 4 2
the 80th answer is :5 7 1 3 0 6 4 2
the 81th answer is :6 0 2 7 5 3 1 4
the 82th answer is :6 1 3 0 7 4 2 5
the 83th answer is :6 1 5 2 0 3 7 4
the 84th answer is :6 2 0 5 7 4 1 3
the 85th answer is :6 2 7 1 4 0 5 3
the 86th answer is :6 3 1 4 7 0 2 5
the 87th answer is :6 3 1 7 5 0 2 4
the 88th answer is :6 4 2 0 5 7 1 3
the 89th answer is :7 1 3 0 6 4 2 5
the 90th answer is :7 1 4 2 0 6 3 5
the 91th answer is :7 2 0 5 1 4 6 3
the 92th answer is :7 3 0 2 5 1 6 4
分享到:
相关推荐
本资源使用c++代码实现N-皇后问题并附上研究小论文,实现算法有:回溯法(递归),回溯法(递归)的镜像优化,回溯法(非递归),回溯法(非递归)的镜像优化,位运算算法,位运算算法的镜像优化。N-皇后问题是八皇后问题的...
利用Erlang中的并行机制计算N-皇后问题,设计并实现了并行计算N-皇后问题的算法。实验结果表明,该算法有效地提升了多核计算机资源的利用率,提高了求解问题的效率。此外,由于Erlang本身具有数据处理上限只受硬件...
N皇后问题的实现
N皇后问题的3种实现方案
N皇后问题,在一个N×N国际象棋盘 上,有N个皇后,每个皇后占一格;要求皇后间不会出现 相互“攻击”的现象,即不能有两个皇后处在同一行、同一 列或同一对角线上。问共有多少种不同的方法。下图以4 个皇后为例,...
n皇后的c语言实现
可以相比传统N皇后解决增加了运行速度,因为采用二进制进行皇后位置运算,其中图片位置以及图片请自行替换。
n-queens-visualizer, 在反应&通量中,对N 皇后问题可视化的解决 n局部搜索算法的可视化探索queens皇后问题的解。 反应岩石的特征。查看实况:https://haseeb-qureshi.github.io/n-queens-visualizer 用不同的局部...
n 皇后问题是一道经典的回溯算法问题,其目标是在一个 � × � n×n 的棋盘上放置 � n 个皇后,使得任意两个皇后都不能在同一行、同一列或同一斜线上。 栈可以用来辅助实现回溯算法,本质上就是手动维护了递归...
非递归形式的N皇后问题---用C#实现、VS2008可以执行
n皇后问题的没有同义的解。用java语言实现n-queens算法
用java语言实现N皇后问题: 基本思路:X(j)表示一个解的空间,j表示行数,里面的值表示可以放置在的列数,抽象约束条件得到能放置一个皇后的约束条件(1)X(i)!=X(k);(2)abs(X(i)-X(k))!=abs(i-k)。应用回溯法,当可以...
n皇后问题C语言实现:在n*n的棋盘上放置n个皇后,要求皇后两两互斥,即任意两个皇后不能出现在同一行、同一列或同一条斜对角线上。试求出所有的合法布局。
C#实现-回溯求解-N皇后,根据软考书籍中的C代码改写实现C#版的回溯N皇后问题。
C语言实现的,用栈的n皇后问题源码+流程图 深度优先遍历
vb实现N皇后问题,操作简单,容易理解!
在一个N×N的国际象棋棋盘中摆N个皇后,使这N个皇后不能互相被对方吃掉。N皇后问题摆法算法描述
下面是使用C++语言实现的N皇后问题的解决方案。 类的设计 在解决N皇后问题时,我们可以使用面向对象的设计思想设计一个名为Queen的类,该类具有以下几个重要的成员变量和成员函数: * 成员变量:num(表示N皇后...
回溯法实现N皇后问题 利用Java中Swing实现的界面比较抽象,但是基本功能还是实现了