Frankly speaking,第一眼看这个题真没劲,古董题,N皇后。不过,第一次提交代码之后我明白了,是我自己太没专研精神了。N皇后是回溯或者说深度优先搜索的典范,我就是初学回溯和DFS时接触到N皇后的,所以我飞敲键盘写出了下面的代码(这个不是直接提交的代码,是后来我测试时用的代码,但是算法当然是一致的),当然,请轻拍。
#include<iostream>
#include<Windows.h>
using namespace std;
int x[100]; // at most 100 queues
int n, times, num;
inline void init(){for(int i =0; i < 100; ++i) x[i] = 0;}
inline int abs(int a) { return a >= 0 ? a : -a; }
inline bool check(int k, int i){
for(int j = 1; j < k; ++j)
if((x[j]==i) || (abs(x[j]-i) == abs(j-k)) )
return false;
return true;
}
void backtrack(int k){
for(int i = 1; i < n+1; i++){
if(check(k, i)){
x[k] = i;
if(k == n){
++num;
if(times < 3){
++times;
for(int j = 1; j < n+1; ++j) cout<<x[j]<<' ';
cout<<endl;
}
}
else backtrack(k+1);
}
}
}
int main(){
while(cin>>n){
times = 0, num = 0;
init();
DWORD t = GetTickCount();
backtrack(1);
std::cout<<"Find "<<num<<" solutions. "<<"Using "<<