初探 ES6:构建和解决数织

刚才走到了第几关?想看答案,点击下方的刷新图标就可以了。

解法

和数独一样,数织也是一个 NP 完全问题。这里介绍一种简单暴力但是不完全的解法,意为不保证能找出某个数织的唯一解。它就是穷举法。

我们来单看某一行:假设这行有 7 格宽,提示数字为 2 和 3。穷举出所有情况:
2 3 |█|█|X|█|█|█|X|
2 3 |█|█|X|X|█|█|█|
2 3 |X|█|█|X|█|█|█|
可以发现无论哪种情况下,第 2、5、6 位都是被填满的,那么可以标记为填满。接着去处理其他的行列。假如下一次处理到这行的时候,第一位已被标记为空,即
2 3 |X|█|?|?|█|█|?|
那么上述的前两种情况都与其矛盾,所以这行的最终结果就是第三种情况。

有些数织(左)本身有不止一个解。还有的(右)的确有唯一解,但是也不能被这种方法解出,这种情况就需要进行递归猜测了。

你可以点击用来表示不确定的浅灰色方块,以将它标记为填充,接着程序会按照当前的状态试着再解一次。

(下一页:构造)

3 条评论

  1. 博主你来打我呀说道:

    啊好长好长好长

  2. Art9说道:

    二维码的演示效果超级炫酷!对,我就是那种看不懂代码只能看看效果的 (*@ο@*)

发表评论

电子邮件地址不会被公开。 必填项已用*标注