c++遞歸實(shí)現(xiàn)n皇后問題代碼(八皇后問題)
還是先來看看最基礎(chǔ)的8皇后問題:
在8X8格的國際象棋上擺放八個(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)吧。
/*
* 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;
}
相關(guān)文章
C語言實(shí)現(xiàn)飛機(jī)售票系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)飛機(jī)售票系統(tǒng),文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2022-05-05C++語言實(shí)現(xiàn)hash表詳解及實(shí)例代碼
這篇文章主要介紹了C++語言實(shí)現(xiàn)hash表詳解及實(shí)例代碼的相關(guān)資料,需要的朋友可以參考下2017-01-01Cocos2d-x UI開發(fā)之文本類使用實(shí)例
這篇文章主要介紹了Cocos2d-x學(xué)習(xí)筆記之文本類,文本類是UI開發(fā)中經(jīng)常使用的,本文用詳細(xì)的代碼注釋講解了文本類的使用,需要的朋友可以參考下2014-09-09淺談C++/C關(guān)于#define的那些奇奇怪怪的用法
本文主要介紹了C++/C關(guān)于#define的那些奇奇怪怪的用法,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-07-07QT使用SQLite數(shù)據(jù)庫超詳細(xì)教程(增刪改查、對(duì)大量數(shù)據(jù)快速存儲(chǔ)和更新)
這篇文章主要給大家介紹了關(guān)于QT使用SQLite數(shù)據(jù)庫的相關(guān)資料,其中包括增刪改查以及對(duì)大量數(shù)據(jù)快速存儲(chǔ)和更新,SQLite是一種嵌入式關(guān)系型數(shù)據(jù)庫管理系統(tǒng),它是一個(gè)軟件庫,提供了一個(gè)自包含、無服務(wù)器、零配置的、事務(wù)性的SQL數(shù)據(jù)庫引擎,需要的朋友可以參考下2024-01-01對(duì)比C語言中g(shù)etc()函數(shù)和ungetc()函數(shù)的使用
這篇文章主要介紹了對(duì)比C語言中g(shù)etc()函數(shù)和ungetc()函數(shù)的使用,是C語言入門學(xué)習(xí)中的基礎(chǔ)知識(shí),需要的朋友可以參考下2015-08-08