八皇后问题

//回溯 加递归  #include<stdio.h>int Chess[8][8]={0};//定义二维数组代表8x8棋盘int a[8],b[15],c[15];//定义a［8］代表一竖是八行，定义b［15］，c［15］代表从↗?到↙?对角线和从↖?到↘?对角线int sum=0;//定义sum累计确定一共有多少种结果void Queen(int n)//定义放置皇后的函数{    int col;//定义col控制皇后的位置    for(col=0;col<8;col  )//从第一行开始确定皇后的位置，逐次递增，col表示皇后在该行的第几个位置    {        if(a[col]&&b[n col]&&c[n-col 7])//判断该位置竖、对角线都还有1个皇后可以放，为真，即＝1        {            Chess[n][col]=1;//放置皇后            a[col]=0;//放置皇后后，该位置的竖剩余可放皇后数变为0            b[n col]=0;//放置皇后后，该位置的由↗?到↙?对角线剩余可放皇后数变为0            c[n-col 7]=0;//放置皇后后，该位置的由↖?到↘?对角线剩余可放皇后数变为0            if(n==7)//判断是否到第八行，不到第八行则执行else            {                sum  ;//循环到第八行，都符合题中条件，摆法加一            }            else//执行，递归            {                Queen(n 1);//调用函数Queen，参数逐次加一            }            Chess[n][col]=0;//取消皇后,恢复棋盘初始值            b[n col]=1;//恢复初始值，保证下一次循环的功能性            c[n-col 7]=1;//恢复初始值，保证下一次循环的功能性            a[col]=1;//恢复初始值，保证下一次循环的功能性        }    }}int main()//主函数{    int i;//定义计数变量i    for(i=0;i<8;i  )//使a［i］＝1，使初始值都为1，即真    {        a[i]=1;    }    for(i=0;i<15;i  )//使b［i］＝1，c［i］＝1，使初始值都为1，即真    {        b[i]=1;        c[i]=1;    }    Queen(0);//调用递归函数Queen，实现sum的累加    printf("%d\n",sum);//输出sum的值    return 0;//返回0}

View Code

 自我实现：

//八皇后问题//a[1...8]表示列的状态 0表示不允许//b[1...15]表示左下到右上的范围//c[1...15]表示右下往左上的范围//由于每一步不确定性，需要用到回溯法 #include<iostream>using namespace std;int a[9],b[16],c[16];int sum=0,num=0;void gcd(int k){//取值1--8     if(k>8){        if(num==8) sum  ;        return ;    }    for(int col=1;col<=8;col  ){        if(a[col]&&b[k col-1]&&c[8-k col]){//            num  ;            a[col]=0;            b[k col-1]=0;            c[8-k col]=0;            gcd(k 1);//            num--;            a[col]=1;            b[k col-1]=1;            c[8-k col]=1;        }    }} void hei(int a[],int n){    for(int i=0;i<=n;i  )    a[i]=1;}int main(){    hei(a,9);    hei(b,16);    hei(c,16);    gcd(1);    cout<<sum<<endl;}

View Code

上面程序最后跳出93种，为什么多了一种？

因为初始化全部为1，回溯后会重复一次，记住多算一次就行！！！