4种吃子跳棋

大家好，欢迎来到IT知识分享网。

目录

一，双玩家单目吃子跳棋

玻璃跳棋

国际跳棋

二，双玩家多目吃子跳棋

大人物跳棋

三，单玩家单目吃子跳棋

智力游戏67跳棋（5）

跳瓶盖

智力游戏——中国跳棋（5-26）

四，单玩家多目吃子跳棋——Hopping dots

1，Hopping dots

2，规则

3，问题的简化

（3.1）局面的数量

（3.2）编号

（3.3）记录所有的边（不考虑方向）

（3.4）深度优先搜索的可能性分析

4，原问题的求解

---

一，双玩家单目吃子跳棋

玻璃跳棋

在线play

规则：棋子只能斜着往前移动一步，或者连续吃子若干次。

吃子不限制方向，且可以连续进行。

棋子到达对方底线可以变成皇后，皇后可以无视1格距离的限制。

要想消灭一个皇后还不太容易，首先要尽可能多的把棋子变成皇后，然后设局卡住对方皇后，使其不能在边缘苟着。

示例：

到了这一步，3个皇后就把对方的皇后完全堵死了。

国际跳棋

规则和上面的玻璃跳棋一样。

二，双玩家多目吃子跳棋

大人物跳棋

在线paly

规则：

（1）人物可以跳到自己的相邻的棋子上，有人物的棋子到达对方底线则获胜，或者把对方棋子吃完获胜。

（2）普通棋子只能斜着往前移动一步或者连续吃子若干次。有人物的棋子可以斜着往前移动或吃子，也可以斜着往后移动或吃子。

（3）普通棋子到达对方底线则变成双子，可以斜着往前，也可以斜着往后。

到了这一步，后面很快就赢了。 

三，单玩家单目吃子跳棋

单玩家吃子跳棋就是要把所有棋子吃掉，只剩下最后一个棋子。

独立钻石棋就是典型的单玩家吃子跳棋，而且独立钻石棋是初始只有1个缺口。

本章只收录单玩家单目吃子跳棋中，不止1个缺口的棋类puzzle。

智力游戏67跳棋（5）

不得不说，这个游戏很难，而且编程也很难。

花了不少功夫，才得到一个勉强给出解的程序。

最难的地方就是，如何避免死循环，也就是（2,0）和（3,1）之间一直跳转的死循环

代码：

#include<iostream> using namespace std; int number = 4; bool move(int list[][5], int i, int j) //判断是否能够从（i,j）开始跳，最多只用number步 { if (list[i][j] == 0)return false; int save[5][5], save_number = number; for (int i = 0; i < 5; i++) //保存list，用于回溯的时候还原list for (int j = 0; j < 5; j++)save[i][j] = list[i][j]; if (number <= 0) { int sum = 0; //判断是不是已经成功了 for (int i = 0; i < 5; i++)for (int j = 0; j < 5; j++)sum += list[i][j]; if (sum == 1 && list[2][2] == 1)return true; return false; } if (i>1 && list[i - 1][j] == 1 && list[i - 2][j] == 0) //满足往上跳的条件 { list[i][j]--; list[i - 1][j]--; list[i - 2][j]++; if (move(list, i - 2, j)) { cout << i << " 上 " << j << endl; return true; } } else if (i<3 && list[i + 1][j] == 1 && list[i + 2][j] == 0) //满足往下跳的条件 { list[i][j]--; list[i + 1][j]--; list[i + 2][j]++; if (move(list, i + 2, j)) { cout << i << " 下 " << j << endl; return true; } } else if (j>1 && list[i][j - 1] == 1 && list[i][j - 2] == 0) //满足往左跳的条件 { list[i][j]--; list[i][j - 1]--; list[i][j - 2]++; if (move(list, i, j - 2)) { cout << i << " 左 " << j << endl; return true; } } else if (j<3 && list[i][j + 1] == 1 && list[i][j + 2] == 0) //满足往右跳的条件 { list[i][j]--; list[i][j + 1]--; list[i][j + 2]++; if (move(list, i, j + 2)) { cout << i << " 右 " << j << endl; return true; } } else if (i>1 && j>1 && list[i - 1][j - 1] == 1 && list[i - 2][j - 2] == 0) //满足往左上跳的条件 { list[i][j]--; list[i - 1][j - 1]--; list[i - 2][j - 2]++; if (move(list, i - 2, j - 2)) { cout << i << " 左上 " << j << endl; return true; } } else if (i<3 && j>1 && list[i + 1][j - 1] == 1 && list[i + 2][j - 2] == 0) //满足往左下跳的条件 { list[i][j]--; list[i + 1][j - 1]--; list[i + 2][j - 2]++; if (move(list, i + 2, j - 2)) { cout << i << " 左下 " << j << endl; return true; } } else if (i>1 && j<3 && list[i - 1][j + 1] == 1 && list[i - 2][j + 2] == 0) //满足往右上跳的条件 { list[i][j]--; list[i - 1][j + 1]--; list[i - 2][j + 2]++; if (move(list, i - 2, j + 2)) { cout << i << " 右上 " << j << endl; return true; } } else if (i<3 && j<3 && list[i + 1][j + 1] == 1 && list[i + 2][j + 2] == 0) //满足往右下跳的条件 { list[i][j]--; list[i + 1][j + 1]--; list[i + 2][j + 2]++; if (move(list, i + 2, j + 2)) { cout << i << " 右下 " << j << endl; return true; } } number--; for (int ii = 0; ii < 5; ii++) //还有8个方向都跳不了的情况，以及可以跳但是我选择不跳的情况 for (int jj = 0; jj < 5; jj++) { if (ii == i&&jj == j)continue; if (move(list, ii, jj))return true; } for (int i = 0; i < 5; i++)for (int j = 0; j < 5; j++)list[i][j] = save[i][j];//还原list number = save_number; return false; } int main() { int list[5][5]; //list用来表示状态，0表示空格，1表示有棋子 for (int i = 0; i < 5; i++) for (int j = 0; j < 5; j++) { if (i == 1 || i == 3 || j == 1 || j == 3)list[i][j] = 1; else list[i][j] = 0; } list[2][2] = 1; move(list, 2, 2); cout << endl << "注意，输出的顺序是反着的"; system("pause>nul"); return 0; }

输出：

4 右上 2
2 右下 0
2 左 2
0 左下 4
2 上 4
4 上 4
4 右 2
4 右 0
2 下 0
0 左下 3
1 右 0
3 左上 2
0 左 2
2 上 2
注意，输出的顺序是反着的

跳瓶盖

在线play

（7）

  

（11）

  

（13）

  

智力游戏——中国跳棋（5-26）

规则和独立钻石棋是一样的，只是棋子的数量不一样而已。

10（5）

用本科毕业设计里面的代码，可以复刻一个一样的出来，只需要把关卡转化成配置，即可用棋谱表示整个操作。

PS：没有这个代码当然也可以用一堆数字表示答案，但是不好看，有这个代码就可以一步步看到效果。

（1）配置

独立钻石棋
row=7 col=7
棋盘格点board[][]=
-1 -1 0 0 0 -1 -1
-1 -1 0 2 0 -1 -1
 0  0  2 1 2 0 0
 0  0  0 2 0  0  0
 0  0  0 1 0  0  0
-1 -1 0 0 0 -1 -1 
-1 -1 0 0 0 -1 -1
棋盘样式boardStyle=1
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
棋子样式chessman=0表示用●和▲代表双方棋子
额外显示内容displayContent=2
轮到谁下turn=1
如何换下棋方howToChangeTurn=1表示只有一方
行棋方式playMod=1
moveMod=1
moveOkMod=4
是否结束具体规则ifEndMod=7

（2）运行

（3）答案

3 4 3 2 5 4 3 4 3 5 3 3 3 2 3 4 2 4 4 4

PS：除了棋盘格点board[][]之外，其他的都和独立钻石棋完全相同，后面我就只把board列出来了。运行结果我也会省略掉，反正都和游戏截图相同。

36（6）

（1）配置

棋盘格点board[][]=
-1 -1 0 0 0 -1 -1
-1 -1 0 2 0 -1 -1
 0  0  0 1 0 0 0
 0  2  1 2 1 2  0
 0  0  0 1 0  0  0
-1 -1 0 2 0 -1 -1 
-1 -1 0 0 0 -1 -1

（2）答案

4 5 4 7 4 3 4 5 6 4 4 4 4 4 4 6 4 7 4 5 2 4 4 4 4 5 4 3 4 2 4 4

66（7）

（1）配置

棋盘格点board[][]=
-1 -1 0 1 0 -1 -1
-1 -1 0 2 0 -1 -1
0 0 2 1 2 0 0
1 2 1 0 1 2 1
0 0 2 1 2 0 0
-1 -1 0 2 0 -1 -1 
-1 -1 0 1 0 -1 -1

（2）答案

4 3 2 3 2 4 4 4 4 5 2 5 4 1 4 3 5 3 3 3 3 3 1 3 1 3 1 5 1 5 3 5 4 7 4 5 5 4 5 6 3 5 5 5 7 4 5 4 4 4 6 4 5 6 5 4 6 4 4 4

PS：在我写毕设的程序之前，也就是大学的时候，我按照独立钻石棋中的方法，给出了这关的答案，如下图所示。

162（8）

（1）配置

棋盘格点board[][]=
-1 -1 0 0 0 -1 -1
-1 -1 0 2 0 -1 -1
0 0 2 1 2 0 0
0 2 1 0 1 2 0
0 0 2 1 2 0 0
-1 -1 0 2 0 -1 -1 
-1 -1 0 0 0 -1 -1

（2）答案

6 4 4 4 4 5 6 5 4 3 4 5 3 5 5 5 6 5 4 5 4 6 4 4 3 4 3 2 3 2 5 2 5 2 5 4 5 4 3 4 2 4 4 4

169（9）

（1）配置

棋盘格点board[][]=
-1 -1 0 0 0 -1 -1
-1 -1 0 0 0 -1 -1
0  0  2 0 2 0 0
0  2  1 2 1 2 0
0  0  2 1 2 0 0
-1 -1 0 2 0 -1 -1 
-1 -1 0 0 0 -1 -1

（2）答案

5 4 3 4 3 4 3 2 3 2 5 2 5 2 5 4 6 4 4 4 4 5 6 5 4 3 4 5 3 5 5 5 6 5 4 5 4 6 4 4

175（10）

（1）配置

棋盘格点board[][]=
-1 -1 0 0 0 -1 -1
-1 -1 0 0 0 -1 -1
0  0  0 1 0 0 0
0  0  1 2 1 0 0
0  1  2 1 2 1 0
-1 -1 0 0 0 -1 -1 
-1 -1 0 0 0 -1 -1

（2）答案

5 3 3 3 3 3 3 5 5 5 5 3 5 2 5 4 4 4 6 4 3 5 5 5 5 6 5 4 6 4 4 4

181（11）

（1）配置

棋盘格点board[][]=
-1 -1 0 0 2 -1 -1
-1 -1 0 2 1 -1 -1
0   1  0 1 2 1 0
0   0  1 2 1 0 0
0   1  2 1 0 1 0
-1 -1 1 2 0 -1 -1 
-1 -1 1 0 0 -1 -1

（2）答案

3 5 5 5 5 3 3 3 3 3 3 5 5 5 5 3 5 2 5 4 7 3 5 3 3 6 3 4 1 5 3 5 3 5 3 3 3 2 3 4 5 3 5 5 3 4 5 4 6 4 4 4 5 6 5 4 5 4 3 4 2 4 4 4

187（12）

194（13）

200（14）

下面的方法，原则上来说和上面的是一样的，只不过执行顺序有一点点不一样而已。

上面的是计算机求出来的，但是下面的更符合人性化的思维，比如连跳不应该拆开，同理，除了最后几步之外，上面一半和下面一半的移动比较独立，也不应该像上面那样交叉进行。

206（15）

212（16）

217（17）

223（18）

这个很对称，解法也是对称的。

对称的：

继续对称：

这样，这个图就和162（8）一样了。

 228（19）

232（20）

233（21）

左边3步，右边3步，变成下图：

这样就化成了187中国跳棋（12）

234（22）

237（23）

239（24）

上边3步，下边3步，变成下图：

这样就化成了206中国跳棋（15）

252（25）

左右对称式的解法：

255（26）

这一关和243中国跳棋（1）是一样的

过关之后：

四，单玩家多目吃子跳棋——Hopping dots

这一章，我想完整的讨论一个游戏，叫Hopping dots，被翻译为逻辑难题。

关键词：独立钻石棋、深度优先搜索、可能性分析、状态压缩、动态规划的备忘录方法

1，Hopping dots

 APK下载链接（Hopping dots 1.1）：资源分享汇总_nameofcsdn的博客-CSDN博客

游戏界面（下图为第一关）

棋盘：由13个点组成

棋子：1个红子和若干个绿子

2，规则

按照独立钻石棋的规则进行吃子，最后只剩下一个子，且为红子，即为胜利。（无论红子在何处）

这是我自己总结的规则，非常简洁，初一看貌似不准确，仔细一想实际上和官方的定义是一样的。

棋子最多有12个，最少有1个。

13个棋子肯定是死局面（无法胜利的局面），因为没法进行操作。

12个棋子的局面中，存不存在活局面（能够胜利的局面），这个暂且不知。

每次操作，棋子数量都是少1，所以，任何局面，最多只能再进行11次操作。

3，问题的简化

问题的简化版：只有绿子没有红子，只要最后只剩下一个子即为胜利（同样不论位置）

这样的版本就更接近独立钻石棋了，对于玩家来说，原问题和问题的简化版差异并不是很大，玩起来难度差不多。而对于想做理论分析的笔者来说，原问题分析起来很繁琐，掩盖了很多规律。

如果只是想直接尝试编写深度优先搜索的程序解决问题，其实是不需要简化的，但是如果要严谨一些，先从理论上分析可能性大小，所以如此简化正是第一步要做的事情。

（3.1）局面的数量

有13个点是可能有子的，所以局面的数量为2^13=8192

其中还包括了大量的死局面，具体有多少活局面，我们并不关心。

（3.2）编号

（3.3）记录所有的边（不考虑方向）

不难数出，一共有16条边

以2、6、8、12为中点的边各有1条，如1-2-3

以4、5、9、10为中点的边各有2条，如1-4-7，2-4-6

以7为中点的边有4条，如2-7-12，4-7-10

之所以不考虑方向，是因为任何时刻，一条边最多对应一种可行操作，

以边1-2-3为例，同一局面下，“从1跳到3”和“从3跳到1”不可能都是可行的操作。

注意到，每条边的3个数都是等差数列，所以一条边只需要2个数字记录下来起点和终点，

这样，便可以用2个长度为16的数组来记录下16条边了。

int st[16] = { 1, 1, 3, 11, 1, 2, 2, 3, 6, 7, 8, 7, 4, 5, 6, 2 }; int en[16] = { 3, 11, 13, 13, 7, 6, 8, 7, 12, 11, 12, 13, 10, 9, 8, 12 };

（3.4）深度优先搜索的可能性分析

因为最多只能进行11次操作，所以深度优先搜索的深度不深。现在需要计算的是，每一次操作有多少种选择？

（3.4.1）任一局面有多少种选择

我们需要一个函数，输入一个局面，输出一个数值，告诉我们有多少种选择。

如何输入呢？使用状态压缩最为方便。

13个点，每个点对应一位，1表示有子，0表示没有子，这样，8192个局面便可以和8192个13位二进制数一一对应了。

输入之后，函数就可以直接计算出有多少种选择了，时间为O（1）

有了这个函数，只要从0到8191枚举n，就能求出f（n）的最大值了，结果是10

代码：

#include <iostream> using namespace std; int st[16] = { 1, 1, 3, 11, 1, 2, 2, 3, 6, 7, 8, 7, 4, 5, 6, 2 }; int en[16] = { 3, 11, 13, 13, 7, 6, 8, 7, 12, 11, 12, 13, 10, 9, 8, 12 }; int f(int n) { int r = 0, s, e, m; for (int i = 0; i < 16; i++) { s = st[i], e = en[i], m = (s + e) / 2; if ((n >> (13 - m)) & 1)r += ((n >> (13 - s)) & 1) ^ ((n >> (13 - e)) & 1); } return r; } int main() { int maxx = 0; for (int n = 0; n < 8192; n++)if (maxx < f(n))maxx = f(n); cout << maxx; return 0; }

（3.4.2）深度优先搜索的复杂度

前面分别算出，一个局面最多能再进行11次操作，每次操作最多10种选择，那么，用深度优先搜索解决这个问题最多需要10^11次枚举计算。这是一个很大的数，普通的笔记本要算很久。

然而，我们不难发现，并非每次操作都有10种选择，比如只剩2个子的时候最多只有2种选择。

那么如果一个局面有k（1<k<13）个子，这个局面最多有多少种选择？

只需利用上面的函数f即可。

代码：

#include <iostream> using namespace std; int st[16] = { 1, 1, 3, 11, 1, 2, 2, 3, 6, 7, 8, 7, 4, 5, 6, 2 }; int en[16] = { 3, 11, 13, 13, 7, 6, 8, 7, 12, 11, 12, 13, 10, 9, 8, 12 }; int num[14];//k个棋子的所有局面中最多有多少种选择 void f(int n) { int r = 0, s, e, m, k = 0; for (int i = 0; i < 16; i++) { s = st[i], e = en[i], m = (s + e) / 2; if ((n >> (13 - m)) & 1)r += ((n >> (13 - s)) & 1) ^ ((n >> (13 - e)) & 1); } while (n) { k += n & 1; n /= 2; } if (num[k] < r)num[k] = r; } int main() { for (int i = 0; i < 14; i++)num[i] = 0; for (int n = 0; n < 8192; n++) f(n); for (int i = 2; i <= 12; i++)cout << num[i] << " "; return 0; }

运行结果：

2  4  7  7  9  10  9  9  8  6  4

2*4*7*7*9*10*9*9*8*6*4=，所以任何一个局面，进行深度优先搜索的话，最多需要约5亿次枚举计算

计算机一秒可以进行约1亿次计算，所以这个时间是可以接受的。

4，原问题的求解

原问题由于有红子的限制，所以编程起来要复杂一些，但是需要枚举的情况少一些。

这样，就可以深度优先搜索求解了，同时，因为局面的数量很有限，所以用动态规划的备忘录方法来避免重复工作。

代码：

#include <iostream> #include<stack> using namespace std; int r[8192][14];//0表示未知，-1表示死局面，1表示活局面 int st[16] = { 1, 1, 3, 11, 1, 2, 2, 3, 6, 7, 8, 7, 4, 5, 6, 2 }; int en[16] = { 3, 11, 13, 13, 7, 6, 8, 7, 12, 11, 12, 13, 10, 9, 8, 12 }; stack<int>ans; bool f(int n, int k) { if (n == (n&-n))return true;//只有1个子 if (r[n][k] < 0)return false; int s, e, m; for (int i = 0; i < 16; i++) { s = st[i], e = en[i], m = (s + e) / 2; if (m == k)continue;//红子不能被跳过 if (!((n >> (13 - m)) & 1))continue; if (!(((n >> (13 - s)) & 1) ^ ((n >> (13 - e)) & 1)))continue; int nn, kk = k, tem; if (k == s || k == e)kk = s + e - k; tem = (1 << (13 - s)) + (1 << (13 - e)); nn = n - (n&tem) + tem - (n&tem) - (1 << (13 - m)); if (f(nn, kk)) { ans.push(i); m = -1; break; } } if (m == -1)return true; r[n][k] = -1; return false; } int main() { int n = 0, k;//n表示无颜色局面，k表示红子位置 cout << "按照编号\n1 2 3\n 4 5\n6 7 8\n 9 10\n11 12 13\n"; cout << "即从上到下，从左往右，依次输入每个格子\n1表示有子，0表示没有子，全部用空格隔开\n"; for (int i = 1; i <= 13; i++) { cin >> k; n = n * 2 + k; } cout << "输入红子所在格子的序号（1-13）\n"; cin >> k; for (int i = 0; i < 8192; i++)for (int j = 0; j < 14; j++)r[i][j] = 0; while (!ans.empty())ans.pop(); f(n, k); cout << "答案为：（一行表示一次操作，每行2个整数分别代表起点和终点的序号）\n"; while (!ans.empty()) { int i = ans.top(); ans.pop(); cout << st[i] << " " << en[i] << endl; } return 0; }

示例：