八皇后问题代码详解

#include <iostream>

#include <cstdio>

#include <sys/timeb.h>

using namespace std;

const int MAX_SIZE = 100;

enum flag {blank ='X',queen = 1};  //枚举类型

char Chess[MAX_SIZE][MAX_SIZE];//棋盘图

int n;//解决n皇后问题

int total;//用于计摆放方式

void Init()

{//对棋牌进行初始化

        for(int i = 0; i < n; i++)

                for(int j = 0; j < n; j++)

                        Chess[i][j] = blank;

        total = 0;//初始时有零中摆放方式

}

bool Judge(int r,int c)

{//判断(r,c)位置是否可放置

        int i,j;

        for(i = r + 1; i < n; i++)  //列不变行变   只管高位即可

                if(Chess[i][c] == queen)

                        return false;//说明c列上已有一皇后

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

                if(Chess[r][i] == queen)

                        return false;//说明r行上已有一皇后

        for(i = r + 1, j = c + 1; (i < n) && (j < n); i++, j++)

                if(Chess[i][j] == queen)

                        return false;//45度斜线上已有一皇后

        for(i = r + 1, j = c - 1; (i <n) && (j >= 0); i++, j--)

                if(Chess[i][j] == queen)

                        return false;//135度斜线上已有一皇后

        return true;//排除四种情况后，说明(r,c)点可放置皇后

}

void Backtrack(int k,int cnt)    //传参Backtrack(n*n-1,0);   8*8-1=63

{//回溯算法主程序

        if(k < 0 || cnt == n)//棋牌摆放完毕 or 以摆满n后

        {

                if(cnt == n)      //成功则输出

                {

                        printf("No.%d:\n",++total);

                        for(int i = 0; i < n; i++)

                        {

                                for(int j = 0; j < n; j++)

                                        printf(" %c ",Chess[i][j]);  //注意是%c

                                putchar('\n');

                        }                     

                        putchar('\n');

                }

        }

        else

        {

                int r = k / n, c = k % n;   //编号与下标的关系，除得行号，取余得列号。

                if(Judge(r,c))

                {//可放置一皇后

                        Chess[r][c] = queen;  //置为皇后

                        Backtrack(k-1,cnt+1); //以已摆好的为前序的所有解都在这句话里了，要特别注意

                        Chess[r][c] = blank;   //还原棋盘，以供回溯

                }

                Backtrack(k-1,cnt); //cnt仅仅用来判断是否摆满

        }

}

int main()

{//此为主函数

        timeb t1,t2;

        long kk;

        cout<<"输入皇后个数:\n";

        while(cin>>n)

        {

                        Init();

                        ftime(&t1);

                        Backtrack(n*n-1,0);

                        ftime(&t2);

                        cout<<"计算"<<n<<"后问题总共可有"<<total<<"种摆法!"<<endl;

                        kk = (t2.time-t1.time)*1000 + t2.millitm-t1.millitm;

                        cout<<"本次回溯耗时:"<<kk<<"毫秒"<<endl;

                        system("PAUSE");

                        cout<<"输入皇后个数:";

        }

        return 0;

}

******************************************************************************************************************************

#include<stdio.h>

#define COSZ 8

#define SLSZ 15

#define BSSZ 15

#define QUSZ 8

#define TRUE 1

#define FALSE 0

int col[COSZ],slash[SLSZ],bslash[BSSZ];

int queen[QUSZ];

int n=0,sum=0;

void generate(void);

int main()

{

   int c,s;

   for(c=0;c<=7;++c)

   {

      col[c]=TRUE;

   }

   for(s=0;s<=14;s++)

   {

      slash[s]=TRUE;

      bslash[s]=TRUE;

   }

   printf("rownum:\t0\t1\t2\t3\t4\t5\t6\t7\n\n");

   generate();

   printf("total:%d\n",sum);

   return 0;

}

void generate(void)

{

   int h,i;

   for(h=0;h<=7;h++)

   {

      if(col[h]&&slash[n+h]&&bslash[n-h+7])

      {

         queen[n]=h;

         col[h]=FALSE;

         slash[h+n]=FALSE;

         bslash[n-h+7]=FALSE;

         n+=1;

         if(n==8)

         {

            sum++;

            printf("%2d",sum);

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

            {

                printf("%8d",queen[i]);

                printf("\n");

            }

         }

         elsegenerate();

         n--;

         slash[n+h]=TRUE;

         bslash[n-h+7]=TRUE;

         col[h]=TRUE;

      }

   }

}