如何用C语言实现移动跳棋谜题的成对移动逻辑
移动跳棋C实现核心逻辑拆解
移动规则的无歧义判定(基于参考步骤反推)
- 数组长度固定为10,元素仅含
0(空位)、b(黑棋)、w(白棋),初始状态为{0,0,0,0,'b','w','b','w','b','w'},目标状态为{'w','w','w','b','b','b',0,0,0,0} - 合法移动的两个核心判定条件:
- 待移动单元:必须是相邻的两个非0元素,组成有序对
(a,b),两者的相对顺序在移动中不能改变 - 目标放置单元:必须是相邻的两个空位0组成的连续空位对,不存在跨空位插入的情况
- 待移动单元:必须是相邻的两个非0元素,组成有序对
- 移动操作的执行逻辑(核心注意:其他位置的元素完全不发生移位联动):
- 定位待移动对的起始下标
s(两个元素分别位于s和s+1位置) - 定位空位对的起始下标
t(两个空位分别位于t和t+1位置) - 将待移动对的值写入空位对位置:
arr[t] = arr[s]; arr[t+1] = arr[s+1]; - 将原待移动对的位置清零:
arr[s] = 0; arr[s+1] = 0;
- 定位待移动对的起始下标
通用移动逻辑的实现思路
- 状态存储:直接用长度为10的char数组存储当前状态,每次移动前拷贝一份当前数组做状态备份,避免非法操作覆盖原有状态。
- 待移动对遍历:遍历数组所有可能的相邻对(下标从0到8),筛选出满足
arr[i] != 0 && arr[i+1] != 0的所有下标s,这些就是所有可选的待移动对位置。 - 空位对遍历:同样遍历数组所有可能的相邻对,筛选出满足
arr[i] == 0 && arr[i+1] == 0的所有下标t,这些就是所有可放置的目标位置。 - 操作执行:对每一组合法的
s和t,执行上述移动操作生成新状态,再判断新状态是否匹配目标。
注意:需要排除待移动对和空位对重叠的无效情况(比如
s == t时,相当于原地无操作,直接跳过即可)。
核心代码示例(移动操作模块)
#include <string.h> // 执行一次合法移动:将s位置的相邻非0对移动到t位置的相邻空位对 void move_pair(char arr[10], int s, int t) { // 备份待移动对的值 char a = arr[s]; char b = arr[s+1]; // 原位置清零 arr[s] = 0; arr[s+1] = 0; // 写入空位对位置 arr[t] = a; arr[t+1] = b; } // 遍历当前状态下的所有合法移动,生成所有后续状态 void get_all_legal_moves(char current[10], char next_states[][10], int *state_count) { *state_count = 0; // 收集所有待移动对的起始下标 int s_list[9], s_cnt = 0; for(int i = 0; i < 9; i++) { if(current[i] != 0 && current[i+1] != 0) { s_list[s_cnt++] = i; } } // 收集所有空位对的起始下标 int t_list[9], t_cnt = 0; for(int i = 0; i < 9; i++) { if(current[i] == 0 && current[i+1] == 0) { t_list[t_cnt++] = i; } } // 遍历所有s、t组合,生成移动后的新状态 for(int s_idx = 0; s_idx < s_cnt; s_idx++) { for(int t_idx = 0; t_idx < t_cnt; t_idx++) { int s = s_list[s_idx]; int t = t_list[t_idx]; // 跳过无意义的原地移动 if(s == t) continue; // 拷贝当前状态,执行移动 memcpy(next_states[*state_count], current, 10 * sizeof(char)); move_pair(next_states[*state_count], s, t); (*state_count)++; } } }
常规排序算法不适用的原因
常规排序的操作单元是单个元素,通过相邻交换、插入移位逐步调整单元素位置,但这个谜题的操作单元是固定顺序的成对元素,且移动时其他位置不发生联动移位,操作约束和单元素排序完全不同,因此无法直接套用冒泡、归并等排序逻辑。
内容的提问来源于stack exchange,提问作者Nerf D。
相关产品推荐
相关产品推荐

