八皇后问题（递归求解）,数据结构与算法,编程语言专区,鱼C论坛

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

八皇后问题（递归求解）

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

该问题是十九世纪著名的数学家高斯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,int j)
{
int t;
t=h*h*h*h*h*h*h*h*h;//列
t=t*h*h*h*h*h*h*h*h;//列
t=t*h*h*h*h*h*h*h*h;//行
t=t*h*h*h*h*h*h*h*h;//行
t=t*h*h*h*h*h*h*h*h;//xie
t=t*h*h*h*h*h*h*h*h;//xie
t=t*h*h*h*h*h*h*h*h;//xie
t=t*h*h*h*h*h*h*h*h;//xie

return t;
}
int main()
{
int h;
for (int qqq=0;qqq<30;qqq++)
{
for(int qq=0;qq<30;qq++)
{
h=1;
}
}
int n,m,k;
int y,e,sa,si,w,l,q,b,sum;
sum=0;
for (y=11;y<=18;y++)
{
h=0;//11
for (e=11;e<=18;e++)
{
if(pd(12,h,e)==0)//12
{
}
else
{
h=0;

for(sa=11;sa<=18;sa++)//13
{
if(pd(13,h,sa)==0)
{
}
else
{
h=0;

for (si=11;si<=18;si++)//14
{
if(pd(14,h,si)==0)
{
}
else
{
h=0;

for(w=11;w<19;w++)//15
{
if(pd(15,h,w)==0)
{
}
else
{
h=0;

for (l=11;l<=18;l++)//16
{
if(pd(16,h,l)==0)
{
}
else
{

h=0;

for (q=11;q<=18;q++)//17
{
if(pd(17,h,q)==0)
{
}
else
{
h=0;
for (b=11;b<=18;b++)//18
{

if(pd(18,h,b)==0)
{
}
else
{
sum++;
h=0;
for (k=11;k<19;k++)
{
cout<<h;
}
cout<<endl;
for (k=11;k<19;k++)
{
cout<<h;
}
cout<<endl;
for (k=11;k<19;k++)
{
cout<<h;
}
cout<<endl;
for (k=11;k<19;k++)
{
cout<<h;
}
cout<<endl;
for (k=11;k<19;k++)
{
cout<<h;
}
cout<<endl;
for (k=11;k<19;k++)
{
cout<<h;
}
cout<<endl;
for (k=11;k<19;k++)
{
cout<<h;
}
cout<<endl;
for (k=11;k<19;k++)
{
cout<<h;
}
cout<<endl;
cout<<""<<endl;
cout<<""<<endl;
cout<<""<<endl;
}
}
for (n=18;n<30;n++)
{
for(m=0;m<30;m++)
{
h=1;
}
}
h=1;
}
}
h=1;
for (n=17;n<30;n++)
{
for(m=0;m<30;m++)
{
h=1;
}
}
}
}
h=1;
for (n=16;n<30;n++)
{
for(m=0;m<30;m++)
{
h=1;
}
}
}
}
h=1;
for (n=15;n<30;n++)
{
for(m=0;m<30;m++)
{
h=1;
}
}
}
}
h=1;
for (n=14;n<30;n++)
{
for(m=0;m<30;m++)
{
h=1;
}
}
}
}

h=1;
for (n=13;n<25;n++)
{
for(m=0;m<30;m++)
{
h=1;
}
}
}
}
for (n=12;n<30;n++)
{
for(m=0;m<30;m++)
{
h=1;
}
}
h=1;
}
cout<<sum<<endl;
return 0;
}

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

andalousie 发表于 2014-2-22 13:10 static/image/common/back.gif
看我同学写的八皇后，多么雷人。。。

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

杨延平 发表于 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; //a为第i行皇后所在列
void show() //图形化输出
{
int i;
int p,q ;
int b={0};
static int t=1;
printf("第%d个解为: ",t++);
for(i=0;i<N;i++)
{
   b]=1;
   printf("(%d,%d) ",i,a);
}
printf("\n");
for(p=0;p<N;p++)
{
   for(q=0;q<N;q++)
   {
         if(b==1)
            printf("●");
         else
            printf("○");
   }
   printf("\n");
}
}
int check(int n) //满足条件返回1，否则返回0
{
int i;
for(i=0;i<n;i++)
{
   if(a==a||fabs(n-i)==fabs(a-a)) //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=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超神了{:10_247:}

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

可以试试从列开始放皇后

页: [1]

鱼C论坛's Archiver

八皇后问题（递归求解）