【修桥游戏】求算法帝给个思路

Moneky

昨天一个小朋友找了一个修桥的智力题求解，之前在电脑上玩过该游戏，但玩的难度不大。下面这个人力完成实在是比较困难。由于喜欢写写程序，于是想到是否能够用电脑求解，苦思良久，没有头绪。各位有什么好的想法来讨论一下吧。


下图是在看了部分答案后人工作出的结果

补充：没两个小岛之间最多两座桥。


该贴已经同步到 Moneky的微博

清风_ll

感觉和扫雷有点类似啊

Zamyi

答案不是唯一的。这个题目答案应该唯一才比较好吧？

Moneky

Zamyi 发表于 2013-12-16 16:48
答案不是唯一的。这个题目答案应该唯一才比较好吧？

其实只要用程序能够找到合理的答案就满足了

Moneky

清风_ll 发表于 2013-12-16 16:44
感觉和扫雷有点类似啊

关键是桥与桥不能相交，而且相邻两个岛的桥不超过两座，这个比较麻烦。

lee1892

1、岛的地理位置是否为题目给定？
2、岛的地理位置信息是否可以如所贴图片能用方格子完整反映？
3、岛的连接是否必须是横平竖直的？
4、相邻又是怎么定义的？
5、是否必然有数字1的出现？

最好能发个原游戏的截图～

暂时想到几个疑问～

Moneky

lee1892 发表于 2013-12-16 18:30
1、岛的地理位置是否为题目给定？
2、岛的地理位置信息是否可以如所贴图片能用方格子完整反映？
3、岛的连 ...

下面就是原题：

1、岛的地理位置是否为题目给定？     【就这道题目确实是这样】 2、岛的地理位置信息是否可以如所贴图片能用方格子完整反映？  【应该可以用平面直角坐标系中的点来确定】 3、岛的连接是否必须是横平竖直的？【是】 4、相邻又是怎么定义的？【同行同列中的A、B两岛之间没有第三岛】 5、是否必然有数字1的出现？【不确定】 RedHat系统中一个游戏就是这个，曾经玩过，不过当时玩的是低难度的，那个游戏可以自己求解，是根据题目生成的过程逆向而直接显示的答案，还是通过题目智能求解的答案就不得而知了。

lee1892

Moneky 发表于 2013-12-16 19:27
下面就是原题：

这样清楚多了
1、貌似行列奇偶相间，以单元格作为坐标系，则行列坐标必然同为奇数或同为偶数
2、第一感觉最合适的是神经网络算法

lee1892

平板回帖太倒霉了～编辑会出乱码！

定义几个概念：
1、角落，指只有4个方向中只有两个方向可以连接
2、边，指4个方向中有3个可以
3、中间，4个方向都能连接

显然，对于上述3种，4、6、8应该直接画双线，而3、5、7可以每个方向都先画单线，再进行下一轮检查。每次划线，应该都能产生新的唯一可确定桥或是必然存在桥，循环检查直到无法产生，开始深度优先搜索，我比较怀疑是不需要的。

比如楼主贴的图片，左边的5必然在上、右、下3个方向至少各有1个桥，画上后其右上角的3成了角落、画2个方向，以此类推，其右上连续的3都会成为新的角落。

又如右上方相邻的两个1不能相连，则右方的1只能连下方的3。

感觉倒还真不是太难，可能关键是把数据结构设计好。

Moneky

lee1892 发表于 2013-12-16 21:03
琢磨了一下，除非能设计出合适的神经网络数学模型，否则比较现实的做法还是不断的逻辑判断，类似数独、五子 ...

先前学习了一些类的知识，所以先想到创建如下的类：

目前也只是想想而已，还不能动手，因为后面的算法什么的没有头绪和思路，当然实际创建这些类也还要慢慢摸索。基本上属于处于捡到个鼠标开始想装电脑的状态。。。


这，9L发生了什么事情？