Kakuro:填字游戏遇上组合数学
你一定见过填字游戏:一个方格,空白处填字母,横竖都要拼成单词。Kakuro 是它的数字版本——格子里填 1 到 9 的数字,横向和纵向的每段连续格子(称为一个 block)都要满足指定的求和约束,并且同一个 block 内的数字不能重复。规则就这三条: 每个白格填 1-9 中的一个数字 同一 block 内数字不重复 每个 block 的数字之和等于线索给出的目标值下面这个小谜题展示了这些要素:黑格上的斜线数字就是线索:斜线右下方是横向线索,左下方是纵向线索。手推一遍用一个 3 行 × 2 列白格的教学例题来说明推导过程: col1 col2row2: ? ? ← H0 横向线索 su...
五格骨牌的三染色问题:2339 种铺法里有多少种能上色?
引言
用 12 块五格骨牌平铺 6×10 矩形共有 2339 种方法——但如果我要求相邻骨牌颜色不同,连角都不能碰,还剩几种?
这是《The Art of Computer Programming》Volume 4B 中的习题 7.2.2.1-277,难度评级 [25](TAOCP 的评级范围 0–50,数字越大越难)。答案是:94 种,仅占约 4%。
用 Dancing Links 解决五格骨牌平铺问题
引言Donald Knuth 在《The Art of Computer Programming》Volume 4B 中提出了 Dancing Links (DLX) 算法——一种优雅地解决精确覆盖问题的回溯算法。本文将探讨习题 7.2.2.1-31 中提到的经典应用:五格骨牌平铺问题。什么是五格骨牌?五格骨牌(Pentominoes)是由 5 个单位正方形连接而成的多格骨牌。不考虑旋转和翻转,共有 12 种 不同的五格骨牌,通常用字母 F, I, L, P, N, T, U, V, W, X, Y, Z 来命名:问题定义经典问题:用全部 12 种五格骨牌各一片,能否精确平铺一个 6×10 的矩形区域?这个问题可以推广到: ...
谁养斑马?——用算法终结逻辑推理题
我花了一个小时没解出来,然后写了 30 行代码,算法用不到 1 毫秒解完了。
这道题就是著名的”斑马谜题”(又叫爱因斯坦谜题):五个人住一排房子,每人国籍不同、职业不同、宠物不同、饮料不同、房子颜色不同,给你一堆线索,问——谁养斑马?
1962 年发表在 Life International 杂志上,据说只有 2% 的人能解出来。
这篇文章介绍一种完全不同的做法:把谜题翻译成 XCC 问题,让舞蹈链算法自动求解。不用画表格,不用推理,只需要把”什么是合法答案”描述清楚。
然后我们反过来——让算法自动出一道新的逻辑推理题。
博客搬家:从 GitHub Pages 到自定义域名
最近做了一件拖了很久的事情——给博客换了个域名。新地址是 blog.morefreeze.top,旧的 morefreeze.github.io 会自动跳转过来,不影响之前收藏的链接。