nqueen.cpp

Nqueen后问题解答,输入任一大于1的数

// Nqueen.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "iostream.h"
#include "math.h"

class Queen {
	friend int nQueen(int);
    private:
		bool Place(int k);
		void Backtrack(int t);
		int n,*x;
		long sun;
};
bool Queen::Place(int k) {
	for(int j = 1;j<k;j++) 
		if((abs(k - j) == abs(x[k] - x[j])) || (x[j] == x[k])) return false;
		 return true;
}
void Queen::Backtrack(int t) {
	if(t > n) sun++;
	else for(int i = 1;i<=n;i++) {
		x[t] = i;
		if(Place(t)) Backtrack(t + 1);
	}
}
int nQueen(int n) {
	Queen X;
	X.n = n;
	X.sun = 0;
	int *p = new int[n+1];
	for(int i = 0;i <= n;i++)
		p[i] = 0;
	X.x = p;
	X.Backtrack(1);
	delete [] p;
	return X.sun;
//	ruturn X.x;
}
void main() {
	int n;
	cin>>n;
	cout<<nQueen(n)<<endl;
}