文档介绍：回溯搜索回溯是一种模拟人类思维过程的算法思想。它的基本方法是:按照深度优先的顺序向下一层扩展结点;扩展到某一层时,若已无法继续扩展且仍未找到解,则退回到父结点, 从父结点的下一个分支开始,按同样的策略继续扩展……, 直到找到问题的解或证明无解。 在4 ×4方格的棋盘内,放置四个皇后,使得任意两个皇后不在同一行、同一列、同一条对角线上。请找出所有的摆法。分析: 如果我们把4 *4的棋盘看成是一个平面直角坐标系,那么任意两个皇后在平面上的坐标应同时满足以下三个条件: ⑴两个皇后的横坐标(行号)不相等。⑵两个皇后的纵坐标(列号)不相等。⑶两个皇后的横坐标之差的绝对值不等于纵坐标之差的绝对值。 I≠KX[I] ≠ X[K] |I-K| ≠|X[I]-X[K]| 例1、四皇后问题我们用数组 x[i] 来描述四个皇后在棋盘上的状态, x[i] =j 表示在第 i行的第 j列放置了一个皇后。(演示) 空棋盘 134- 1--- 11-- 12-- 13-- 131- 132- 133- 14-- 141- 142- 143- 144- 2--- 21-- 22-- 23-- 24-- 241- 2411 2412 2413 绿色方框表示搜索过程中生成的合法结点,红色方框表示尝试生成的非法结点. 在回溯算法中,无论搜索进行到哪一结点,都只需要保存根结点到当前结点之前的路径,而不需要保存其他分支,因此只需要一个线性表即可保存搜索的“历程”.在向纵深方向扩展结点时,结点是按照访问顺序逐一处理的;在回溯时,. const n=4; var i,j, k :integer; {K是栈顶指针} x:array[1..n] of integer;{ 栈} function place(k:integer): boolean ; var i:integer; begin place:=true; for i:=1 to k-1 do if ( )or (abs(x[i]-x[k])=abs(i-k)) then place:=false ; end; procedure print; { 输出一种方案} var i:integer; begin for i:=1 to n do write(x[i]:4); writeln ; end; begin k:=1; {摆放第一个皇后} x[k]:=0; {保存第 k个皇后的列号} while ( ) do {栈非空时} begin x[k]:=x[k]+1; while(x[k]<=n)and( ) do x[k]:=x[k]+1; {尝试第 k行下一列} if ( ) then k:=k-1 { 回溯} else if k=n then ( ) else begin { 摆放下一个皇后} ( ); x[k]:=0 end end ; end. x[i]=x[k] k>0 not place(k) x[k]>n print k:=k+1 不满足约束条件 0k 1 0123 012344 012 01 23 4342 12 34 0 1 01230 例2、数字排列问题列出所有从数字 1到数字 n的连续自然数的排列,要求所产生的任一数字序列中不能出现重复的数字. 输入:n( 1<=n<=9 ) 输出:由 1~n组成的所有不重复的数字序列,每行一个序列. 样例 输入: 3 输出: 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 begin readln (n); k:=1; x[k]:=0; while k>0 do begin x[k]:=x[k]+1; while ( ) and (not place(k)) do x[k]:=x[k]+1; if x[k]>n then( )