N皇后问题
在N*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。
你的任务是，对于给定的N，求出有多少种合法的放置方法。
Input
共有若干行，每行一个正整数N≤10，表示棋盘和皇后的数量；如果N=0，表示结束。
Output
共有若干行，每行一个正整数，表示对应输入行的皇后的不同放置数量。
Sample Input
1
8
5
0 Sample Output
1
92
10 首先水题一波
N皇后问题解的个数
n solution(n)
1 1
2 0
3 0
4 2
5 10
6 4
7 40
8 92
9 352
10 724
11 2680
12 14200
13 73712
14 365596
15 2279184
16 14772512
17 95815104
18 666090624
19 4968057848
20 39029188884
21 314666222712
22 2691008701644
23 24233937684440
24 227514171973736
25 2207893435808352
水题代码
#include <iostream>
#include <stdio.h>
#include <cstring>
using namespace std;
int n;
int main()
{
while(scanf("%d",&n)!=EOF){
if(n==0) break;
switch(n){
case 1: printf("1\n");break;
case 2: printf("0\n");break;
case 3: printf("0\n");break;
case 4: printf("2\n");break;
case 5: printf("10\n");break;
case 6: printf("4\n");break;
case 7: printf("40\n");break;
case 8: printf("92\n");break;
case 9: printf("352\n");break;
case 10:printf("724\n");break;
case 11:printf("2680\n");break;
}
}
//cout << "Hello world!" << endl;
return 0;
}
正经答案
问题描述：八皇后问题是一个以国际象棋为背景的问题：如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。
我们可以通过下面的图标来展示回溯法的过程
从而更加有助于我们的理解
我们在试探的过程中，皇后的放置需要检查他的位置是否和已经放置好的皇后发生冲突，为此需要以及检查函数来检查当前要放置皇后的位置，是不是和其他已经放置的皇后发生冲突
假设有两个皇后被放置在（i，j）和（k，l）的位置上，明显，当且仅当|i-k|=|j-l| 时，两个皇后才在同一条对角线上。
（1）先从首位开始检查，如果不能放置，接着检查该行第二个位置，依次检查下去，直到在该行找到一个可以放置一个皇后的地方，然后保存当前状态，转到下一行重复上述方法的检索。
（2）如果检查了该行所有的位置均不能放置一个皇后，说明上一行皇后放置的位置无法让所有的皇后找到自己合适的位置，因此就要回溯到上一行，重新检查该皇后位置后面的位置。
OK
来一波暴力答
DFS
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <cmath>
using namespace std;
int n,ans;
int vis[20][20];
int h[20];
bool check(int k ,int l){
for(int i=0;i<k;i++){
for(int j=0;j<n;j++){
if(vis[i][j]==1&&(i==k||j==l||abs(i-k)==abs(j-l))){
return false;
}
}
}
return true;
}
void dfs(int h){
if(h==n){
ans++;
return;
}
for(int i=0;i<n;i++){
if(vis[h][i]==0&&check(h,i)){
vis[h][i]=1;
dfs(h+1);
vis[h][i]=0;
}
}
}
int main(){
while(scanf("%d",&n)!=EOF){
if(n==0)break;
memset(vis,0,sizeof(vis));
ans=0;
dfs(0);
printf("%d\n",ans);
}
return 0;
}
结果很准确
很不幸TLE
接下来剪枝
-
思路：枚举 然后检测，回朔
-
总共有s=n*n个点 对于每个点 横坐标为s/now,纵坐标为s%n
-
水平方向 只需要检查0到s/now
-
竖直方向 只需要检查0到s%now
-
斜线方向 只需要检查左上和右上
-
能到达s就为一种方案 累加
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <cmath>
using namespace std;
int n,ans;
int vis[20][20];
int h0[20],l0[20];
bool check(int k ,int l){
for(int i=1;i<k+1;i++){
if(k-i>=0&&l+i<n&&vis[k-i][l+i]==1){
return false;
}
if(k-i>=0&&l-i>=0&&vis[k-i][l-i]==1){
return false;
}
}
return true;
}
void dfs(int h){
if(h==n){
ans++;
return;
}
for(int i=0;i<n;i++){
if(vis[h][i]==0&&h0[h]==0&&l0[i]==0&&check(h,i)){
vis[h][i]=1;
h0[h]=1;
l0[i]=1;
dfs(h+1);
vis[h][i]=0;
h0[h]=0;
l0[i]=0;
}
}
}
int main(){
while(scanf("%d",&n)!=EOF){
if(n==0)break;
memset(vis,0,sizeof(vis));
ans=0;
dfs(0);
printf("%d\n",ans);
}
return 0;
}
不过依然TLE
研究了一下大牛的代码，位运算被神一样的运用！ORZ！
剪枝：
1、一个数和它的负数取与，得到的是最右边的1！负数在计算机里面的表示是原码取反加1，可以试一下，确实是得到最右边的。这样就可以简化for循环，免得一位一位地判断了；
2、按照行来进行枚举，同时将两个对角线和列的状况压缩表示！详细解释的话，我们可以这样想，对于任何一行，都有n个位置，那么这n个位置相应的列是否有皇后，我们可以用一个bool的数组来表示，有的数置为1，没有为0。那么进而，我们可以把这个bool数组压缩成一个数，使得这个数的二进制表示就是这个bool数组，通过位运算来判断相应的位置上是否为1，如果三个状态的相应位置上都代表可以放一个1的话，那么就用位运算来改变这个位置的值！
3、对于对角线，要单拿出来说一下。由于，第i行的第j个位置和第i+1行的j-1一个值，在主对角线上是对应的，而第i行的第一个位置，在主对角线的情况下对之后的行是没有影响的；同理，付对角线的情况，每一行的最后一个元素对于后面的行的是没有影响的，并且是第i行的第j个位置和i+1行的j+1的位置是对应。因此，在向下一层遍历的时候，要把主对角线像坐移位，付对角线向右移位。这样，使得相应的位置可以对上，没有用的删去，新增的置为0。如果还是不懂，就画一个矩阵，一目了然！
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n, ans;
int limit;
void dfs( int h, int r, int l ) {
if ( h == limit ) { //说明n列都站满了
ans++;
return;
}
int pos = limit & (~(h|r|l)), p; //pos的二进制位0的，并且这个limit不能省，limit保证了pos高于n的位为0
while ( pos ) {
p = pos & (-pos); //这个运算，即原码和补码取与的运算，可以得出最右边的1；
pos -= p;
dfs( h+p, (r+p)<<1, (l+p)>>1 );
}
}
int main()
{
while ( scanf("%d", &n) != EOF && n ) {
ans = 0;
limit = ( 1<<n ) - 1; //limit的二进制是n个1；
//cout << limit << endl;
dfs( 0, 0, 0 );
printf("%d\n", ans);
}
}
