编程|妙哉！用文言文编程 竟从28万行唐诗中找出了对称矩阵( 二 )
八皇后问题 ， 简单来说是这样的：
8 x 8的国际象棋棋盘上 ， 摆放8个不同的皇后 ， 使其不能互相攻击 ， 即处在同一行、同一列、同一斜线上 ， 求解摆放方法 。
文章图片
这个问题 ， 可以用到一种名为“回溯法”的算法来求解 ， 原理如图：
文章图片
如果用回溯法来找“幻方” ， 计算机需要先随机“找出半句诗” ， 再挨个儿往后面搜索合适的诗句 。
例如 ， 计算机先从13万行唐诗中 ， 随机找出诗句“风月清江夜”：
文章图片
根据对称矩阵的原理 ， 第二句诗的开头 ， 就应该以“月”为首：
文章图片
（以月开头的诗句 ， 应该还是有不少的 ， 像月上柳梢头）
以此类推 ， 第三句诗的开头 ， 就应该以“清夜”为首：
文章图片
（以清夜开头的诗句 ， 就少了许多）
而第四句诗的开头 ， 就应该以“江山归”打头：
文章图片
（江山归开头的诗……可选范围应该更少了）
最后一句诗的开头 ， 就必须与前4句诗的结尾完全一致 ， “夜深来客”：
文章图片
难度逐渐变成地狱级……
在这几步操作中 ， 要是有任何一步无法满足条件 ， 就得全部推倒重来 。
这样的话 ， 最初的第一步 ， 就显得尤为重要：从什么类型的诗句开始遍历 ， 才能最快地找到答案？
他为此用上了启发式搜索 ， 从已知问题信息入手 ， 对这些空格进行评估 ， 找到限制条件最多、即最容易“下笔”的那个位置 ， 再从这个位置开始找诗 。
具体写成代码求解的话 ， 就是利用递归法的结构 。
同时 ， 用上剪枝法 ， 缩小剩下位置的查找范围 。
也就是说 ， 要用到约束函数 ， 在扩展节点处剪去不满足约束条件的子树；再用限界函数 ， 剪去得不到最优解的子树 。
文章图片
这样一来 ， 就能降低问题复杂度 。
然而在运行代码时 ， 作者却发现 ， 这样做效率并不高 。
这种方法 ， 虽然可以求解“N”皇后问题 ， 却不太适合求汉字矩阵 。
因为 ， 要填进格子里的 ， 可不止8个皇后 ， 每一格可以填的汉字 ， 就有5000+种选择！
文章图片
采用递归法的话 ， 计算机在填上前面的汉字时 ， 实际上就缩小了剩下汉字可以搜查的范围 。
如果没有找到最初那个合适的字 ， 往往搜到一半后 ， 能用的诗句就没了 ， 又得重新再猜 ， 效率不升反降 。
越想越烦躁 ， 这位小哥干脆一拍大腿：不如暴力搜索！
文章图片
当然 ， 也不是普通的暴力搜索 。
会有两个搜索条件：
其一 ， 以五言诗为例 ， 第五列的前4个字 ， 和第五行的前4个字 ， 内容是否完全一样？如果不一样 ， 就扔掉 。
推荐阅读
- 发动机|三缸机的“病” 为何要用四缸机来治？
- 熊孩子|熊孩子用打火机玩火烧毁私家车 监控曝光：点燃了隔音棉
- 考研|小伙考研用掉近60支笔：每天5点起、查成绩瞬间泪奔大喊
- 五菱|五菱官宣注册“GAMEBOY”商标 或率先用于新款宏光MINI EV
- 安卓|不用iPhone！苹果员工集体要用安卓手机：原因是为防公司窥探
- 丰田|丰田推出可充气的方向盘 自动变粗变细！使用场景想不到
- 五菱|凯捷“亲兄弟”！五菱佳辰官图发布 排七座家用MPV
- 微信|官方：现行“个人收款码”不停用、不关闭 新增“个人经营码”究竟是什么？
- 微信|小商户不用担心了！支付宝、微信：3月1日起个人收款码不停用
- 董明珠|董明珠呼吁消费者定期更换电器：长期使用老化空调可能带来隐患