n皇后问题的子集树求解与排列树求解

在n×n棋盘上放彼此不受攻击的n个皇后。
按国际象棋规则，皇后可攻击同行、同列、同一斜线的棋子。

等价于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。

可以用一个数组存储每行中的皇后的纵坐标，例如n=8时，X=(4,6,8,2,7,1,3,5)表示第一行的皇后的横坐标为4，

第二行的皇后的横坐标为6，......

比较常用的一种求解办法为通过子集树求解，约束条件为abs(k-j)！=abs(x[j]-x[k]) 并且 x[j]！=x[k]。

其实这个问题也可以描述为n个数字的排列问题，约束条件为abs(k-j)！=abs(x[j]-x[k])，这样该问题就可以用全排列的算法求解。

子集树求解的程序为：

#include 
#include 
int x[20];
int n,count;
int Place(int k)
{int j;for(j=1;jn) {for(i=1;i<=n;i++)printf("%d ",x[i]);printf("\n");count++;}elsefor(i=1;i<=n;i++) {x[t]=i;if(Place(t))Backtrack(t+1);}
}
int main()
{printf("请输入n:");scanf("%d",&n);Backtrack(1);printf("共%d组答案\n",count);return 0;
}

排列树求解的程序为：

#include 
#include 
int n,count;
int Place(int data[], int k)
{int j;for(j=1;jn){for(i=1;i<=n;i++)printf("%d ",data[i]);printf("\n");count++;}else{for(i=k;i<=n;i++){swap(data[k],data[i]);if(k==1 || Place(data,k))perm(data,k+1,n);swap(data[i],data[k]);}}
}
int main()
{int i;int data[20];printf("请输入n:");scanf("%d",&n);for(i=1;i<=n;i++)data[i]=i;perm(data,1,n);printf("共%d组答案\n",count);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！