八皇后问题（递归求解）

小甲鱼

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

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

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

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

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


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

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

牡丹花下死做鬼

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

兢兢

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

じO-联合

强烈支持楼主ing……

andalousie

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

#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;
}

小甲鱼

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

                               
登录/注册后可看大图

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

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

杨延平

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

阿衡

强烈支持楼主ing……

请问11

啊

请问11

{:1_1:}

DESTINY1002

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

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

weberwang

真是难得给力的帖子啊。

Einsteng

八皇后
#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

5L超神了

hanyonstyle

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

Tangmige

先看

余錦濤

#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:31
本人的拙见

可以试试从列开始放皇后