トウモロコシのパズルを解くのにCP-SATを使ったら、車輪の再発明をやめられた
Solving a corn puzzle with CP-SAT
3Dプリントされたトウモロコシのパズルを解くため、著者はClaudeに相談。するとClaudeは再帰的なバックトラッキングではなく、GoogleのOR-Tools CP-SATをインポートして解いてみせた。パズルはExact Cover問題の変種で、各ピースを一度ずつ配置し、各マスを一度ずつ覆うという2種類の制約だけでモデル化できる。Sudokuでも同じ手法を試し、既存のソルバーを活用する重要性を学んだ。
「この車輪はすでに発明されていた。バックトラッキングの代わりに、Claudeはこうした問題を解くために作られた産業グレードのライブラリをただインポートしただけだった。」
HNでの議論
16- emil-lp
ここでのCPはConstraint Problem、つまりCSP（Constraint Satisfaction Problem、制約充足問題）のことです。
https://en.wikipedia.org/wiki/Constraint_satisfaction_proble...
- sashank_1509
いいですか、この特定のケースでは、ピースが10個くらいのパズルなら、再帰的バックトラッカーでも同じくらい速いし、もっと重要なのは、はるかに推論しやすく実装も簡単だということです。
もしこれが千ピースのパズルだったとしても、優れたヒューリスティクスを備えた再帰的バックトラッカーならCP-SATに勝つだろうと私は賭けます。sudokuのケースでさえ、優れたヒューリスティクスを組み合わせたバックトラッキングはCP-SATに勝ちます。なぜClaudeが即座にCP-SATを使う方に飛びついたのか、よく分かりません。
- nh23423fefe
> それは私が自分で書くよりもずっと良くて、結局そこから学ぶことになった。
いずれLLMのコードをけなすことは、誰の目にも怠惰な現実逃避と映るようになるだろう。私もSATの存在は知っているが、実際に何度もやってみない限り、今抱えている問題を即座に見抜いてSATと解釈するのはかなり難しい。エージェントが「正しいもの」を提案してくれるのは明らかに優れている。そして願わくば、それが将来の私の直感を養う助けになればいい。