UC知道紧急 ！！！！怎样输出所有皇后的位置？
来源：百度知道 编辑：UC知道 时间：2024/06/19 22:02:12
#include <iostream>
using namespace std;
class Queen{
friend int nQueen(int);
private:
bool Place(int k);
void Backtrack(int t);
int n,//皇后个数
*x;//当前解
long sum;//当前已找到的可行方案数
};
bool Queen::Place(int k)
{
for(int j=1;j<k;j++)
if((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++;
else
for(int i=1;i<=n;i++){
x[t]=i;
if(Place(t))Backtrack(t+1);
}
}
int nQueen(int n)
{
Queen X;
//初始化X
X.n=n;
X.sum=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.sum;
}
int main()
{
int s;
cin>>s;
cout<<nQueen(s)<<endl;
return 0;
}
这里的程序只能得
using namespace std;
class Queen{
friend int nQueen(int);
private:
bool Place(int k);
void Backtrack(int t);
int n,//皇后个数
*x;//当前解
long sum;//当前已找到的可行方案数
};
bool Queen::Place(int k)
{
for(int j=1;j<k;j++)
if((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++;
else
for(int i=1;i<=n;i++){
x[t]=i;
if(Place(t))Backtrack(t+1);
}
}
int nQueen(int n)
{
Queen X;
//初始化X
X.n=n;
X.sum=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.sum;
}
int main()
{
int s;
cin>>s;
cout<<nQueen(s)<<endl;
return 0;
}
这里的程序只能得
这里设定是著名的八皇后问题，你可以更改其中的MAX得n皇后问题。输出已经显示了皇后位置。
一个很简洁的完整c代码如下，用的是递归方法。win-tc和Dev-c++下运行通过
#include <stdio.h>
#include <math.h>
#define MAX 8 /* 棋子数及棋盘大小MAXxMAX */
int board[MAX];
void show_result() /* 印出结果 */
{
int i;
for(i=0;i<MAX;i++)
printf("(%d,%d)",i,board[i]);
printf("\n");
}
int check_cross(int n) /* 检查是否在同一直横斜线上有其它棋子 */
{
int i;
for(i=0;i<n;i++){
if(board[i]==board[n] || (n-i)==abs(board[i]-board[n]))return 1;
}
return 0;
}
void put_chess(int n) /* 放棋子到棋盘上 */
{
int i;
for(i=0;i<MAX;i++){
board[n]=i;
if(!check_cross(n)){
if(n==MAX-1) show_result();/* 找到其中一种放法了...印出结果 */
else put_chess(n+1);
}
}
}
int main(void)
{
system("cls");
puts("The possible placements are:");
put_chess(0);