C++実現n皇后問題
//書籍参照:コンピュータアルゴリズム基礎-華中科技大学第三版
//n皇后問題を遡及法で実現し、nqueens(int k)法を再帰で実現し、効率を高めるために非再帰に変更することができる
//n皇后問題を遡及法で実現し、nqueens(int k)法を再帰で実現し、効率を高めるために非再帰に変更することができる
//queen.h--Queen class
#ifndef _QUEEN_H_
#define _QUEEN_H_
#include<iostream>
class Queen
{
private:
int queens;//total queens
int *answer;//answer array
int sum;//total answers
//judge a certain place is available,k represent row,i represent column
bool place(int k,int i)const;
void printResult()const;//print result
public:
Queen(int n);
~Queen();
void nqueens(int k=1);//search the solutionof vector space under the condition
void printSum()const{ std::cout<<sum<<std::endl;}
};
#endif
//N_QUEEN.cpp--Queen class methods
#include<cmath>
#include"queen.h"
Queen::Queen(int n)
{
queens=n;
answer=new int[n+1];
sum=0;
}
Queen::~Queen()
{
delete []answer;
}
void Queen::nqueens(int k)
{
answer[k]=1;
while(answer[k]<=queens)
{
if(place(k,answer[k]))
{
if(k==queens)
{
sum++;
printResult();
}
else
nqueens(k+1);
}
answer[k]=answer[k]+1;
}
}
bool Queen::place(int k,int i)const
{
int m=1;
while(m<k)
{
if(answer[m]==answer[k]||abs(answer[k]-answer[m])==abs(k-m))
return false;
m++;
}
return true;
}
void Queen::printResult()const
{
for(int i=1;i<queens;i++)
{
std::cout<<answer[i]<<" ";
}
std::cout<<std::endl;
}
//use.cpp--test Queen class
#include<iostream>
#include"queen.h"
int main()
{
std::cout<<"Enter the queens:";
int m;
std::cin>>m;
Queen q=Queen(m);
q.nqueens();
std::cout<<"Total methods: ";
q.printSum();
std::cout<<"Done!
";
return 0;
}