回溯法(探索与回溯法)是一种选优搜索法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。
基本思想:
在包含问题的所有解的解空间树中,按照深度优先搜索的策略,从根结点出发深度探索解空间树。当探索到某一结点时,要先判断该结点是否包含问题的解,如果包含,就从该结点出发继续探索下去,如果该结点不包含问题的解,则逐层向其祖先结点回溯。(其实回溯法就是对隐式图的深度优先搜索算法)。
若用回溯法求问题的所有解时,要回溯到根,且根结点的所有可行的子树都要已被搜索遍才结束。 而若使用回溯法求任一个解时,只要搜索到问题的一个解就可以结束。
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2553
#include<iostream> #include<cstdio> #include<cmath> using namespace std; int x[11],N,sum; bool place(int k){ //判断第K个皇后是否可以加入 for(int i=1;i<k;i++){ if(x[i]==x[k] || abs(k-i)==abs(x[k]-x[i])) return false; } return true ; } void backtrack(int k){ //k的初值为1 if(k>N) //安排完N个皇后后sum++ sum++; else{ for(int i=1;i<=N;i++){ //找第K个皇后的列坐标 x[k]=i; if(place(k)){ backtrack(k+1); } } } } int main(){ int ans[11]; for(N=1;N<=10;N++){ sum=0; backtrack(1); ans[N]=sum; } while(scanf("%d",&N)!=EOF && N){ printf("%d\n",ans[N]); } return 0; }