c++遞歸實現(xiàn)n皇后問題代碼(八皇后問題)
還是先來看看最基礎(chǔ)的8皇后問題：
在8X8格的國際象棋上擺放八個皇后，使其不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法。
擴展到N皇后問題是一樣的。
一看，似乎要用到二維數(shù)組。其實不需要。一維數(shù)組就能判斷，比如Arr[i]，就可以表示一個元素位于第i行第Arr[i]列——應(yīng)用廣泛的小技巧。而且在這里我們不用考慮去存儲整個矩陣，如果Arr[i]存在，那么我們在打印的時候，打印到皇后位置的時候輸出1，非皇后位輸出0即可。
這種思路的實現(xiàn)方式網(wǎng)上大把，包括前面提到的那位同學(xué)，所以也就不要糾結(jié)有沒有改善有沒有提高之類的了，權(quán)當(dāng)一次練習(xí)即可。
直接上代碼好了，覺得遞歸方法沒什么好說的，空間想想能力好一點兒很容易理解。明天有空再寫寫非遞歸實現(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皇后問題，觸底則進行打印
void Solve(int rowCurrent,int *&NQueen,int n,int &count, ofstream &os)
{
if(rowCurrent == n) //當(dāng)前行數(shù)觸底，即完成了一個矩陣，將它輸出
{
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; //解的計數(shù)
cout<<"請輸入問題的規(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;
}
C++機房預(yù)約系統(tǒng)實現(xiàn)流程實例
利用C語言實現(xiàn)任務(wù)調(diào)度的示例代碼