Ruby 数独求解器解析 TRICK 2015「最通用性最小」获奖作品 eregon/entry.rb 的协程魔法【免费下载链接】rubyThe Ruby Programming Language项目地址: https://gitcode.com/GitHub_Trending/ru/ruby导读本文以 Ruby 官方仓库 sample/trick2015/eregon/remarks.markdown 为骨架完整剖析 TRICK 2015第二届 Transcendental Ruby Imbroglio Contest第四名获奖作品 eregon/entry.rb一个仅 15 行、核心求解器 302 字符、却能输出任意数独全部解甚至全部完整数独的最小通用求解器。文章将逐行讲解其用Fiber协程实现回溯、用字符串片段夹藏数独盘面、用 9 层栈帧回溯 81 层的设计并结合仓库中cont.c、string.c、ruby.c等源码佐证其运行机制。读完你可以掌握如何用协程优雅地实现回溯搜索、如何用String#b与Fiber.yield的返回值做极简编程以及如何在无break、无递归的前提下完成深度搜索。一、参赛背景TRICK 2015 与Least general solversample/trick2015/README.md记载了这一目录的来历它收录了第二届 Transcendental Ruby Imbroglio ContestTRICK 2015为 rubyKaigi 举办的获奖作品并特别声明这些是反面教材切勿当作示例代码使用。其中kinaba/entry.rbBest piphilology金奖ksk_1/entry.rbMost unreadable ALU银奖monae/entry.rbDoubling amphisbaena award铜奖eregon/entry.rbLeast general solver第四名ksk_2/entry.rbMost general solver第五名本文主角eregon/entry.rb的作者是 Benoit Daloze用户名 eregon见 authors.markdown他给出的程序描述是该程序展示任意数独题目的全部解并获评最小通用求解器——因为它用极小的代码量覆盖了任意盘面求解这一通用问题。事实边界说明以上奖项与作者信息均出自仓库内 sample/trick2015/README.md 与 authors.markdown最少通用求解器属于赛会命名本文不做任何性能或优劣推断。二、运行与验证一条命令跑通全部解2.1 运行方式按 remarks.markdown 的说明直接运行、不带任何参数ruby sample/trick2015/eregon/entry.rb运行后程序会求解内嵌数独 → 打印全部解每个解是一组 9 行数字解之间以空行分隔→ 静默结束。若把盘面中所有数字替换为0或_程序将尝试打印每一个可能的完整数独——remarks 中明确提醒我们对这种行为不做任何时间上的保证因为完整数独解的空间极其庞大。2.2 作者验证过的实现与平台remarks.markdown 列出了作者当时确认可运行的环境Linuxruby 2.3.0devtrunk 52394、ruby 2.2.2p95、ruby 2.0.0p647Darwinruby 2.0.0p247、jruby 9.0.3.0、rubinius 2.2.6.n74也就是说该程序在 MRI、JRuby、Rubinius 三类实现上均有通过记录。需要说明的是这些是 2015 年的验证环境在当前仓库2.x/3.x 时代源码上运行时核心依赖的Fiber、String#b、$*等机制依然存在详见第四节源码佐证但 jruby/rubinius 的兼容性以各自当前版本为准。2.3 参数限制remarks 的 Limitation 一节特意注明The program does not want anyargumentwith you and will quit quietly if you try some.即程序不接受任何命令行参数。原因直白$*即ARGV命令行参数数组被程序直接当作数独盘面使用——s$*。传入参数会破坏盘面布局因此作者让程序安静地退出。从仓库入口 ruby.c 可以看到$*对应的正是rb_argvRuby 命令行的ARGV这也印证了该程序对参数零容忍的设计由来。三、程序形态15 行、302 字符求解器、42 个单词remarks.markdown 给出了程序规模与两处关键好数字$ wc entry.rb 15 42 60015 行源码本仓库中实际为 16 行、601 字节为提交时的细微差异42 个单词面向作者的某种计数600 字节左右——而真正求解器的核心仅 302 字符前提数独盘面存放在变量s中编码为行的数组每行是数字数组。作者还列出了若干设计上的趣味点实现回溯时状态保存极其优雅借助 Fiber 的挂起/恢复整个程序栈帧深度不超过 9 层却可以回溯高达81 层9×9 盘面程序主循环是格子之间的舞蹈一头是解另一头是程序结束只使用无限循环全程没有break求解器的创建与盘面数据交错生成代码与数据穿插拼装程序容易去混淆但搞懂原理更难最后一行藏着一个笑脸。第四点尤其反直觉没有break的无限循环如何终止答案就在loop{cl[ic.resume ? 1:-1]}这一行——它用Fiber#resume的返回值真/假来决定下一轮走向哪个协程从而在数据层面结束循环。这与常规的break/条件跳转思路完全不同是理解全文的钥匙。四、源码级拆解逐行还原协程数独entry.rb的完整内容如下本仓库内文件共 16 行class String;def[]*a;$*a;b;end;end; _0;zCFiber;s$*;a*0..8;lC.new{e xit},*a.product(a).select{|r,c|s[r][c ]0}.[1,9,_, _,_,8, _,_,5]map{|r, c|C.ne[_,_,2, _,5,_, _,8,9]w{os[r ][c];l[8,_,6, 7,4,_, _,_,_]oop{(1. .9).map{|n|C.yield(s[r][c]n)if a.non e?{|k|[_,_,_, _,_,4, _,9,2]s[r][k] n||s[_,2,3, _,7,_, 8,1,_][k][c] n||s[[5,6,_, 8,_,_, _,_,_]r-r%3k %3][c-c%3k/3]n}};s[r][c]o;C.yield }}},C.[_,_,_, _,2,7, 9,_,3]new{loo p{puts[9,3,_, _,8,_, 1,_,_] s.map{ |r|r*[2,_,_, 5,_,_, _,4,8] } ;C.yield}};cl[i1];loop{cl[ic.res ume ? 1:-1]};eval z.tr ?\n,4.1 第一层混淆字符串夹藏盘面全程序的核心技巧在最后一行eval z.tr ?\n,。它把变量z中的换行全部去掉后求值。而z是由10 段字符串字面量与9×3 个盘面数字字面量交替拼接而成z CFiber;s$*;a*0..8;lC.new{e xit},*a.product(a).select{|r,c|s[r][c ]0}. [1,9,_, _,_,8, _,_,5] map{|r, c|C.ne [_,_,2, _,5,_, _,8,9] w{os[r ][c];l [8,_,6, 7,4,_, _,_,_] oop{(1. .9).map{|n|C.yield(s[r][c]n)if a.non e?{|k| [_,_,_, _,_,4, _,9,2] s[r][k] n||s [_,2,3, _,7,_, 8,1,_] [k][c] n||s[ [5,6,_, 8,_,_, _,_,_] r-r%3k %3][c-c%3k/3]n}};s[r][c]o;C.yield }}},C. [_,_,_, _,2,7, 9,_,3] new{loo p{puts [9,3,_, _,8,_, 1,_,_] s.map{ |r|r* [2,_,_, 5,_,_, _,4,8] } ;C.yield}};cl[i1];loop{cl[ic.res ume ? 1:-1]}这里的[1,9,_, _,_,8, _,_,5]之所以能作为的右操作数与字符串拼接是因为第一行定义了一个魔法方法class String; def [] *a; $* a; b; end; end拆开看String#[]被重定义为把参数追加进$*盘面数组然后返回b——而b是self.b省略接收者的方法调用即调用String#b返回当前字符串的 ASCII-8BIT 副本。所以str [1,9,_]等价于str str.b一个与原字符串内容相同的 String 对象从而把数字数组伪装成字符串参与拼接a是[]的参数*a收集所有参数即 9 个数字被$* a整体压入盘面——9 个数字作为一个子数组一行存入_是普通局部变量初始化为0第二行_0因此[1,9,_]即[1,9,0]。全盘用_0表示空位——这也解释了空盘面全部填0或_的用法来源。结果z求值后得到一段连续、无换行、含盘面数据的 Ruby 代码字符串这段代码整体仍是一个表达式{/}配平、可独立求值其中盘面以[数字,数字,...]字面量的形式被字符串片段包裹既做数据又做代码。这正是 remarks 所说的求解器的创建与盘面交错interleaves the creation of the solver and the puzzle。4.2 核心求解器302 字符的协程回溯去掉盘面数据后求解器本体浓缩为以下逻辑为可读性已还原缩进与eval后实际执行的代码等价C Fiber s $* # 盘面9 个元素每个是一行9 个数字 a *0..8 # a [0,1,...,8]用作行/列/块索引 # 求解器链l 是一组 Fiber 的数组 l [C.new { exit }, # l[0]哨兵——从 Fiber 内 exit 结束程序 *a.product(a).select { |r, c| s[r][c] 0 }.map { |r, c| C.new { o s[r][c] # 保存原值应为 0 loop { (1..9).map { |n| C.yield(s[r][c] n) if a.none? { |k| s[r][k] n || # 同行冲突 s[k][c] n || # 同列冲突 s[r - r % 3 k % 3][c - c % 3 k / 3] n # 同 3×3 宫冲突 } } s[r][c] o # 9 个候选全部试完 → 复位 C.yield # 向上一个格子让路 } } }, C.new { # 最后一个打印协程 loop { puts s.map { |r| r * } # 打印当前盘面 空行 C.yield } } ]候选检查对空位(r,c)逐一尝试n 1..9仅当n未出现在第r行、第c列以及所在的 3×3 宫宫的行偏移r-r%3、列偏移c-c%3时才yield(s[r][c]n)——把填入 n 的盘面让渡给下游。a.none?遍历全部 9 个k三条件之一成立即拒绝该候选。主循环程序最精妙的一行c l[i 1] loop { c l[i c.resume ? 1 : -1] }Fiber#resume的返回值来自被恢复协程中最后一次C.yield的实参无参C.yield则返回nil为假求解器协程yield回传的是s[r][c] n赋值表达式返回被赋的值即1..9真值→ 主循环i 1前进到下一格当 9 个候选全部试完执行无参C.yield→ 返回nil假→i - 1后退到上一格回溯打印协程无参yield→ 返回nil→ 后退当所有空位都回溯到起点、i回到 0 时恢复l[0]这个哨兵协程它在Fiber内调用exit—— 程序结束。于是没有break的无限循环得以终止loop永不跳出但exit直接从进程层面结束程序。这也回应了 remarks 中的设计说明——return-ing from a Fiber is not allowedFiber 内不允许return穿过协程边界所以程序必须exit。栈帧深度 ≤ 9 的秘密所有空位的搜索逻辑都被封装在各自的Fiber对象里主程序从不递归调用求解器而是在 81 个协程之间水平切换每次resume的调用栈只有主循环 → 被恢复 Fiber 的块两层整个程序最深不超过 9 层栈帧而回溯深度却可达 81 层——这正是用协程保存回溯状态的优雅之处也是 remarks 反复强调的设计亮点。4.3 打印格式每个解的输出由打印协程完成puts s.map { |r| r * } r * 把一行数字数组以空格连接成字符串 给结果数组追加一个空串使puts在每行末尾额外输出一个空行从而在解与解之间形成空行分隔。五、作者自述的技巧清单与源码佐证remarks.markdown 列出了三项为缩短代码而用的技巧每一条都能在本仓库源码中找到依据定义的方法可以既无括号也无空格def[]*a定义了String#[]其参数收集语法*a允许省略括号与空格这是 Ruby 方法定义语法允许的极简形态对应实现见 string.c 中rb_str_b与rb_define_method(rb_cString, b, rb_str_b, 0)后者表明String#b是 0 参数方法故b可省略接收者与括号作为self的最短别名。利用无参Fiber.yield的返回值C.yield不带参数时向resume方返回nil假值主循环据此判定该格已穷尽、应回溯而带参yield(s[r][c]n)返回真值驱动前进。对应机制见 cont.c 的fiber_switch与 cont.c 的rb_fiber_yield——参数经由argc/argv传给调用方无参即得到nil。String#b作为极短的selfb是self.b返回字符串自身的 ASCII-8BIT 副本实现见 string.c 的rb_str_b它复制接收者字符串内容与字节用它当[]的返回值让代码 [盘面数字]拼接成立——字符串片段把数字数组吸收成连续代码。另外 remarks 补充了一处原版备注In the original code, the last cell was:C.new{loop{yield s; C.yield}}, implementing some sort of forwarding coroutine.即初版最后一个协程是个转发协程forwarding coroutineyield s把盘面转发给上层后再让渡。提交版把它改成了直接打印逻辑更直白。设计缺陷的坦诚自省remarks 的 Design issues 部分还记录了两个作者认为的槽点Fiber 内不允许return程序不得不以exit收场笛卡尔积运算符仍然太长理想中a*a就能表达a.product(a)但 Ruby 没有为Array#product提供运算符写法。这两点既是参赛吐槽也间接展示了 Ruby 语言边界的真实面貌。六、灵感来源与延伸阅读remarks 提到本作的灵感来自两处一份报纸上多解的数独——促使作者思考输出全部解而非单一解论文《Revisiting Coroutines》——协程视角的回溯程序设计正是本作把每个格子建模为独立协程的理论源头。想在本仓库内继续深入推荐按此路线阅读获奖目录总览sample/trick2015/README.md并置的ksk_2是最通用求解器可与本文对比同一问题的两种极端解法作者信息sample/trick2015/eregon/authors.markdownFiber底层实现cont.cfiber_switch的上下文切换、cont.crb_fiber_resume/rb_fiber_yieldString#b实现string.c$*/ARGV的来源ruby.crb_argv。注TRICK 官方说明与其余届获奖作品不在本仓库内本文仅以仓库收录内容为准不提供外部链接。七、总结eregon/entry.rb用 600 字节演示了三个反直觉的 Ruby 事实协程即状态81 个Fiber各守一格回溯深度 81 层而栈帧不超过 9 层Fiber#resume的返回值真前进、假回溯充当了隐式的指针移动取代了传统的递归与break代码即数据、数据即代码通过重定义String#[]并借助String#b把 9 行盘面数字织进代码字符串再eval执行——混淆的核心不是加密而是把数据结构伪装成语法语言边界的诚实呈现Fiber内不能return、product没有运算符写法、程序只能exit收尾——这些槽点恰恰是理解 Ruby 协程语义的最佳注脚。把它与同目录 ksk_2/entry.rb 的最通用求解器对照阅读可以直观看到同一次混淆大赛里通用与最小两个方向可以演绎出截然不同的代码哲学。【免费下载链接】rubyThe Ruby Programming Language项目地址: https://gitcode.com/GitHub_Trending/ru/ruby创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考