快捷導(dǎo)航

c++遞歸實(shí)現(xiàn)n皇后問題代碼(八皇后問題)

更新時(shí)間：2013年12月25日 10:29:49 作者：

c++遞歸實(shí)現(xiàn)n皇后問題代碼分享，大家參考使用吧

還是先來看看最基礎(chǔ)的8皇后問題：

在8X8格的國(guó)際象棋上擺放八個(gè)皇后，使其不能互相攻擊，即任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法。

擴(kuò)展到N皇后問題是一樣的。
一看，似乎要用到二維數(shù)組。其實(shí)不需要。一維數(shù)組就能判斷，比如Arr[i]，就可以表示一個(gè)元素位于第i行第Arr[i]列——應(yīng)用廣泛的小技巧。而且在這里我們不用考慮去存儲(chǔ)整個(gè)矩陣，如果Arr[i]存在，那么我們?cè)诖蛴〉臅r(shí)候，打印到皇后位置的時(shí)候輸出1，非皇后位輸出0即可。

這種思路的實(shí)現(xiàn)方式網(wǎng)上大把，包括前面提到的那位同學(xué)，所以也就不要糾結(jié)有沒有改善有沒有提高之類的了，權(quán)當(dāng)一次練習(xí)即可。

直接上代碼好了，覺得遞歸方法沒什么好說的，空間想想能力好一點(diǎn)兒很容易理解。明天有空再寫寫非遞歸實(shí)現(xiàn)吧。

復(fù)制代碼代碼如下:

/*
* NQueen.cpp
*
* Created on: 2013年12月23日
*      Author: nerohwang
*/
//形參rowCurrent表示當(dāng)前所到的行數(shù)
#include<iostream>
#include<fstream>
#include<iomanip>
#include<stdlib.h>
using namespace std;
bool Check(int rowCurrent,int *&NQueen);                         //判斷函數(shù)
void Print(ofstream &os,int n,int *&NQueen);                                  //打印函數(shù)
void Solve(int rowCurrent,int *&NQueen,int n,int &count, ofstream &os);           //N皇后問題處理函數(shù)，index一般初值為0

//判斷函數(shù)，凡是橫豎有沖突，或是斜線上有沖突，返回FALSE
bool Check(int rowCurrent,int *&NQueen)
{
    int i = 0;
    while(i < rowCurrent)
    {
        if(NQueen[i] == NQueen[rowCurrent] || (abs(NQueen[i]-NQueen[rowCurrent]) == abs(i-rowCurrent)) )
        {
            return false;
        }
        i++;
    }
    return true;
}

//將所有可能出現(xiàn)的結(jié)果輸出文本文檔
void Print(ofstream &os,int n,int *&NQueen)
{
    os<<"一次調(diào)用\n";
    for (int i = 0;i < n;i++) {
        for(int j = 0 ; j < n; j++)
        {
            os<<(NQueen[i]==j?1:0);
            os<<setw(2);
        }
        os<<"\n";
    }
    os<<"\n";
}

//核心函數(shù)。遞歸解決N皇后問題，觸底則進(jìn)行打印
void Solve(int rowCurrent,int *&NQueen,int n,int &count, ofstream &os)
{
    if(rowCurrent == n) //當(dāng)前行數(shù)觸底，即完成了一個(gè)矩陣，將它輸出
    {
        Print(os,n,NQueen);
        count++;
    }
    for(int i = 0; i < n; i++)
    {
        NQueen[rowCurrent] = i;                     //row行i列試一試
        if(Check(rowCurrent,NQueen))
        {
            Solve(rowCurrent+1,NQueen,n,count,os); //移向下一行
        }
    }
}

int main()
{
    int n;           //問題規(guī)模
    int count = 0;   //解的計(jì)數(shù)
    cout<<"請(qǐng)輸入問題的規(guī)模N"<<endl;
    cin>>n;
    if(n<4)
    {
        cerr<<"問題規(guī)模必須大于4"<<endl;
        return 0;
    }
    int *NQueen = new int[n];
    ofstream os;
    os.open("result.txt");
    Solve(0,NQueen,n,count,os);
    cout<<"問題的解有"<<count<<"種方法"<<endl;
    os.close();
    return 0;
}