Mint's log: YAPC::NAメモ1日目：Sudoku by Regexp（数独を正規表現で解く）2007年7月10日 YAPC::NAメモ1日目：Sudoku by Regexp（数独を正規表現で解く） 数独をPerlで解く、というネタはすっかり出尽くした感があったのだが、まだあったか、というのがこの講演の内容。純粋な正規表現だけを使って数独を解くという楽しいものなのに、半分足らずの時点で隣の部屋に移らなければいけなかったのであとでスライドを見て適当に補足した。ちなみにこのリンク先は29ページ、YAPCの講演に使われたのは64ページなので、YAPC版はもう少し詳しかったはず。 前半の内容 数独の紹介（会場の大多数は知ってたみたいだけど） 数独を解くアルゴリズムの紹介CPANにもモジュールが多数 Parrot版のsudoku.pirもある 数独を解くという問題はNP完全。正規表現もNP完全。 数独を正規表現で解こう 制約：拡張正規表現は使わない。 (? )型の正規表現は(?: )だけ使
