一笔画

近期无聊，itouch上下了一个一笔画游戏，琢磨几下，发现稍微用了一点数学知识，通关还是蛮容易的。

规则

规则跟游戏名字一样，使用一条线不重复地遍历完图形的所有边。游戏截图如下：

图1

我可以通过以下图中所示的路线，完成这局游戏（S代表起点）。

图2

玩游戏的过程也是思考的过程，当通关或者是从中悟出解决办法的时候，会很兴奋。

假设从一个很小白的角度来玩一笔画，一般步骤会怎么样。

1. 随便找一个起点，开始寻找一条路径；
2. 倘若找不到解法，可以有2个选择，一种是换个起点，一种是从这个起点开始寻找其他路径

步骤很简单，如果使用程序来寻找解法，那么可以大概抽象成比较简单的深搜（可以参考文章【算法入门】深度优先搜索(DFS)）的过程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

//深搜
bool DFS(Node node){
  neighbour = node.getNeighbour();//获取相邻节点，条件是该节点跟node节点的边未被访问
 
  if (neighbour.length == 0 && allEdgeVisit == true){
    return true;//如果再也找不到邻居，并且所有边都被访问了。
  }
  foreach (neighbour as nextNode){
    setVisit(node, nextNode);//设置成访问过
    if (DFS(neighbour)){
      return true;
    }
    setNotVisit(node, nextNode);//设置成未访问
  }
  return false;//无解
}
 
foreach (nodeList as node){
  if (DFS(node)){
    //找到解法
  }
}

显然对于这个游戏来说，如果用计算机来求解，瞬间秒杀。
但是对于人类来说，我们并不能满足这样粗暴的解法，如果要人类去做这样枯燥的搜索解的做法，是很让人泄气的。

于是我们需要变通一下，那就是我们得去思考怎么样去减少那些不必要的路径搜索，也就是尽量尝试一些更容易成功的路线。

我们这样是在尝试寻找一种方法去减少求解空间。如果这种方法能够让人快速完成游戏，反之，当然也可以让计算机更快求解。

背后的数学规律

如果知道图论的基本属性的度的一些知识跟规律，想这个游戏的解法，并不用花去很多时间，由于这个游戏的图都是连通图，所以以下讨论图都是基于这个前提的。度的简单定义：

1. 每个点所连接的边的数目；（图2的起点S的度为3）
2. 出度：以该点作为起点的边的数目；（图2的起点的蓝色边成为出度，因为那条边从起点“出去”了）
3. 入度：以该点作为终点的边数目；

当游戏中从一个点到另一个点的时候，有两个规律：

1. 一个点（起始点）的出度少了1，另一个点（终点）的入度少了1。
2. 每次划过一个点时，这个点如果是中途的点，它的入度跟出度各自少了1，也即是该点的度少了2。

由这样两条简单的规律就可以推断出真正的解法：

1. 由于每次画一笔（连接2个点），就会使得整个图的度总和少了2，所以这个图能被一笔画的必要条件是整个图的度总和一定是偶数。
2. 如果一个点的度是奇数的，那它必然是起点或者终点。
3. 因此，这个图要么都是偶数度的点，要么有且仅有2个奇数度的节点。
4. 如果图中的点的度都是偶数，那么起点跟终点是同一点。只要存在解，图中任何点都可以当做是起点终点。

由于这个游戏是一定有解的，再根据这几条简单规律，可以总结出一个很简单的玩法：

数一下图中的点，有哪些点是奇数条边连着的，那么不用想其他的，直接把它当起点去划，很快就能通关了。

我把这个方法告知我小学3年级的表妹，她轻松过了N关。

第二关卡

当然游戏关卡会慢慢变难，也就是问题变种。到了第二大关时，问题变了一下，图中出现了红色的线条，这条线需要被访问两次。

图3

如果能理解第一关的规律，这关的规律就不难想到了，只要数每个点的度时，把红色的边当成是2条边来算即可。所以问题再演变成XX颜色的边需要访问N次，那就把那种边当做N度来算即可。

其实可以从中体会到一点，关卡游戏的设计，往往都是上一关的游戏规则的一个变种。

第三关卡

再变种一下，就是游戏中出现的某些边是指定方向了，也就是你必须按照该方向来划过这条边，这个变种就约束了我们可能要固定某个起点或者终点了。玩法约束了一下：

1. 规则依旧同上述一样，但是在选择起点时需要根据图形方向选定一个起点（第一关跟第二关的起点跟终点倒过来是可以的，第三关不行了）
2. 在中间搜索路径时，有方向的约束

图4

由于还没有爆关，先把基本的规则介绍记录一下。下一关卡待续。。。