初探 ES6:构建和解决数织
刚才走到了第几关?想看答案,点击下方的刷新图标就可以了。
解法
和数独一样,数织也是一个 NP 完全问题。这里介绍一种简单暴力但是不完全的解法,意为不保证能找出某个数织的唯一解。它就是穷举法。
我们来单看某一行:假设这行有 7 格宽,提示数字为 2 和 3。穷举出所有情况:
2 3 |█|█|X|█|█|█|X|
2 3 |█|█|X|X|█|█|█|
2 3 |X|█|█|X|█|█|█|
可以发现无论哪种情况下,第 2、5、6 位都是被填满的,那么可以标记为填满。接着去处理其他的行列。假如下一次处理到这行的时候,第一位已被标记为空,即
2 3 |X|█|?|?|█|█|?|
那么上述的前两种情况都与其矛盾,所以这行的最终结果就是第三种情况。
有些数织(左)本身有不止一个解。还有的(右)的确有唯一解,但是也不能被这种方法解出,这种情况就需要进行递归猜测了。
你可以点击用来表示不确定的浅灰色方块,以将它标记为填充,接着程序会按照当前的状态试着再解一次。
(下一页:构造)
啊好长好长好长
二维码的演示效果超级炫酷!对,我就是那种看不懂代码只能看看效果的 (*@ο@*)
肖大神怎么可能看不懂代码😁