问题描述：
在7块石头上，有绿、红青蛙各3只， 绿青蛙在左边面向右，红青蛙在右边面向左，中间是个空位。每次移动一只青蛙，青蛙只能往前跳一步，或隔着一只青蛙跳一步，将左边的绿青蛙移动到右边，将右边的红青蛙移动到左边。
解法一迭代回溯法：
#include
#include
typedef int BOOL;
#define TRUE1
#define FALSE0
void iterative_backtrack();// 迭代回溯法求解问题
void recursive_backtrack(int n);// 递归回溯法求问题解
BOOL can_shift(int i);// 判断在第i个石头上青蛙是否能移位
void frog_shift(int i);// 在第i个石头上青蛙是否能移位
int where_empty();// 计算空位的位置
BOOL is_success();// 判断是否已经完成所有移位
void print_result();// 打印结果
#define EMPTY0// 表示空位
#define GREEN1// 表示绿青蛙
#define RED2// 表示红青蛙
#define NUM7// 表示石头数
#define MAXSTEP24// 完成移位可能需要的步数
/* stone[i]表示第i块石头上的物体 */
static int stone[NUM] = {GREEN, GREEN, GREEN, EMPTY, RED, RED, RED};
/* step[i]表示第i步骤时，哪块石头上的青蛙进行了移位 */
static int step[MAXSTEP];
int main() {
int i;
/* 遇到step[i]的值为-1时，表示该步骤未被执行 */
for (i = 0; i < MAXSTEP; i++)
step[i] = -1;
iterative_backtrack();
return EXIT_SUCCESS;
}
/*
** 迭代回溯法求解
*/
void iterative_backtrack() {
int n = 0;// 迭代的深度，即执行的步骤数
int i = 0;// 当前将进行移位的青蛙的位置
int frog_pos[MAXSTEP];// 保存每一步骤将进行移位的青蛙的位置
int empty_pos[MAXSTEP];// 保存没一步骤空位的位置
while(TRUE) {
/* 寻找第一只能够移位的青蛙 */
while (i < NUM && !can_shift(i))
i++;
/* 如果存在能够移位的青蛙 */
if (i < NUM) {
/* 保存当前将进行移位的青蛙的位置 */
frog_pos[n] = i;
/* 保存当前空位的位置 */
empty_pos[n] = where_empty();
/* 记录第n步骤时，第i块石头上的青蛙进行移位 */
step[n] = i;
/* 第i块石头上的青蛙进行移 */
frog_shift(i);
/* 如果已经完成所有青蛙的正确移位 */
if (is_success()) {
print_result();// 打印结果
n++;// 进行下一步骤
}
/* 如果还未完成所有青蛙的正确移位 */
else {
n++;// 进行下一步骤
i = 0;// 从第0块石头上的青蛙开始迭代
}
}
/* 如果每一块石头上的青蛙都不能进行移位 */
else {
/* 回溯至上一步骤，如果是回溯至第-1步骤时，结束迭代 */
if (–n < 0)
break;
frog_shift(empty_pos[n]);// 将上一步骤进行移位的青蛙移回原处
i = frog_pos[n] + 1;// 从下一块石头的青蛙开始迭代
}
}
}
/*
** 判断在第i个石头上青蛙是否能移位
*/
BOOL can_shift(int i) {
int empty_pos = where_empty();
switch(stone[i]) {
/*
** 绿青蛙从左往右跳，如果前面两块石头中有个空位，那么该青蛙能够移位
** 红青蛙从右往左跳，如果前面两块石头中有个空位，那么该青蛙能够移位
*/
case GREEN:
if (empty_pos > i && empty_pos <= i + 2)
return TRUE;
break;
case RED:
if (empty_pos < i && empty_pos >= i – 2)
return TRUE;
break;
case EMPTY:
default:
return FALSE;
break;
}
return FALSE;
}
/*
** 在第i块石头上的青蛙进行移位
*/
void frog_shift(int i) {
int empty_pos = where_empty();
stone[empty_pos] = stone[i];
stone[i] = EMPTY;
}
/*
** 计算空位的位置
*/
int where_empty() {
int i;
for (i = 0; i < NUM; i++)
if (stone[i] == EMPTY) break;
return i;
}
/*
** 判断是否已经完成所有移位
*/
BOOL is_success() {
if (stone[0] == RED &&
stone[1] == RED &&
stone[2] == RED &&
stone[3] == EMPTY &&
stone[4] == GREEN &&
stone[5] == GREEN &&
stone[6] == GREEN)
return TRUE;
return FALSE;
}
/*
** 打印结果
*/
void print_result() {
int i;
for (i = 0; i < MAXSTEP; i++) {
if (step[i] == -1)
break;
printf("%d ", step[i]);
}
putchar('\n');
}
解法二递归回溯法：
#include
#include
typedef int BOOL;
#define TRUE1
#define FALSE0
void iterative_backtrack();// 迭代回溯法求解问题
void recursive_backtrack(int n);// 递归回溯法求问题解
BOOL can_shift(int i);// 判断在第i个石头上青蛙是否能移位
void frog_shift(int i);// 在第i个石头上青蛙是否能移位
int where_empty();// 计算空位的位置
BOOL is_success();// 判断是否已经完成所有移位
void print_result();// 打印结果
#define EMPTY0// 表示空位
#define GREEN1// 表示绿青蛙
#define RED2// 表示红青蛙
#define NUM7// 表示石头数
#define MAXSTEP24// 完成移位可能需要的步数
/* stone[i]表示第i块石头上的物体 */
static int stone[NUM] = {GREEN, GREEN, GREEN, EMPTY, RED, RED, RED};
/* step[i]表示第i步骤时，哪块石头上的青蛙进行了移位 */
static int step[MAXSTEP];
int main() {
int i;
/* 遇到step[i]的值为-1时，表示该步骤未被执行 */
for (i = 0; i < MAXSTEP; i++)
step[i] = -1;
recursive_backtrack(0);
return EXIT_SUCCESS;
}
/*
** 递归回溯法求解
** n表示递归的深度数，即执行的步骤
*/
void recursive_backtrack(int n) {
int i;
int original_empty_pos;
if (is_success()) {
print_result();
} else {
/* 从第0块石头上的青蛙逐一尝试 */
for (i = 0; i < NUM; i++) {
/* 如果第i块石头上的青蛙能够进行移位 */
if (can_shift(i)) {
/* 记录青蛙移位前，空位的位置 */
original_empty_pos = where_empty();
/* 记录第n步骤时，第i块石头上的青蛙进行移位 */
step[n] = i;
/* 第i块石头上的青蛙进行移位 */
frog_shift(i);
/* 执行下一步骤，第n+1步骤 */
recursive_backtrack(n+1);
/* 回溯，将青蛙移回原来的位置 */
frog_shift(original_empty_pos);
}
}
}
}
/*
** 判断在第i个石头上青蛙是否能移位
*/
BOOL can_shift(int i) {
int empty_pos = where_empty();
switch(stone[i]) {
/*
** 绿青蛙从左往右跳，如果前面两块石头中有个空位，那么该青蛙能够移位
** 红青蛙从右往左跳，如果前面两块石头中有个空位，那么该青蛙能够移位
*/
case GREEN:
if (empty_pos > i && empty_pos <= i + 2)
return TRUE;
break;
case RED:
if (empty_pos < i && empty_pos >= i – 2)
return TRUE;
break;
case EMPTY:
default:
return FALSE;
break;
}
return FALSE;
}
/*
** 在第i块石头上的青蛙进行移位
*/
void frog_shift(int i) {
int empty_pos = where_empty();
stone[empty_pos] = stone[i];
stone[i] = EMPTY;
}
/*
** 计算空位的位置
*/
int where_empty() {
int i;
for (i = 0; i < NUM; i++)
if (stone[i] == EMPTY) break;
return i;
}
/*
** 判断是否已经完成所有移位
*/
BOOL is_success() {
if (stone[0] == RED &&
stone[1] == RED &&
stone[2] == RED &&
stone[3] == EMPTY &&
stone[4] == GREEN &&
stone[5] == GREEN &&
stone[6] == GREEN)
return TRUE;
return FALSE;
}
/*
** 打印结果
*/
void print_result() {
int i;
for (i = 0; i < MAXSTEP; i++) {
if (step[i] == -1)
break;
printf("%d ", step[i]);
}
putchar('\n');
}
结果输出：
2 4 5 3 1 0 2 4 6 5 3 1 2 4 3
4 2 1 3 5 6 4 2 0 1 3 5 4 2 3