3种吃子跳棋
目录
一，双玩家吃子跳棋
玻璃跳棋
二，单玩家吃子跳棋
智力游戏67跳棋（5）
一个挑战
跳瓶盖
三，单玩家多目吃子跳棋——Hopping dots
1，Hopping dots
2，规则
3，问题的简化
（3.1）局面的数量
（3.2）编号
（3.3）记录所有的边（不考虑方向）
（3.4）深度优先搜索的可能性分析
4，原问题的求解
一，双玩家吃子跳棋
玻璃跳棋
在线play
规则：棋子只能斜着往前移动一步，或者连续吃子若干次。
吃子不限制方向，且可以连续进行。
棋子到达对方底线可以变成皇后，皇后可以无视1格距离的限制。
要想消灭一个皇后还不太容易，首先要尽可能多的把棋子变成皇后，然后设局卡住对方皇后，使其不能在边缘苟着。
示例：
到了这一步，3个皇后就把对方的皇后完全堵死了。
二，单玩家吃子跳棋
独立钻石棋就是典型的单玩家吃子跳棋，而且独立钻石棋是初始只有1个缺口。
智力游戏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，用于回溯的时候还原listfor (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
注意，输出的顺序是反着的
一个挑战
Taptap游戏，只有一关。
任选一个格子去掉棋子，变成空格，然后按照独立钻石棋的规则消除棋子，最后只剩一颗棋子。
先选中第四行第一个格子消掉，然后再把上面的消掉：
跳瓶盖
在线play
（7）
（11）
（13）
三，单玩家多目吃子跳棋——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=548674560，所以任何一个局面，进行深度优先搜索的话，最多需要约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;
}示例：
