關(guān)于回溯法的遞歸與非遞歸—–N皇后問題

藍橋杯 基礎(chǔ)練習(xí) 2n皇后問題
　　給定一個n*n的棋盤，棋盤中有一些位置不能放皇后。現(xiàn)在要向棋盤中放入n個黑皇后和n個白皇后，使任意的兩個黑皇后都不在同一行、同一列或同一條對角線上，任意的兩個白皇后都不在同一行、同一列或同一條對角線上。問總共有多少種放法？n小于等于8。
輸入格式
　　輸入的第一行為一個整數(shù)n，表示棋盤的大小。
　　接下來n行，每行n個0或1的整數(shù)，如果一個整數(shù)為1，表示對應(yīng)的位置可以放皇后，如果一個整數(shù)為0，表示對應(yīng)的位置不可以放皇后。
輸出格式
　　輸出一個整數(shù)，表示總共有多少種放法。
樣例輸入
4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
樣例輸出
2
樣例輸入
4
1 0 1 1
1 1 1 1
1 1 1 1
1 1 1 1
樣例輸出
0

最初思路（運行超時）

定義一個二維數(shù)組當(dāng)棋盤，挨個遍歷，每個位置分為放黑皇后或放白皇后或不放三個選擇；用回溯法的遞歸實現(xiàn)。

后來看了別人的代碼，自己的方法簡直太笨了，分析了一下有以下缺點：

黑白一起考慮：這樣每個位置就多了一個選擇，在遞歸的過程相當(dāng)于時間復(fù)雜度多乘了個n；如果先考慮黑在考慮白，相當(dāng)于時間復(fù)雜度乘以2。

二維數(shù)組：遍歷麻煩，而且耗時。因為一行只能放一個皇后（先只考慮一個顏色的皇后）所以這一行只要有皇后了，就直接到下一行去找。

遞歸：通常來說回溯法分為遞歸和非遞歸，遞歸的效率低一些。要練習(xí)使用非遞歸的方法。

改進方法

黑白分開考慮，先看黑皇后，再看白。

用一位數(shù)組代替，q[i]代表第i行上的皇后在第幾列。

用非遞歸。

#include <stdio.h> #include <iostream> using namespace std; int blq[8];//每行的黑皇后在第幾列 int whq[8];//每行的白皇后在第幾列 int n; int can[8][8];//存放0/1，能否放皇后 int result=0; bool Place(int * q,int x,int y) {if(can[x][y]==0) return false;for(int i=0;i<x;i++) {//是否在一列上 if(q[i]==y) return false;if(i+q[i]==x+y||i-q[i]==x-y) return false;//對角線 } return true; }void WhiteQueen() {int x=0,y=0; while(x<n){for(;y<n;y++){if(Place(whq,x,y)&&blq[x]!=y) {//cout<<"q["<<x<<"]="<<y<<" ";whq[x]=y;y=0;break;}}if(whq[x]==-1){//說明第x行沒找到合適的位置 ，回溯 x--;if(x<0) return;//回溯到第一行，第一行都沒有合適的位置 就結(jié)束 y=whq[x]+1;whq[x]=-1;//返回上一行continue;}if(whq[n-1]!=-1){//找到一種解 result++;/*for(int i=0;i<n;i++) cout<<whq[i]<<" ";cout<<endl;*/y=whq[x]+1;//皇后往下移一個位置繼續(xù)找whq[n-1]=-1;//清除改行皇后 = continue;}x++;} } void BlackQueen() {int x=0,y=0; while(x<n){for(;y<n;y++){if(Place(blq,x,y)) {//cout<<"q["<<x<<"]="<<y<<" ";blq[x]=y;y=0;break;}}if(blq[x]==-1){//說明第x行沒找到合適的位置 ，回溯 x--;if(x<0) return;//回溯到第一行，第一行都沒有合適的位置 就結(jié)束 y=blq[x]+1;blq[x]=-1;//返回上一行continue;}if(blq[n-1]!=-1){//找到一種解 WhiteQueen();/*for(int i=0;i<n;i++) cout<<blq[i]<<" ";cout<<endl;*/y=blq[x]+1;//皇后往下移一個位置繼續(xù)找blq[n-1]=-1;//清除改行皇后 = continue;}x++;} }int main() {cin>>n;for(int i=0;i<n;i++){for(int j=0;j<n;j++) cin>>can[i][j];}for(int i=0;i<n;i++) {blq[i]=-1;whq[i]=-1;}BlackQueen();cout<<result; }

---

參考博客（思路詳解）

總結(jié)

以上是生活随笔為你收集整理的关于回溯法的递归与非递归-----N皇后问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。