#include <stdio.h>
#include <time.h>
#include <stdlib.h>
int cells[64]/*存储摆放方案，一维数组视为二维棋盘*/
int num=0/*记录尝试次数*/
int output()/*输出棋盘状态*/{
static int count=0/*静态变量计录本次输出的编号*/
int t=0,m,n/*辅助计算黑白格的选取*/
count++
printf("方案%d：\r\n",count)
for(m=0m<8m++){
for(n=0n<8n++){
t++
if(cells[n+m*8]==0){/*没有皇后*/
t%2?printf("□"):printf("■")/*根据奇偶与否决定输出格子黑白*/
}else{/*有皇后*/
printf("★")
}
}
t++/*偏移，使黑白格交错*/
printf("\r\n")
}
if(count==30||count==60)system("pause")
return 0
}
int ok(int i)/*递归判断第i行的落子可行性*/{
int k,j,t1,t2,r/*临时变量，作用随机*/
for(k=0k<8k++){/*从行首开始向后轮流判断*/
r=0num++/*r存储是否存在冲突，非0则为冲突*/
for(j=0j<8j++){/*清空该行可能的棋子，避免由子过程返回后产生的冲突。*/
cells[j+i*8]=0
}
for(j=0j<ij++){/*纵向判断*/
if(cells[k+j*8]) r=1
}
t2=t1=k+i*8/*t1、t2临时存储斜向游标位置*/
t1-=9/*向左上方对角线偏移一格*/
while(t1%8!=7&&t1>=0){/*斜线上仍有格子*/
if(cells[t1]){r=1break}/*斜向存在冲突*/
t1-=9/*继续移动*/
}
t2-=7/*同理*/
while(t2%8!=0&&t2>=0){
if(cells[t2]){r=1break}
t2-=7
}
if(!r){/*没有发生冲突*/
cells[k+i*8]=1/*确认落子*/
if(i<7){/*没有落完八个皇后*/
ok(i+1)/*继续在下一行寻找方案*/
}else{/*落子成功结束*/
output()/*输出棋盘状况*/
}
}
}
return 0
}
int main()/*应用程序入口，不解释*/{
int i/*临时变量，用于初始化棋盘*/
double a,b,c/*计时用*/
printf(Q)
printf("什么？八皇后？小case，马上给出答案～～\r\n")
for(i=0i<64i++){/*棋盘初始化*/
cells[i]=0
}
a=clock()/*开始时间*/
ok(0)/*运算*/
b=clock()/*结束时间*/
printf("\r\n回答完毕！\r\n")
c=(double)(b-a)/CLOCKS_PER_SEC/*计算时间间隔*/
printf("经过%i次尝试，耗时%f秒，表示没有鸭梨……\r\n\r\n",num,c)
return 0
}
如下是8皇后的程序：#include<stdio.h>
#include<stdlib.h>
void eightqueen(int a[][99],int n)
void print(int a[][99])
int up(int a[][99],int row,int col)
int down(int a[][99],int row,int col)
int left(int a[][99],int row,int col)
int right(int a[][99],int row,int col)
int num=0
main()
{
int a[99][99]={0},n //将皇后的位置放在一个二维的数组里面，a[i][j]=1表示该位置有一个皇后
eightqueen(a,0)
system("pause")
return 0
}
void print(int a[][99]) //输出当前的一种合理的走法。
{
int i,row,col
printf("Case %d\n",num)
for(row=0row<8row++)
{
for(col=0col<8col++)
{
printf("%d ",a[row][col])
}
printf("\n")
}
printf("\n")
}
void eightqueen(int a[][99],int row) //通过回溯法计算8皇后的走法。
{
int col,i
for(col=0col<=7col++)
{
//判断都前位置是否是合理的位置。
if ((up(a,row,col)==0)&&(down(a,row,col)==0)&&(left(a,row,col)==0)&&(right(a,row,col)==0))
{
a[row][col]=1//如果是，将当前位置置为1（摆放一个皇后）
if(row==7) //所有的8个皇后都已经摆放好了，输出当前的情况。
{
num++
print(a)
}
else
{
eightqueen(a,row+1)//在row+1摆放下一个皇后。
}
a[row][col]=0
}
}
}
//判断同一行列是否有其他的皇后
int up(int a[][99],int row,int col)
{
int i
for(i=0i<8i++)
{
if(a[i][col]==1)
{
return 1
}
}
return 0
}
//判断同一行上是否有其他的皇后
int down(int a[][99],int row,int col)
{
int i
for(i=0i<8i++)
{
if(a[row][i]==1)
{
return 1
}
}
return 0
}
//判断左上到右下的对接线上是否有其他的皇后
int left(int a[][99],int row,int col)
{
int i
for(i=0i<8i++)
{
if(((row+i)<8)&&((col+i)<8))
{
if(a[row+i][col+i]==1)
{
return 1
}
}
if(((row-i)>=0)&&((col-i)>=0))
{
if(a[row-i][col-i]==1)
{
return 1
}
}
}
return 0
}
//判断左下到右上的对接线上是否有其他的皇后
int right(int a[][99],int row,int col)
{
int i
for(i=0i<8i++)
{
if(((row+i)<8)&&((col-i)>=0)) //
{
if(a[row+i][col-i]==1)
{
return 1
}
}
if(((row-i)>=0)&&((col+i)<8)) //这儿的判断有问题，
{
if(a[row-i][col+i]==1)
{
return 1
}
}
}
return 0
}
回溯法:八皇后问题，一个经典问题在程序设计中还有一种方法叫做"回溯法".他不是按照某种公式或确定的法则,求问题的解,而是通过试探和纠正错误的策略,找到问题的街.这种方法一般是从一个原始状态出发,通过若干步试探,最后达到目标状态终止.
回溯法在理论上来说,就是在一棵搜索树中从根结点出发,找到一条达到满足某条件的子结点的路径.在搜索过程中,对于每一个中间结点,他的位置以及向下搜索过程是相似的,因此完全可以用递归来处理.典型的例子就是著名的"八皇后问题".
"八皇后问题"是在国际象棋棋盘上放置八个皇后,使她们不能相吃.国际象棋中的皇后可以吃掉与她处于同一行,同一列,同一对角线上的棋子.因此每一行只能摆放一个皇后.因共有八行,所以每行有且只有一个皇后.
在本例中皇后的位置有一个一维数组来存放A(I)=J表示第I行皇后放在第J列.下面主要来看看怎么样判断皇后是否安全的问题.(1)首先,用一维数组来表示,已经解决了不在同一行的问题.(2)对于列可以引进一个标志数组C[J],若J列上已放了皇后,则C[J]=FALSE.(3)对于左上右下的对角线I-J为一常量,位于[-7,+7]之间,再此引入标志数组L[-7..7]对于左下右上的对角线,类似的有I+J等于常量,用数组R[2..16]来表示.当在第I行,第J列上放置了皇后,则只需设置:C[J]:=FALSEL[I-J]:=FLASER[I+J]:=FALSE就可以解决皇后的安全问题了.
问题描述：在标准国际象棋的棋盘上（8*8格）准备放置8只皇后，我们知道，国际象棋中皇后的威力是最大的，她既可以横走竖走，还可以斜着走，遇到挡在她前进路线上的敌人，她就可以吃掉对手。要求在棋盘上安放8只皇后，使她们彼此互相都不能吃到对方，求皇后的放法。
/************************************************************************/
/* */
/*问题：在8×8的国际象棋棋盘上放置8个皇后，要求任意两个皇后 */
/* 不能在同一行、同一列或同一条对角线上。 */
/* */
/*本程序使用递归－回溯法求解8皇后问题。Visual C++ 6.0 调试通过。 */
/*作者 晨星 2002年5月9日 */
/* */
/************************************************************************/
#include <stdio.h>
#include <conio.h>
#include <math.h>
#define QUEENS 8
//!记录解的序号的全局变量。
int iCount = 0
//!记录皇后在各列上的放置位置的全局数组。
int Site[QUEENS]
//!递归求解的函数。
void Queen(int n)
//!输出一个解。
void Output()
//!判断第n个皇后放上去之后，是否有冲突。
int IsValid(int n)
/*----------------------------Main：主函数。 ----------------------------*/
void main()
{
//!从第0列开始递归试探。
Queen(0)
//!按任意键返回。
getch()
}
/*-----------------Queen：递归放置第n个皇后，程序的核心!----------------*/
void Queen(int n)
{
int i
//!参数n从0开始，等于8时便试出了一个解，将它输出并回溯。
if(n == QUEENS)
{
Output()
return
}
//!n还没到8，在第n列的各个行上依次试探。
for(i = 1 i <= QUEENS i++)
{
//!在该列的第i行上放置皇后。
Site[n] = i
//!如果放置没有冲突，就开始下一列的试探。
if(IsValid(n))
Queen(n + 1)
}
}
/*------IsValid：判断第n个皇后放上去之后，是否合法，即是否无冲突。------*/
int IsValid(int n)
{
int i
//!将第n个皇后的位置依次于前面n－1个皇后的位置比较。
for(i = 0 i <n i++)
{
//!两个皇后在同一行上，返回0。
if(Site[i] == Site[n])
return 0
//!两个皇后在同一对角线上，返回0。
if(abs(Site[i] - Site[n]) == (n - i))
return 0
}
//!没有冲突，返回1。
return 1
}
/*------------Output：输出一个解，即一种没有冲突的放置方案。------------*/
void Output()
{
int i
//!输出序号。
printf("No.%-5d" , ++iCount)
//!依次输出各个列上的皇后的位置，即所在的行数。
for(i = 0 i <QUEENS i++)
printf("%d " , Site[i])
printf("n")
}
STL源代码
用了STL, 方法是一样的.
#include <iostream>
#include <string>
using namespace std
void queen(const string t, const string s)
{
if (s=="") cout<<t<<endl
else
for (int i=0i<s.length()i++) {
bool safe=true
for (int j=0j<t.length()j++) {
if (t.length()-j==abs(s[i]-t[j])) safe=false
}
if (safe) queen(t+s[i], s.substr(0,i)+s.substr(i+1))
}
}
int main()
{
string s="01234567"
queen("",s)
system("PAUSE")
exit(EXIT_SUCCESS)
}
递归解八皇后问题
/*递归法解八皇后问题*/
/*作者黄国瑜，《数据结构（C语言版）》清华大学出版社*/
char Chessboard[8][8]/*声明8＊8的空白棋盘*/
int N_Queens(int LocX, int LocY, int Queens) /*递归*/
{
int i,j
int Result=0
if(Queens == 8)/*递归结束条件*/
return 1
else if(QueenPlace(LocX,LocY))/*递归执行部分*/
{
Chessboard[LocX][LocY] = 'Q'
for(i=0i<8i++)
for(j=0j<8j++)
{
Result += N_Queens(i,j,Queens+1)
if(Result>0)
break
}
if(Result>0)
return 1
else
{
Chessboard[LocX][LocY] = 'X'
}
}
else
return 0
}
int QueenPlace(int LocX,int LocY) /*判断传入坐标本身及入八个方向上是否有皇后*/
{
int i,j
if(Chessboard[LocX][LocY] != 'X')
return 0
for(j=LocY-1j>=0j--)
if(Chessboard[LocX][j] != 'X')
return 0
for(j=LocY+1j<8j++)
if(Chessboard[LocX][j] != 'X')
return 0
for(i=LocX-1i>=0i--)
if(Chessboard[i][LocY] != 'X')
return 0
for(i=LocX+1i<8i++)
if(Chessboard[i][LocY] != 'X')
return 0
i= LocX - 1
j= LocY - 1
while (i>=0&&j>=0)
if(Chessboard[i--][j--] != 'X')
return 0
i= LocX + 1
j= LocY - 1
while (i<8&&j>=0)
if(Chessboard[i++][j--] != 'X')
return 0
i= LocX - 1
j= LocY + 1
while (i>=0&&j<8)
if(Chessboard[i--][j++] != 'X')
return 0
i= LocX + 1
j= LocY + 1
while (i<8&&j<8)
if(Chessboard[i++][j--] != 'X')
return 0
return 1
}
main() /*主程序*/
{
int i,j
for(i=0i<8i++)
for(j=0j<8j++)
Chessboard[i][j] = 'X'
N_Queens(0,0,0)
printf("the graph of 8 Queens on the Chessboard.is:n")
for(i=0i<8i++)
for(j=0j<8j++)
{
if(Chessboard[i][j] == 'Q')
printf("(%d,%d)n",i,j)
}
getch()
}
/*********************************************************
*****************八皇后问题*******************************
************根据严书给的类c算法求得************************
*********************************************************/
#include<stdio.h>
#define N 8
int col=1,row=1,slash=1,bslash=1
int a[N][N]
int p,q,k,l
int num=0
void trial(int i)
{
int j /*注 意，这里的j 一定要设为内部变量*/
if(i==N)
{
num++
for(k=0k<Nk++)
{
for(l=0l<Nl++)
{
if(a[k][l]==1)
printf("@")
else printf("*")
}
printf("n")
}
printf("nn")
getchar()
}
else
{
for(j=0j<Nj++)
{
for(k=0k<ik++)
if(a[k][j]==1)
{
col=0
break
} /*列*/
p=i-1
q=j+1
while((p>=0)&&(q<N))
{
if(a[p][q]==1)
{
slash=0
break
}
p--
q++
}
p=i-1
q=j-1/*对角*/
while((p>=0)&&(q>=0))
{
if(a[p][q]==1)
{
bslash=0
break
}
p--
q--
} /*斜对角*/
if((col==1)&&(slash==1)&&(bslash==1)) /*条件判断*/
{
a[i][j]=1
trial(i+1)
}
col=1slash=1bslash=1
a[i][j]=0
}
}
}
void main()
{
trial(0)
printf("%dn",num)
getchar()
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）