八皇后问题程序

#include<stdioh>

#include<mathh>

#include<stringh>

#include<stdlibh>

int printed;

void draw(int a,int k)

{

int i,j;

for(i=0;i<k;i++)

{

printf("\t");

for(j=0;j<k;j++)

if(a[i]-1==j) printf("Q "); else printf("- ");

printf("\n");

}

printf("\n");

}

void Settle(int a,int iStep,int k)

{

int i,j,l,flag=1;

for(i=0;i<iStep-1;i++)

if(a[iStep-1]==a[i]) return;

if(iStep==k) 

{

for(j=0;j<k;j++)

for(l=0;l<k&&l!=j;l++)

if(fabs(j-l)==fabs(a[j]-a[l])) flag=0;

if(flag)

{

for(i=0;i<k;i++)

printf("(%d,%d) ",i+1,a[i]);

printf("\n");

draw(a,k);

printed++;

}

flag=1;

}

for(i=1;i<=k;i++)

{

a[iStep]=i;

Settle(a,iStep+1,k);

}

}

void main()

{

int a;

int k;

printf("Enter the size of the square:");

scanf("%d",&k);

a=(int)calloc(k,sizeof(int));

system("cls");

Settle(a,0,k);

if(! printed) printf("No answers accepted!\n");

else printf("%d states available!\n",printed);

}

//这是用C语言实现的，主要是递归全排列，具体不会的再问我吧^^

回溯法:八皇后问题，一个经典问题

在程序设计中还有一种方法叫做"回溯法"他不是按照某种公式或确定的法则,求问题的解,而是通过试探和纠正错误的策略,找到问题的街这种方法一般是从一个原始状态出发,通过若干步试探,最后达到目标状态终止

回溯法在理论上来说,就是在一棵搜索树中从根结点出发,找到一条达到满足某条件的子结点的路径在搜索过程中,对于每一个中间结点,他的位置以及向下搜索过程是相似的,因此完全可以用递归来处理典型的例子就是著名的"八皇后问题"

"八皇后问题"是在国际象棋棋盘上放置八个皇后,使她们不能相吃国际象棋中的皇后可以吃掉与她处于同一行,同一列,同一对角线上的棋子因此每一行只能摆放一个皇后因共有八行,所以每行有且只有一个皇后

在本例中皇后的位置有一个一维数组来存放A(I)=J表示第I行皇后放在第J列下面主要来看看怎么样判断皇后是否安全的问题(1)首先,用一维数组来表示,已经解决了不在同一行的问题(2)对于列可以引进一个标志数组C[J],若J列上已放了皇后,则C[J]=FALSE(3)对于左上右下的对角线I-J为一常量,位于[-7,+7]之间,再此引入标志数组L[-77];对于左下右上的对角线,类似的有I+J等于常量,用数组R[216]来表示当在第I行,第J列上放置了皇后,则只需设置:C[J]:=FALSE; L[I-J]:=FLASE; R[I+J]:=FALSE就可以解决皇后的安全问题了

问题描述：在标准国际象棋的棋盘上（88格）准备放置8只皇后，我们知道，国际象棋中皇后的威力是最大的，她既可以横走竖走，还可以斜着走，遇到挡在她前进路线上的敌人，她就可以吃掉对手。要求在棋盘上安放8只皇后，使她们彼此互相都不能吃到对方，求皇后的放法。

//

/ /

/ 问题：在8×8的国际象棋棋盘上放置8个皇后，要求任意两个皇后 /

/ 不能在同一行、同一列或同一条对角线上。 /

/ /

/ 本程序使用递归－回溯法求解8皇后问题。Visual C++ 60 调试通过。 /

/ 作者 晨星 2002年5月9日 /

/ /

//

#include <stdioh>

#include <conioh>

#include <mathh>

#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=0; i<slength(); i++) {

bool safe=true;

for (int j=0;j<tlength();j++) {

if (tlength()-j==abs(s[i]-t[j])) safe=false;

}

if (safe) queen(t+s[i], ssubstr(0,i)+ssubstr(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=0;i<8;i++)

for(j=0;j<8;j++)

{

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-1;j>=0;j--)

if(Chessboard[LocX][j] != 'X')

return 0;

for(j=LocY+1;j<8;j++)

if(Chessboard[LocX][j] != 'X')

return 0;

for(i=LocX-1;i>=0;i--)

if(Chessboard[i][LocY] != 'X')

return 0;

for(i=LocX+1;i<8;i++)

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=0;i<8;i++)

for(j=0;j<8;j++)

Chessboard[i][j] = 'X';

N_Queens(0,0,0);

printf("the graph of 8 Queens on the Chessboardis:n");

for(i=0;i<8;i++)

for(j=0;j<8;j++)

{

if(Chessboard[i][j] == 'Q')

printf("(%d,%d)n",i,j);

}

getch();

}

/

八皇后问题

根据严书给的类c算法求得

/

#include<stdioh>

#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=0;k<N;k++)

{

for(l=0;l<N;l++)

{

if(a[k][l]==1)

printf("@");

else printf("");

}

printf("n");

}

printf("nn");

getchar();

}

else

{

for(j=0;j<N;j++)

{

for(k=0;k<i;k++)

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=1;slash=1;bslash=1;

a[i][j]=0;

}

}

}

void main()

{

trial(0);

printf("%dn",num);

getchar();

}

TurboC 图形演示 八皇后 分步过程, 红色为当前挪动棋子

出现一种结果 棋盘颜色变为亮白色

空格键开关分步演示, ESC 退出

#include <mathh>

#include <conioh>

#include <stdioh>

#include <stdlibh>

#include <graphicsh>

#define SIZE 8

void drawb(int x, int y, int color1, int color2);

void drawqueen(int x, int y, int color);

void Backtrack(int t, int n, int x);

int place(int k, int x);

int main(void)

{

int GraphDriver;

int GraphMode;

int i, j, x, y;

int queenlist[SIZE + 1];

x = 70;

y = 30;

GraphDriver = DETECT;

initgraph(&GraphDriver, &GraphMode, "");

drawb(x, y, 7, 1);

getch();

Backtrack(1, SIZE, queenlist);

}

void drawb(int x, int y, int color1, int color2)

{

int i, j;

char buffer[2] = {"0"};

for (i = 0; i < SIZE; i++)

{

for (j = 0; j < SIZE; j++)

{

setfillstyle(SOLID_FILL, ((i % 2 == 0 && j % 2 == 0) || (i % 2 != 0 && j % 2 != 0)) color1 : color2);

bar(x + i 49, y + j 49, x + i 49 + 48, y + j 49 + 48);

}

}

setcolor(15);

for (i = 0; i < SIZE; i++)

{

buffer[0]++;

outtextxy(x - 15, y + i 49 + 20, buffer);

}

buffer[0] = 'A';

for (i = 0; i < SIZE; i++)

{

outtextxy(x + i 49 + 20, y + 402, buffer);

buffer[0]++;

}

}

void drawqueen(int x, int y, int color)

{

setcolor(color);

setfillstyle(SOLID_FILL, color);

moveto(x 49 + 39, y 49 + 11);

lineto(x 49 + 39, y 49 - 11);

lineto(x 49 + 51, y 49 - 11);

lineto(x 49 + 51, y 49 + 11);

lineto(x 49 + 59, y 49 + 19);

lineto(x 49 + 31, y 49 + 19);

lineto(x 49 + 39, y 49 + 11);

floodfill(x 49 + 50, y 49 + 12, color);

}

int place(int k, int x)

{

int j;

for(j = 1; j < k; j++)

if ((abs(k - j) == abs(x[j] - x[k])) || (x[j] == x[k]))

return 0;

return 1;

}

void Backtrack(int t, int n, int x)

{

int i;

int a, b;

static int step = 1;

if (t > n)

{

drawb(70, 30, 15, 1);

for (i = 1; i <= n; i++)

{

drawqueen(i, x[i], 0);

}

a = getch();

if (a == 0)

a = getch();

else if (a == 27)

{

closegraph();

exit(0);

}

else if (a == 32)

{

step = 1 - step;

}

}

else

for(i = 1; i <= n; i++)

{

x[t] = i;

if (step == 1)

{

drawb(70, 30, 7, 1);

for (a = 1; a <= t; a++)

{

drawqueen(a, x[a], (a == t) 12 : 0);

}

a = getch();

if (a == 27)

{

closegraph();

exit(0);

}

else if (a == 32)

{

step = 1 - step;

}

}

if (place(t, x))

Backtrack(t + 1, n, x);

}

}

八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。 对于八皇后问题的实现，如果结合动态的图形演示，则可以使算法的描述更形象、更生动，使教学能产生良好的效果。下面是用Turbo C实现的八皇后问题的图形程序，能够演示全部的92组解。八皇后问题动态图形的实现

以上就是关于八皇后问题程序全部的内容，包括:八皇后问题程序、八皇后c++源码讲解、八皇后问题等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！