标准Hashi搭桥谜题既要求每座岛的桥数等于提示数字,也要求所有岛组成一个连通网络。只满足数字并不足以完成。
先计算容量,再增加桥梁
桥沿横向或纵向通往可直接相连的邻岛,不能交叉,同一对岛之间最多两座桥。假设一座岛还差三座桥,只剩两个可连接方向,其中一个方向最多再接一座,那么另一个方向必须接两座,第一个方向必须接一座。新桥堵住路线或邻岛桥数已满时,需要重新计算剩余容量。
操作步骤
- 从每座岛的提示中减去已有桥数,并列出剩余合法方向。
- 只有数字或连通要求能够确定时才补桥,同时检查桥的两端。
- 封闭一个局部群组前,确认它仍能至少通过一条连接到达其他岛。
两个数字为1的岛,可以直接连在一起吗?
如果这样会形成已经封闭的孤立岛对,而其他地方还有岛,就不可以。两个岛各自的桥数虽然正确,却违反了全图连通规则。既要看局部总数,也要看整体连通性;一个看起来完成的角落,不一定能成为最终解的一部分。