八皇后问题（递归+非递归）_9.a使用递归和非递归完成8皇后问题,若棋盘为5x5或9x9结果如何?总结递归与非递归算

#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 )
{ //回溯算法主程序
        
         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 ] );
                                 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 );
         }
        
}

int main ( )
{ //此为主函数
        timeb t1,t2;
         long kk;
        cout<< "输入皇后个数:";
         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 <iostream>
#include <sys/timeb.h>
#define N 100
using  namespace std;

int board [N ];
int n,sum;

void init ( )
{
         for ( int i =  1; i <= n; i++ )
                board [i ] =  0;
}

void display ( )
{
         int i,j;
        cout<< "No."<<sum<<endl;
         for (i =  1; i <= n; i++ )
         {
                 for (j =  1; j <= n; j++ )
                         if (board [i ] == j )
                                cout<< "Q ";
                         else
                                cout<< "X ";
                cout<<endl;
         }
        cout<<endl;
}

bool canPut ( int k )
{
         for ( int i =  1; i < k; i++ )
                 if ( ( abs (k - i ) ==  abs (board [k ] - board [i ] ) ) || board [i ] == board [k ] )
                         return  false; //1.是否在同一斜线;2.是否位于同一列
         return  true;
}

void Backtrack ( )
{
        board [ 1 ] =  0;
         int k =  1;
         while (k >  0 )
         {
                board [k ]++;
                 while ( (board [k ] <= n ) && ! (canPut (k ) ) )
                        board [k ] +=  1;
                 if (board [k ] <= n )
                         if (k == n )
                         {
                                sum++;
                                display ( );
                         }
                         else
                         {
                                k++;
                                board [k ] =  0;
                         }
                 else
                        k--;

         }
}

int main ( )
{
        timeb t1,t2;
         long kk;
        cout<< "输入皇后个数:";
         while (cin>>n )
         {
                init ( );
                sum =  0;
                ftime (&t1 );
                Backtrack ( );
                ftime (&t2 );
                cout<< "总共排列方式为:"<<sum<<endl;
                kk =  (t2. time-t1. time )* 1000 + t2. millitm-t1. millitm;
                cout<< "本次回溯耗时:"<<kk<< "毫秒"<<endl;
                 system ( "PAUSE" );
                cout<< "输入皇后个数:";
         }
         return  0;
}