关于修桥（Hashi）游戏解题算法

lee1892 · 发表于 2015-8-14 14:14

本帖最后由 lee1892 于 2015-8-14 14:14 编辑

相关的游戏介绍和题目在：http://club.excelhome.net/thread-1115046-1-1.html

这里讨论一下算法。

名次定义：
1、岛：数字所在格子，为 1~8，表示可连接的桥的数量
2、桥：连接两个岛的线

游戏规则：
1、同一水平线或是同一竖直线上的相邻两岛间可以连接桥
2、两岛间最多可连接两座桥
3、桥不能与桥相交
4、所有岛所连接桥的数量必须等于该岛的数字
5、所有岛必须通过桥连通

算法：
1、对每个岛记录其所有岛连接的可能，如计某岛的桥为：上->U，下->D，左->L，右->R，后缀以 1 或 2 以表示建桥数量

如上图中第2行右侧的 4，其连接可能为：L2R1D1；L2D2；L1R1D2

2、由规则5，可以简单排除这样的可能，该可能的连线使得其连通的所有岛的数字都被用完，即这些岛都无法与其它岛连通
如上图中左上角的 2，其连接可能 R2 就不成立；又如右上角的 1，其 L1 不成立

3、对于仅有一个连接可能的岛，该可能中的桥可建立

4、某岛中，如某桥存在于所有可能中，则该桥可建立，如步骤1例中的L1D1

5、建立桥时，其所连接的岛的可能中不包含该桥的都不成立

6、建立桥时，与其交叉的所有桥都不能成立，修改这些桥所连接的岛的可能

7、建立桥时，其所连接的岛剩余可连接桥的数量为 0 或 1 时，会影响其临近岛的可能，至步骤 3

8、检查是否完成，所有岛的已连接桥的数量等于其数字，将相互已连通的岛归为一组，则应只有一组

9、如某桥的建立使得某组封闭或使得连接的两组封闭，且剩余组数大于 1，则该桥不成立，则修改其所连接的岛的可能，至步骤 3

至此，较为简单的都可以完成，不能完成的要用试算法，即对于某个可能进行试算，如能完成游戏则退出，如导致错误则该可能不成立，如仍不能完成，则继续试算（此处深度优先和广度优先均可）。

以上供讨论。

wcymiss · 发表于 2015-9-10 12:59

本帖最后由 wcymiss 于 2015-9-10 15:06 编辑

经过几天努力，终于完工，效率应该还可以吧。试了25*25的第22个，可以秒杀。{:soso_e182:}

修桥题-wcymiss.rar (25.24 KB, 下载次数: 120)

代码思路:
1、将岛屿、邻岛、经过点，都整理为一维n*n行的数据，有关方向数据的，为(n*n行4列)大小的数组
2、经过点的数组(n*n行4列)大小，每个元素是一个数组，包含m个经过点索引号
3、创建一个(n*n行4列)大小的数组，储存每个经过点四周的岛屿索引号
4、创建一个动态修桥信息表(n*n行7列)，包含每个岛屿的：
每个方向可修桥数(1至4列，数据不可超过2),可修桥的邻岛个数(5)，可修桥总数(6)，需修桥数(7)
创建一个动态的已修桥数组 (n * n行4列)
5、先行判断:
需修桥数均为1的的两个岛不能修桥 (会造成孤链)
需修桥数均为2的的两个岛最多只能修1座桥 (修2座会造成孤链)
6、判断必然的修桥情况(整理了3种)，进行修桥
需修桥数=可修桥总数，则修所有的桥
需修桥数=有可修桥的邻岛的个数*2-1，则每个邻岛至少修一座桥
需修桥数=总可修桥数-1，则，可修2座桥的邻岛至少修一座桥
修桥时，动态数组变化：
增加已修桥数
减少桥两端岛屿的可修桥明细、个数、总数，需修桥数
减少桥两端岛屿的邻岛的可修桥明细?个数?总数
修桥经过点的交叉方向的两个岛切断联系(可修桥为明细为0，个数-1，总数减少)
7、搜索一个未完成修桥的岛，进行尝试修桥
8、同第6步
9、进行总共已修桥个数与连通性判断。失败则重复7、8、9，直到成功

假如公共变量全作为过程的参数进行传递恐怕要降低一部分效率。

lee1892 · 发表于 2015-9-10 20:03

wcymiss 发表于 2015-9-10 18:20
好的，慢慢来，慢慢跟大师学算法。努力学习，努力做题。

做题最希望能得到老师的点评了。非常期待

别，我最不喜欢当老师了，说说我的看法吧，仅对你的文字描述。

先说数据结构。
1，你实际上是用二维数组干自定义数据类型的事，当然可以实现，但显然代码的可读性很差，写代码的时候也非常考验记性。
2，你没有为桥分配内存，而是用经过的格子来储存桥之间的干涉信息，以动态查找，想来在处理建桥后代码会比较繁琐。
3，可以不需要用NxN这么多元素，有多少个岛就用多少元素就行，其行列位置可以作为岛的属性，然后岛有如下属性：数字，剩余数字、四个方向的邻岛编号、四个方向的可建桥的编号、四个方向已建桥的值，所有连接可能。桥的处理，先把所有可能的桥进行编号，通过其经过的格子可以找出哪些桥是互相干涉的，桥的属性有：连接的岛的编号、与其干涉的桥的编号集合、是否水平等，桥可以设成静态的，备查用。以上这些信息的收集都是O(N)过程。

再说算法方面的
1、我在1楼里说的办法其实是个通用的逻辑归纳，你提到的几个都是特例。
a、初始可能的简单排除，应该是该可能所连的所有数字之和等于该数字时予以排除，除1-1，2=2外，还有如3-1/1/1，3-1/2，4-1/1/2，4-2/2，5-1/2/2，6-2/2/2等
b、前面提到的一个岛的全部连接可能性的收集其实是简单的组合计算，以一个4的岛其左1右3下2为例，则是由'左右右下下'中取四个的所有不重复组合，就构成左右右下，左右下下，右右下下，共三个可能，其中右下总是存在，所以右下这两个方向都至少要建一个桥。注意，这是一个通用的逻辑，而且贯穿整个解题过程，只是在初始化后，要使用剩余数字这个属性而已。上述的这个4的岛，建桥后，其剩余数字为2，可能连接则为左右，左下和右下。这和你所说的步骤6有根本的不同，更重要的是你的这个步骤6更像是一个初始化的过程，而不是解题循环办法。如果是这样的话，你的代码基本只能算暴力计算，而不是逻辑解题了。
2、1楼贴里提到的建桥后形成闭环的逻辑你没有做，实际做题时会经常用到的。
3、桥的建立导致其它桥的不能建立，进而导致某岛的连接数不够，这个逻辑我也没做，但实际做题时也会经常碰到，尤其难度高的。

逻辑解题，就是一个由简单逻辑到复杂逻辑不断循环查找的过程，一旦有变化，则再循环，只有在所有办法都用过后而没有变化才开始试错。

你的代码之所以快，就是因为用的逻辑太少了，而这个题暴力尝试是很快的，因为基本不会形成错误步骤树。

没看你代码，有说错的包涵，供参考

lee1892 · 发表于 2015-8-17 12:43

写了一个解题代码~

Moneky · 发表于 2015-8-17 13:42

本帖最后由 Moneky 于 2015-8-17 13:49 编辑

牛人不是吹的，你居然还记得。试试看看。
刚刚又去看了一下之前的帖子，居然都两年了。。。。。

lee1892 · 发表于 2015-8-25 11:17

本帖最后由 lee1892 于 2015-8-25 11:21 编辑

目测 25x25 中的 22 是用时最久的，5.x 秒

增加了每步的说明

没人写代码吗？我前面提到的算法应该不难实现的，wcy小姐呢？

cjh-01 · 发表于 2015-9-3 20:15

太难了，能把解答附件分享一下吗？

lee1892 · 发表于 2015-9-4 20:56

cjh-01 发表于 2015-9-3 20:15
太难了，能把解答附件分享一下吗？

难点可能在于数据结构的安排上，有时间我把代码整理一下，详细说说思路。

先等等Moneky和wcymiss，这俩都说过要写代码的

Moneky · 发表于 2015-9-4 21:26

lee1892 发表于 2015-9-4 20:56
难点可能在于数据结构的安排上，有时间我把代码整理一下，详细说说思路。

先等等Moneky和wcymiss，这 ...

别啊，我吹牛了，写不出来。{:soso_e143:}

wcymiss · 发表于 2015-9-6 15:03

再等等，正在写，不知道能不能写出来。

wcymiss · 发表于 2015-9-6 23:11

先上个能出结果的，代码没优化，效率先不考虑。

Test修桥.rar (20.07 KB, 下载次数: 56)

明天换种思路看看，速度能否快点。

lee1892 · 发表于 2015-9-7 08:47

wcymiss 发表于 2015-9-6 23:11
先上个能出结果的，代码没优化，效率先不考虑。

4楼那个25x25的22题，貌似死机一般......

我用自定义数据类型作的，岛、桥、解题记录，都是一维数组，有个数据初始化的过程

你的代码我没细看，但估计慢的原因还是数据结构没组织好。一开始就应该把所需要的数据全部整理好，通常会是O(N)的过程，比如一个桥和哪些桥是干涉的，一个岛的全部连接可能。如果在解题过程中再去动态查找这些信息的话，会使得复杂度大幅上升的。

		自动登录	找回密码
密码			免费注册

[讨论] 关于修桥（Hashi）游戏解题算法

评分

评分