八皇后问题（递归求解）

小甲鱼 · 发表于 2013-3-2 03:00:53

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

八皇后问题，是一个古老而著名的问题，是回溯算法的典型例题（这节课小甲鱼先用递归算法来解）。

该问题是十九世纪著名的数学家高斯1850年提出：

在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

高斯先生当年由于没有学好计算机编程，没日没夜地计算呀，得出结论是76种，硬生生把自己给“搞死”了！

对了，当年还没有计算机……

视频讲解：http://blog.fishc.com/2228.html

源代码参考：http://bbs.fishc.com/thread-28183-1-1.html

牡丹花下死做鬼 · 发表于 2013-3-9 07:01:46

下载看看虽然目前对递归还不怎么了解

兢兢 · 发表于 2013-7-12 10:28:59

Dim a(8, 8)
For i = 0 To 7
For j = 0 To 7
      a(i, j) = 0
Next
Next
num=1
For n0 = 0 To 7
a(0, n0) = 1
hang0=n0
For n1 = 0 To 7
      If safe(1, n1) = 1 Then
         a(1, n1) = 1
         hang1=n1
         For n2 = 0 To 7
            If safe(2, n2) = 1 Then
                  a(2, n2) = 1
                  hang2=n2
                  For n3 = 0 To 7
                     If safe(3, n3) = 1 Then
                        a(3, n3) = 1
                        hang3=n3
                        For n4 = 0 To 7
                              If safe(4, n4) = 1 Then
                                 a(4, n4) = 1
                                 hang4=n4
                                 For n5 = 0 To 7
                                    If safe(5, n5) = 1 Then
                                          a(5, n5) = 1
                                          hang5=n5
                                          For n6 = 0 To 7
                                             If safe(6, n6) = 1 Then
                                                a(6, n6) = 1
                                                hang6=n6
                                                For n7 = 0 To 7
                                                      If safe(7, n7) = 1 Then
                                                         a(7, n7) = 1
                                                         hang7=n7
                                                         Call printf()
                                                         num=num+1
                                                      End If
                                                Next
                                                a(7, hang7) = 0
                                             End If
                                             a(6, hang6) = 0
                                          Next
                                    End If
                                    a(5, hang5) = 0
                                 Next
                              End If
                              a(4, hang4) = 0
                        Next
                     End If
                     a(3, hang3) = 0
                  Next
            End If
            a(2, hang2) = 0
         Next
      End If
      a(1, hang1) = 0
Next
a(0, hang0) = 0
Next
Sub printf()
p=""
For i = 0 To 7
      For j = 0 To 7
         P = P & CStr(a(i, j)) & " "
      Next
      P = P & vbCrLf
Next
MsgBox p, vbokonly, "第" & num & "种皇后位置！"
End Sub
Function safe(x, y)
For h= 0 To 7
      For l = 0 To 7
         If a(h, l) = 1 Then
            If (h = x) or (l=y) or ((h - l)= (x - y)) or ((h + l) = (x + y)) Then
                  safe = 0
                  Exit Function
            Else
                  safe = 1
            End If
         End If
      Next
Next
End Function

a764934018 · 发表于 2013-8-7 19:27:27

提示: 作者被禁止或删除内容自动屏蔽

じO-联合 · 发表于 2014-2-18 11:05:59

强烈支持楼主ing……

andalousie · 发表于 2014-2-22 13:10:51

看我同学写的八皇后，多么雷人。。。

#include <iostream>
#include <string>
using namespace std;
int pd(int i,int h[30][30],int j)
{
int t;
t=h[i][j]*h[i][j+1]*h[i][j+2]*h[i][j+3]*h[i][j+4]*h[i][j+5]*h[i][j+6]*h[i][j+7]*h[i][j+8];//列
t=t*h[i][j-1]*h[i][j-2]*h[i][j-3]*h[i][j-4]*h[i][j-5]*h[i][j-6]*h[i][j-7]*h[i][j-8];//列
t=t*h[i+1][j]*h[i+2][j]*h[i+3][j]*h[i+4][j]*h[i+5][j]*h[i+6][j]*h[i+7][j]*h[i+8][j];//行
t=t*h[i-1][j]*h[i-2][j]*h[i-3][j]*h[i-4][j]*h[i-5][j]*h[i-6][j]*h[i-7][j]*h[i-8][j];//行
t=t*h[i+1][j+1]*h[i+2][j+2]*h[i+3][j+3]*h[i+4][j+4]*h[i+5][j+5]*h[i+6][j+6]*h[i+7][j+7]*h[i+8][j+8];//xie
t=t*h[i-1][j+1]*h[i-2][j+2]*h[i-3][j+3]*h[i-4][j+4]*h[i-5][j+5]*h[i-6][j+6]*h[i-7][j+7]*h[i-8][j+8];//xie
t=t*h[i+1][j-1]*h[i+2][j-2]*h[i+3][j-3]*h[i+4][j-4]*h[i+5][j-5]*h[i+6][j-6]*h[i+7][j-7]*h[i+8][j-8];//xie
t=t*h[i-1][j-1]*h[i-2][j-2]*h[i-3][j-3]*h[i-4][j-4]*h[i-5][j-5]*h[i-6][j-6]*h[i-7][j-7]*h[i-8][j-8];//xie
return t;
}
int main()
{
int h[30][30];
for (int qqq=0;qqq<30;qqq++)
{
for(int qq=0;qq<30;qq++)
{
h[qqq][qq]=1;
}
}
int n,m,k;
int y,e,sa,si,w,l,q,b,sum;
sum=0;
for (y=11;y<=18;y++)
{
h[11][y]=0;//11
for (e=11;e<=18;e++)
{
if(pd(12,h,e)==0)//12
{
}
else
{
h[12][e]=0;
for(sa=11;sa<=18;sa++)//13
{
if(pd(13,h,sa)==0)
{
}
else
{
h[13][sa]=0;
for (si=11;si<=18;si++)//14
{
if(pd(14,h,si)==0)
{
}
else
{
h[14][si]=0;
for(w=11;w<19;w++)//15
{
if(pd(15,h,w)==0)
{
}
else
{
h[15][w]=0;
for (l=11;l<=18;l++)//16
{
if(pd(16,h,l)==0)
{
}
else
{
h[16][l]=0;
for (q=11;q<=18;q++)//17
{
if(pd(17,h,q)==0)
{
}
else
{
h[17][q]=0;
for (b=11;b<=18;b++)//18
{
if(pd(18,h,b)==0)
{
}
else
{
sum++;
h[18][b]=0;
for (k=11;k<19;k++)
{
cout<<h[11][k];
}
cout<<endl;
for (k=11;k<19;k++)
{
cout<<h[12][k];
}
cout<<endl;
for (k=11;k<19;k++)
{
cout<<h[13][k];
}
cout<<endl;
for (k=11;k<19;k++)
{
cout<<h[14][k];
}
cout<<endl;
for (k=11;k<19;k++)
{
cout<<h[15][k];
}
cout<<endl;
for (k=11;k<19;k++)
{
cout<<h[16][k];
}
cout<<endl;
for (k=11;k<19;k++)
{
cout<<h[17][k];
}
cout<<endl;
for (k=11;k<19;k++)
{
cout<<h[18][k];
}
cout<<endl;
cout<<" "<<endl;
cout<<" "<<endl;
cout<<" "<<endl;
}
}
for (n=18;n<30;n++)
{
for(m=0;m<30;m++)
{
h[n][m]=1;
}
}
h[17][q]=1;
}
}
h[16][l]=1;
for (n=17;n<30;n++)
{
for(m=0;m<30;m++)
{
h[n][m]=1;
}
}
}
}
h[15][w]=1;
for (n=16;n<30;n++)
{
for(m=0;m<30;m++)
{
h[n][m]=1;
}
}
}
}
h[14][si]=1;
for (n=15;n<30;n++)
{
for(m=0;m<30;m++)
{
h[n][m]=1;
}
}
}
}
h[13][sa]=1;
for (n=14;n<30;n++)
{
for(m=0;m<30;m++)
{
h[n][m]=1;
}
}
}
}
h[12][e]=1;
for (n=13;n<25;n++)
{
for(m=0;m<30;m++)
{
h[n][m]=1;
}
}
}
}
for (n=12;n<30;n++)
{
for(m=0;m<30;m++)
{
h[n][m]=1;
}
}
h[11][y]=1;
}
cout<<sum<<endl;
return 0;
}

复制代码

小甲鱼 · 发表于 2014-2-22 16:45:48

andalousie 发表于 2014-2-22 13:10

登录/注册后可看大图

看我同学写的八皇后，多么雷人。。。

雅蠛蝶，一个比一个经典！！！

杨延平 · 发表于 2014-4-17 17:47:24

请求楼主帮忙
我的问题：八皇后我的理解是把所有结果遍历一遍楼主的代码从1——7行都有 for(i=0;i<8;++i){EightQuee}
的遍历为什么第一行只遍历了一次为什么结果不是8*92

阿衡 · 发表于 2014-5-4 20:07:53

强烈支持楼主ing……

请问11 · 发表于 2014-10-23 17:39:45

请问11 · 发表于 2014-10-23 17:47:41

{:1_1:}

DESTINY1002 · 发表于 2014-12-1 21:58:23

andalousie 发表于 2014-2-22 13:10
看我同学写的八皇后，多么雷人。。。

神人也~~~受我膜拜~~~~

weberwang · 发表于 2015-1-15 11:36:29

真是难得给力的帖子啊。

Einsteng · 发表于 2016-7-14 17:06:25

八皇后
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<conio.h>
#define N 8 //皇后数=棋盘行列数
int a[N]; //a[i]为第i行皇后所在列
void show() //图形化输出
{
int i;
int p,q ;
int b[N][N]={0};
static int t=1;
printf("第%d个解为: ",t++);
for(i=0;i<N;i++)
{
      b[i][a[i]]=1;
      printf("(%d,%d) ",i,a[i]);
}
printf("\n");
for(p=0;p<N;p++)
{
      for(q=0;q<N;q++)
      {
         if(b[p][q]==1)
            printf("●");
         else
            printf("○");
      }
      printf("\n");
}
}
int check(int n) //满足条件返回1，否则返回0
{
int i;
for(i=0;i<n;i++)
{
      if(a[i]==a[n]||fabs(n-i)==fabs(a[i]-a[n])) //at the same column or diagonal (对角线)
         return 0;
}
return 1;
}
void put(int n) //在第n行放置第n个皇后
{
int i;
if(n==N)
      return ;
for(i=0;i<N;i++)
{
      a[n]=i;
      if(check(n)) //位置合法
      {
         if(n==N-1) //皇后全部放置完毕
            show();
         else
            put(n+1);
      }
}
}
int main ()
{
put(0);
return 0;
}

renxiaole · 发表于 2017-1-18 19:37:44

5L超神了

hanyonstyle · 发表于 2017-4-25 15:06:09

下载看看虽然目前对递归还不怎么了解

Tangmige · 发表于 2018-3-1 12:24:15

先看

余錦濤 · 发表于 2019-11-21 23:31:39

#include<stdio.h>
#define N 8
int count=0;
int IsSafe(int row,int n,int (*chess)[N])
{
//判断列,斜向是否有冲突
//情况分为5种,左上，左下，右上，右下，本列
int i,j;
int flag;
flag=1;//安全
for(i=0;i<N;i++) //本列
{
if( 1 == chess[i][n])
{
flag=0;
break;
}
}
for(i=row,j=n;i>=0&&j>=0;--i,--j)//左上
{
if( 1 == chess[i][j])
{
flag=0;
break;
}
}
for(i=row,j=n;i<N&&j>=0;++i,--j)//左下
{
if( 1 == chess[i][j])
{
flag=0;
break;
}
}
for(i=row,j=n;i>=0&&j<N;--i,++j)//右上
{
if( 1 == chess[i][j])
{
flag=0;
break;
}
}
for(i=row,j=n;i<N&&j<N;++i,++j)//右下
{
if( 1 == chess[i][j])
{
flag=0;
break;
}
}
return flag;
}
// 参数row: 表示起始行
// 参数n: 表示列数
// 参数(*chess)[N]: 表示指向棋盘每一行的指针
void EightQueen(int row,int n,int (*chess)[N])//重点
{
//操作下标为 row 的那行
//复制整个棋盘
int chess2[N][N]={0};
int i,j;
for(i=0;i<N;++i)//复制,形成副本，然后操作副本
{
for(j=0;j<N;++j)
chess2[i][j]=chess[i][j];
}
//判断row==N,row==N代表溢出了,如果溢出了，就输出这种可能
//否则，继续填棋
if( N==row )//棋盘满了,输出副本
{
for(i=0;i<N;++i)
{
for(j=0;j<N;++j)
printf("%d ",chess2[i][j]);
printf("\n");
}
printf("\n\n");
count++; //出现一种可能
}
else //无溢出,棋盘未满，继续填棋
{
for(j=0;j<N;++j)//填充本行的0到N-1列
{
if(IsSafe(row,j,chess2))//1:安全,row行j列填棋
{
for(i=0;i<N;++i)
chess2[row][i]=0;//为了数据安全,清空本行
chess2[row][j]=1;//row行j列填棋
EightQueen(row+1,n,chess2);//填充下一行
}
}
}
}
//*(*(chess+i)+j) (*chess)[N]
int main(int argc, char *argv[]) {
//主函数说明:
int chess[N][N]={0};
EightQueen(0,N,chess);
printf("%d皇后有%d种可能！\n\n",N,count);
return 0;
}

复制代码

本人的拙见

余錦濤 · 发表于 2019-11-21 23:34:13

余錦濤发表于 2019-11-21 23:31
本人的拙见

可以试试从列开始放皇后

账号		自动登录	找回密码
密码			立即注册

a764934018 a764934018 当前离线 UID 258298 日志相册贡献荣誉积分 30 狗仔卡头像被屏蔽	发表于 2013-8-7 19:27:27 \| 显示全部楼层提示: 作者被禁止或删除内容自动屏蔽
	小甲鱼最新课程 -> https://ilovefishc.com
	回复支持反对使用道具举报显身卡

[技术交流] 八皇后问题（递归求解）

马上注册，结交更多好友，享用更多功能^_^

浏览过的版块