一．問題描述

在8×8格的國際象棋棋盤上放置八個皇后，使得任意兩個皇后不能互相攻擊，即任何行、列或對角線（與水平軸夾角為45°或135°的斜線）上不得有兩個或兩個以上的皇后。這樣的一個格局稱為問題的一個解。請用遞歸與非遞歸兩種方法寫出求出八皇后問題的算法。

二．解題思路描述

一個正確的解應當是每一列，每一行，每一條斜線上均只有一個皇后。

對于遞歸算法，本人才有模擬的方式進行，而且，我覺得開辟一個二維數組更顯而易見。首先，從空棋盤開始擺放，保證第m行m個皇后互不攻擊，然后擺放第m+1個皇后。當然對于第m+1個皇后可能有多種擺放方法，由此，我必須一一枚舉，采用回溯策略是可行且合乎邏輯的。?

而對于非遞歸算法，我只是借助于書本上一個遞歸改為非遞歸的框架，依次搭建而已。

在此過程中，我采用一維數組，一位對于八皇后問題，每一行不可能存在二個及二個以上的皇后，board[i]表示第i行棋盤擺放的位置為第board[i]列。遞歸方法借助于系統提供的棧，而我非遞歸算法的實現，僅僅是自己構造一個棧而已。

遞歸解法

?

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

總結

以上是生活随笔為你收集整理的八皇后问题（递归+非递归）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。