华容道问题求解第一部分_思路即方案设计

一、前言

华容道是一种传统的益智游戏，通常由一个长方形木板和若干个方块组成。其中包括一个或多个不同颜色的方块（也称为车块）和其他大小相同的方块（也称为障碍块）。游戏的目标是将车块从木板的一个端点移动到另一个端点，通过调整其他方块的位置来清除道路并组成一个通路。华容道可以锻炼思考和推理能力，提高空间想象和逻辑能力。这个游戏在中国有着很长的历史，并在全世界广受欢迎。（以上内容来自INSCODE AI 创作助手）

而笔者接触这问题要追溯到敝人的小学时期了，依稀记得在上学的路上，有成人玩这个游戏，感到非常有趣。知道最少80多步可以将被困的曹操从华容道放走。在十几年前，笔者在某公司谋职时，曾经用C#写了一个简版的求解。该解法目的是在于锻炼笔者的思维，以及软件编程方面的技巧。当时的解法是1000多步，我知道这个肯定是软件有疏漏，没有找到最佳方法，或者是没有穷举到所有方法所致，因此想重写这个问题的求解。
在重写的过程中，主要解决以下两个问题：
第一：步数的确定
在上一个版本中，对步数的计算非常模糊，和人移动棋子的步骤的步数较大差异。例如，下图：

从A将小卒（方块）移到B处， 按照人的步骤应该是一步，但是软件中算成两步；

第二：没有穷举出所有方法
这个大约是源于算法中的疏漏，需要在重构具体解法。
第三：寻找最少步数
这个算法其实不难，就是限定步数，就是如果步数超过了限定值，就放弃，这样就可以找到最少步数。缺点就是在最坏的情况下可能要穷举所有步骤，可以采用经验值法，例如上限设为90步。这个涉嫌作弊了，也可以从 1 逐渐增大上限值，这样就会很慢。当然怎么找到一个快速的路径是一个问题，一个优化的问题。

---

二、功能描述

软件名称：华容道
功能：1：提供一个人机交互界面，可以通过鼠标进行游戏；
2：自动求解
自动求解并找出最优解，即公认的81步走法；
3：将提供两个版本，电脑版和手机版。其中电脑版指Windows版本，将使用C#；手机版使用Flutter或者Unity；
实现方法：
DFS
寻求到一个解后，再去寻找另一个解法。这就是DFS，深度优先算法。

---

三、概要设计

3.1 总体功能描述

基础功能分成两个方面进行，数据层和呈现层，还有两者的适配功能。

3.1.1数据层

1、静态数据1.1 棋盘布局1.2 棋子描述棋子的静态结构包含以下属性：name:名称size： 长宽，整数icon：图标position: 头部位置，定义为左上角位置。2、动态数据2.1 布局记录2.2 步骤记录
3、 逻辑和方法3.1 遍历移动采用两种方法移动：A 遍历移动， B 经验移动。首先采用遍历移动，这种方法将探索理论上所有的移动方法。为了描述清晰，进行一个简单的定义方向定义： 方向1：向上方向2：向右方向3：向下方向4：向左上下左右均指屏幕的上下左右步长定义：移动一个基本小方块为一个步长，根据题目限定，最多一次可以移动两个步长；步数：移动一次即为一步，注意一次可能移动一个步长，也可能移动两个步长。3.2 经验移动引入移动人工经验移动方法，这样可以快速移动，需要引入类似于公式或者围棋中定式的概念。这个方法需要单独研究。3.3 移动方法3.3.1 DFS 方法确定可以移动的方块，只有空白区域周边的方块才有可能移动；因此首先定位空白区域，然后查找周边方块，放入备选移动方块集合中；然后从该集合中按照一定顺序移动方块，移动方块后，空白区域发生变化，因此需要重复上面的步骤。如下图所示

3.3.1.1 棋子移动方法
变棋子的坐标即可。这样每个旗子的移动方法是统一的，
一次成功的改动，记作一步。
3.3.1.2 空余位置计算
两种方法：A） 根据棋子的坐标及其尺寸属性可以查找空余位置；
B) 每移动一个棋子，计算空余位置
3.3.1.3 可移动棋子查找
棋子移动之后，空余位置随即发生变化，为了进行下一步的移动，需要找到可移动的棋子。当然当期移动的棋子肯定是一个，但是不能进行反向移动，否则陷入死循环了。

3.1.2呈现层

呈现层就是将数据层的数据以合适的方式展现出来，给软件使用者一个展示，属于UI部分的设计。该部分将遵循一般的UI设计原则，同时将提供如下功能
1、布局设计
自动布局：提供游戏的经典布局样式
用户布局：用户自己可以定义布局
2、交互功能：提供一个可以使用键盘或者鼠标的游戏操作界面；
3、记录功能：记录用户操作过程并可以重现

3.1.3 适配器

适配器用于数据层和呈现层之间，负责将数据层中的位置关系等视觉信息提取出来提交给呈现层；也负责将呈现层的位置操作等指令转换成数据层的相应信息。下面的用词视角为界面视角即呈现层视角。
1、数据获取
应该是一组函数或者接口，从数据层获取呈现层需要的数据，这些数据应该是直接可用的数据；
2、发送数据
同样也是一组函数或者接口，将呈现层的操作转化为数据层可理解的数据，发送给数据层。

---