算法设计与分析 回溯法 n皇后问题

在n*n格的棋盘上放置彼此不受攻击的n个皇后。按照国际向其的规则，皇后可以攻击同一行、同一列、同一斜线上的棋子。

#include
long nQueen（int n）;
int abs（int ）;
//主函数；

int main（）{
	int numberresult;
	cout<<“输入要放置的皇后个数：“;
	cin>>number;
    result=nQueen（number）;
	cout<	return 0;
}
//类和函数；
class Queen {
	friend long nQueen（int）;
private:
	bool Place（int k）;
	void Backtrack（int t）;
	int n   //皇后个数；
		*x;  //当前解；x[i]表示皇后放在棋盘的第i 行的第x[i]列；
	long sum;  //当前已找到的可行方案数；
};
bool Queen::Place（int k）
{
for（int j=1;jif（（abs（k-j）==abs（x[j]-x[k]）） ||（x[j]==x[k]）） return false;
return true;
}
void Queen::Backtrack（int t）
{
	if（t>n） {sum++;   //成功放置一次，方案数加1；
	for（int row=1;row		for（int col=1;col			if（x[row]==col） cout<<“1“<<“ “;    //当row行的列的值等于x[row]的值时，
			  	else cout<<“0“<<“ “;           //就证明这一行的皇后放在该列，即把该位置标志为1；否则为0
		}
		cout<	}
	cout<	}

	else {
		for（int i=1; i<=n;i++）{
			x[t]=i;          
			if（Place（t）） Backtrack（t+1）;
		}
	}
}

long nQueen（int n）
{
	Queen X;
	X.n=n;
	X.sum=0;
	int *p=new int [n+1];
	for（int i=1;i<=n;i++）
		p[i]=0;
	X.x=p;
	X.Backtrack（1）;
	delete []p;
	return X.sum;
}

int abs（int a）
{ int b;
	if（a>=0） return a;
	else b=0-a;
	 return b;
}

 

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       1348  2000-12-03 09:42  n后问题.cpp

----------- ---------  ---------- -----  ----

                 1348                    1