文档介绍：搜索与回溯搜索与回溯是计算机解题中常用的算法,有很多问题无法根据某种确定的计算法则来求解,此时可以利用搜索与回溯的技术求解。回溯是搜索算法中的一种控制策略。它的基本思想是:为了求得问题的解,先选择某一种可能情况向前探索,在探索过程中,一旦发现原来的选择是错误的,就退回一步重新选择,继续向前探索,如此反复进行,直至得到解或证明无解。如迷宫问题:进入迷宫后,先随意选择一个前进方向,一步步向前试探前进,如果碰到死胡同,说明前进方向已无路可走,这时,首先看其它方向是否还有路可走,如果有路可走,则沿该方向再向前试探;如果已无路可走,则返回一步,再看其它方向是否还有路可走;如果有路可走,则沿该方向再向前试探。按此原则不断搜索回溯再搜索,直到找到新的出路或从原路返回入口处无解为止。四皇后问题+问题描述:求出在一个4×4的棋盘上,放置四个不能互相捕捉的“皇后”的所有布局。 1 2 3 41243-四皇后问题,可以采用穷举算法,用四重循环实现。beginfori1:=1to4dofori2:=1to4dofori3:=1to4dofori4:=1to4dobegins[1]:=i1;{s数组存放某行放置皇后的列号},s[2]:=i2;{数组的下标表示行号}s[3]:=i3;s[4]:=i4;if检查是否成立then打印这种布局;end;、同一行和同一对角线上。functioncheck:boolean;vari,j:integer;beginfori:=1to4-1doforj:=i+1to4doif(s[i]=s[j])or(s[i]-i=s[j]-j)or(s[i]+i=s[j]+j)thenbegincheck:=false;exitend;check:=trueend;打印模块:procedureprint;vari:integer;beginfori:=1to4dowrite(s[i]:2);writelnend;八皇后问题问题描述:求出在一个8×8的棋盘上,放置八个不能互相捕捉的“皇后”的所有布局。(2)算法分析:这是来源于国际象棋的一个问题。皇后可以前、后、左、右和沿着对角线方向相互捕捉。如图所示,一个皇后放在棋盘4行3列位置上,棋盘打‘●’的位置就不能再放置皇后。上图提示我们,一个合适的解应是在每列、每行确实有一个皇后,且在一条对角线上最多只有一个皇后。⑴用一维数组表示解,Vars:array[1..8]ofinteger;取下标I表示行,s[I]的内容表示列j。如第3行第5列放一个皇后,则s[3]=5。⑵能放入一个皇后在某行某列必须满足条件同一行、同一列上没有皇后;同一对角线上没有皇后。我们可以用一行一行地放的方法,这样就不用考虑行的问题,设置一个数组 Vara:array[1..8]ofboolean这样用a[j]=true 表示j列上无皇后。右上到左下方向的对角线是否有皇后,这个方向上的对角线有如下特征,行号加列号相等,即I+j相同,变化范围是2..16,可用数组Varb:array[2..16]ofboolean来表示,当b[I+j]=true时表示这条对角线上无皇后。左上到右下方向的对角线是否有皇后,这个方向上的对角线有如下特征,行号减列号相等,即I-j相同,变化范围是-7..7,可用数组Varc: