典型的回溯算法问题
典型的回溯算法问题.txt等余震的心情，就像初恋的少女等情人，既怕他不来，又怕他乱来。 听说女人如衣服，兄弟如手足，回想起来，我竟然七手八脚地裸奔了二十多年！今天心情不好，我只有四句话想说，包括这句和前面的两句，我的话说完了！
典型的回溯算法问题
一、购票问题
有2n个人排队购一件价为0.5元的商品，其中一半人拿一张1元人民币，另一半人拿一张0.5元的人民币，要使售货员在售货中，不发生找钱困难，问这2n个人应该如何排队？找出所有排队的方案。（售货员一开始就没有准备零钱）
分析：
（1）根据题意可以看出，要使售货员在售货中，不发生找钱困难，则在排队中，应该是任何情况下，持0.5元的排在前面的人数多于持1元的人数。
（2）该问题可以用二进制数表示：用0表示持0.5元的人，用1表示持1元的人，那么2n个人排队问题化为2n个0、1的排列问题。这里我们用数组B[1..
2n ] 存放持币情况。
（3）设k是B数组下标指针，B[K]=0或B[K]=1，另用数组d[0]、d[1]记录0与1的个数，且必须满足：n >d[0]>=d[1]。
（4）算法：回溯搜索。
（a）先将B[1]、B[2]、……B[2n]置-1，从第一个元素开始搜索，每个元素先取0，再取1，即B[K]+1→B[K]，试探新的值，若符合规则，增加一个新元素；
（b） 若k<2n，则k+1→k，试探下一个元素，若k=2n则输出B[1]、B[2] ……，B[2n]。
（c）如果B[K]的值不符合要求，则B[K]再加1，试探新的值，若B[K]=2，表示第k个元素的所有值都搜索过，均不符合条件，只能返回到上一个元素B[K-1]，即回溯。
（d）返回到上一个元素k：=k-1 ，并修改D[0]、D[1]。
（5）直到求出所有解。
二、骑士游历问题
在n×n的国际象棋上的某一位置上放置一个马，然后采用象棋中“马走日字”的规则，要求这个马能不重复地走完 n×n
个格子，试用计算机解决这个问题。
分析：
本题是典型的回溯算法问题，设骑士在某一位置，设(X,Y )，按规则走，下一步可以是如图 ( n=5 ) 所示的8个位置之一。
我们将重点考虑前进的方向：如果某一步可继续走下去，就试探着走下去且考虑下一步的走法，若走不通则返回，考虑另选一个位置。
三、四色问题
设有如图1的地图，每个区域代表一个省，区域中的数字表示省的编号，现在要求给每个省涂上红、蓝、黄、白四种颜色之一，同时使相邻的省份以不同的颜
色区分。
图1 图2
分析：
（1）本题是图论中的一个搜索问题，我们可以将该问题简化：将每个省看着一个点，而将省之间的联系看作一条边，可以得到如图2所示图形。
（2）从图2可以知道各省之间的相邻关系，我们可以数据阵列表示——矩阵，即用一个二维数组来表示：
R[x，y ]= 1 表示省 x 与省 y 相邻
0 表示省 x 与省 y 不相邻
由图2可以得到如下矩阵
0 1 0 0 0 0 1
1 0 1 1 1 1 1
0 1 0 1 0 0 0
0 1 1 0 1 0 0
0 1 0 1 0 1 0
0 1 0 0 1 0 1
1 1 0 0 0 1 0
（3）从编号为1的省开始按四种颜色顺序填色，当第一个省颜色与相邻省颜色不同时，就可以确定第一个省的颜色，然后，再依次对第二、第三，……，进行处理，直到所有省份颜色都涂上为止。
（4）问题关键在于在填色过程中，如果即将填的颜色与相邻省的颜色相同，而且四种颜色都试探过，均不能满足要求，则需要回溯到上一个点（即前一个省），修改上一个省的颜色，重新试探下一个省的颜色。
四、填数问题
在n*n 的棋盘上（1<=n<=10）填入1，2，3，……，n*n, 共有n*n 个数，使得任意两个相邻数的和为素数。例如：当n=2时，有：
1 2
4 3
当n=4时，一种可以填写的方案如下表，在这里我们约定：左上角的格子里必须填数字1。程序要求：输入n ；输出
：有多个解，则输出第一行、第一列之和为最小的排列方案；若无解，则输出“NO！”
1 2 11 12
16 15 8 5
13 4 9 14
6 7 10 3
分析：
（1）从问题可以看出这是一个搜索问题，程序中必须完成判断相邻两个数的和是否是素数的任务。
（2）如果一边填数，一边求和及判断素数，程序运行速度将大大减慢，所以我们可以采用数组结构，将2～n*n之间所有素数存放在一个数组中。由于问题中指出n<=10，所以，最大的相邻两个数的和是：99+100<200。我们只需要将2～200之间的素数存放在数组中就可以了。
（3）按行、列填入数据，并求相邻两个数的和，将其与素数数组比较，若是素数，则当前格可以填数，继续填数。若当前格没有数据可以填，则要回溯到上一格，重新填写上一格数据，再进行判断。
数据
结构：
（1）用一个布尔数组T 表示1～n*n之间的数是否用过，false表示没有用过，true表示已经用过。
（2）用一个二维数组A，存放棋盘格子上填数的状态，其中A[1，1]=1。
（3）用一个数组下标指针，表明递归调用层次和回溯的层次。