皇后控制问题
查看 提交 统计 提问
总时间限制: 10000ms 单个测试点时间限制: 1000ms 内存限制: 128000kB
描述
在一个n×n个方格组成的棋盘上的任一方格中放置一个皇后，该皇后可以控制他所在的行，列以及对角线上的所有方格。对于给定的自然数n，在n×n个方格组成的棋盘上最少要放置多少个皇后才能控制棋盘上的所有方格，且放置的皇后互不攻击？ 编程任务：设计一个算法，对于给定的自然数n (1≤n≤100)计算在n×n个方格组成的棋盘上最少要放置多少个皇后才能控制棋盘上的所有方格，且放置的皇后互不攻击。
输入
第一行有1个正整数n。
输出
将计算出来的最少皇后数及最佳放置方案输出。文件的第1行是最少皇后数；接下来的1行是皇后的最佳放置方案。
样例输入
8
样例输出
5
0 3 6 0 0 2 5 8
我写的代码编译就错误了，
//#include
#include
int min=101;
int index[101];
int save[101];
int can_set(int chess[][100],int n){
int i,j;
for(i=0;i for(j=0;j if(chess[i][j]==0){
return 1;
}
}
}
return 0;
}
int can_put(int chess[][100],int n,int x,int y){
int i,j;
if(chess[x][y]==1){
return 0;
}
for(i=x-1,j=y-1;i>=0&&j>=0;i--,j--){
if(chess[i][j]==1){
return 0;
}
}
for(i=x-1;i>=0;i--){
if(chess[i][y]==1){
return 0;
}
}
for(i=x-1,j=y+1;i>=0&&y if(chess[i][j]==1){
return 0;
}
}
for(j=y-1;j>=0;j--){
if(chess[x][j]==1){
return 0;
}
}
for(j=y+1;j if(chess[x][j]==1){
return 0;
}
}
for(i=x+1,j=y-1;i=0;i++,j--){
if(chess[i][j]==1){
return 0;
}
}
for(i=x+1;i if(chess[i][y]==1){
return 0;
}
}
for(i=x+1,j=y+1;i if(chess[i][j]==1){
return 0;
}
}
return 1;
}
void put(int chess[][100],int n,int x,int y){
int i,j;
chess[x][y]==1;
for(i=x-1,j=y-1;i>=0&&j>=0;i--,j--)
chess[i][j]==1;
for(i=x-1;i>=0;i--)
chess[i][y]=1;
for(i=x-1,j=y+1;i>=0&&y chess[i][j]==1;
for(j=y-1;j>=0;j--)
chess[x][j]=1;
for(j=y+1;j chess[x][j]==1;
for(i=x+1,j=y-1;i=0;i++,j--)
chess[i][j]==1;
for(i=x+1;i chess[i][y]==1;
for(i=x+1,j=y+1;i chess[i][j]==1;
}
void receive(int chess[][100],int n,int x,int y){
int i,j;
chess[x][y]==0;
for(i=x-1,j=y-1;i>=0&&j>=0;i--,j--)
chess[i][j]==0;
for(i=x-1;i>=0;i--)
chess[i][y]=0;
for(i=x-1,j=y+1;i>=0&&y chess[i][j]==0;
for(j=y-1;j>=0;j--)
chess[x][j]=0;
for(j=y+1;j chess[x][j]==0;
for(i=x+1,j=y-1;i=0;i++,j--)
chess[i][j]==0;
for(i=x+1;i<n;i++)
chess[i][y]==0;
for(i=x+1,j=y+1;i<n&&j<n;i++,j++)
chess[i][j]==0;
}
void dfs(int chess[][100],int n,int step,int column){
int i;
if(!can_set(chess,n)){
printf("***");
if(step<min){
min=step;
memset(save,0,sizeof(int));
for(i=0;i<min;i++){
save[i]=index[i];
}
memset(index,0,sizeof(int));
step=0;
return;
}
}else{
for(i=0;i<n;i++){
if(can_put(chess,n,i,column)){
put(chess,n,i,column);
index[step]=column;
dfs(chess,n,step+1,column+1);
receive(chess,n,i,column);
index[step]=0;
}
}
if(i==n){
dfs(chess,n,step,column+1);
}
}
}
int main(){
int n,i,step,j;
int chess[100][100];
scanf("%d",&n);
for(i=0;i<n;i++){
for(j=0;j<n;j++){
chess[i][j]=0;
}
}
dfs(chess,n,step,0);
printf("%d\n",min);
memset(index,0,sizeof(int));
for(i=0;i<min;i++){
index[save[i]]=1;
}
for(i=0;i<n;i++){
if(index[i]==1){
printf("%d ",i);
}
}
return 0;
}
哈，比八皇后问题难一点，类似于机器人巡逻那道题
机器人巡逻那道题目就是八皇后吧
这道题目可以允许有某一行没有出现皇后的