思想:存三个数组记录记录走的过程,运用回溯不符合或row==n+1就跳出当前层,直到找完;递归时的路径都在保存着,当连续跳出到第一次进入的dfs且i=n时就全部跳出dfs函数了;
#include<stdio.h>
#include<string.h>
int n,sum;
int visit[][];
int dp[];
void dfs(int row){int i;
if(row==n+){
sum++;return;
}//如果行等于要求找的行数,跳出这一层进行下一次查找
for(i=;i<=n;i++){//一定要注意i为当前列数,变化的visit是一维数组,将行数转化为列数相当于将面化为线,
//分↖↑↗ 这三个数组,主要因为i是从小到大的,存一个数组会造成影响
if(visit[][i]== && visit[][i+row]== && visit[][row-i+n]==){/*i代表当前列数;
visit【i】代表当前这一列是否放皇后; visit[i+row]为↗是否放元素*/
visit[][i] = visit[][i+row] = visit[][row-i+n] = ;//i代表列数,每次从1到n
dfs(row+);
visit[][i]=visit[][i+row]=visit[][row-i+n]=;//回溯,当函数跳出当前层时,证明成功了,或不符合,然后回溯,使上一层走的不算;进行下一次查找;
}//如果if没执行证明不符合i++进行行中下一次查找;
}
return;//如果不符合跳出这一层;
}
int main(){int N;
for(n=;n<=;n++){sum=;
memset(visit,,sizeof(visit));
dfs();
dp[n]=sum;//打表主要怕超时;
}
while(~scanf("%d",&N),N){
printf("%d\n",dp[N]);
}
return ;
}
推荐个帖子:http://topic.csdn.net/t/20060424/13/4709025.html
还有的大神用的位运算,写的;
n皇后问题将递归与回溯用到了极致。。。