はじめに
3年前、ぼくのかんがえたさいきょうのナンプレの解き方をPythonに実装してみたという記事を書きました。ナンプレを毎日解いていたら飽きてきたので、自分の解き方をプログラムに残しておこうと思って書いたものです。
先日ふと読み返す機会があって、当時の記録を見返してみると、一番最初の力技版は「世界一難しい数独」を解くのに464秒、工夫を重ねた最終版でも1.969秒かかっていました。それだけ時間のかかっていたコードを、今AIと対話しながらどこまで縮められるのか、単純に気になってしまったんですよね。
というわけで今回は、Claude Codeと一緒にこのコードを読み直して、実際にどこまで速くできるかを試してみた記録です。
まず現状を診断してもらった
自分の勘だけで直すよりも、まず客観的に見てもらった方が早いだろうと思い、Claude Codeにコードのレビューを頼みました。返ってきた診断は、正直予想と違いました。
自分はてっきり「アルゴリズムそのものが非効率」なのが原因だと思っていたんですが、実際の一番の犯人はdeepcopyの乱用だったんです。当時のコードは、再帰1回ごとに盤面全体・候補の集合全体をdeepcopyでまるごと複製していました。
solve_number_place(
deepcopy(number_list),
deepcopy(new_column_list),
deepcopy(new_row_list),
deepcopy(new_area_list),
)
当時の最終版は「世界一難しい数独」を解くのに再帰1993回で1.969秒かかっていたので、単純計算で1回あたり約1msです。9×9のマス目相手にこれはさすがに遅すぎて、複製のコストが計算量そのものより支配的になっている、という指摘でした。言われてみれば当たり前なんですが、3年前の自分は探索の枝刈りにばかり気を取られていて、ここに全く目が向いていませんでした。
進め方を決める
いきなり全部書き直すと、どこがどう効いたのか分からなくなりそうだったので、段階を分けて、それぞれをPull Requestにしてから進めることにしました。
- 可読性だけを直すPR（挙動は一切変えない）
-
deepcopyをやめてビットマスク管理 + in-place backtrackに書き換えるPR - naked pair・pointing pairという手筋を追加するPR
それぞれ、変更前後で「世界一難しい数独」を解かせて、盤面と解の数が完全に一致することを確認してからマージする、というルールにしました。速くなったつもりで答えが間違っていたら意味がないので、ここは譲れないところです。
Phase 1 可読性だけを直す
最初のPRでは、性能には一切手をつけず、1つのファイルに全部入っていたmain.pyを役割ごとに分けました。
-
board.py盤面の表現と候補の計算 -
solver.py探索アルゴリズム -
reporting.py統計情報の出力
possibility_listのような、何を表しているのか名前だけでは分からない変数も、cell_candidatesのように意味の分かる名前に直しています。ここは地味な作業ですが、この後の変更がどこに効いているのかを追いやすくするための下準備でした。
Phase 2 deepcopyをやめて、ビットマスク管理にする
ここが今回の一番の本丸です。やったことは大きく2つです。
1つ目は、候補の管理をset()からビットマスク（整数）に変えたことです。1〜9の候補を9bitの整数で表現して、行・列・エリアの制約は単純なビット演算（AND/OR）で計算できるようにしました。Pythonのsetオブジェクトを毎回作るより、整数演算の方が圧倒的に軽いです。
2つ目が本題で、deepcopyをやめて、盤面をin-placeで書き換えるようにしました。仮に数字を置いてみて、ダメだったら戻す。ただそれだけです。
def assign(self, row, col, value):
"""(row, col) に value を置く"""
self.cells[row * BOARD_SIZE + col] = value
self._clear_candidate(row, col, value)
def unassign(self, row, col, value):
"""assign(row, col, value) を取り消す"""
self.cells[row * BOARD_SIZE + col] = 0
self._restore_candidate(row, col, value)
盤面全体をコピーする代わりに、「どこを変えたか」だけを覚えておいて、ダメだったらその変更だけを打ち消す。バックトラックというアルゴリズム自体は3年前から変わっていないんですが、実装の仕方だけでここまで変わるのかと自分でも驚きました。
あわせて、naked single・hidden single（候補が1つしかないマス）が見つからなくなるまで確定処理を繰り返してから分岐するようにしました。さらに「あるマスの候補が0個」だけでなく、「行・列・エリアで、まだ置いていない数字なのに置ける場所が1つもない」ケースも矛盾として早めに検出するようにしています。これで無駄な探索を早い段階で切り上げられます。
結果はこちらです（「世界一難しい数独」、手元のMacで計測）。
| count（再帰・分岐の回数） | no_cnt（矛盾で弾いた回数） | 実行時間 | |
|---|---|---|---|
| Phase 1（可読性のみ） | 1993 | 211 | 1.110s |
| Phase 2（ビットマスク + in-place） | 321 | 160 | 0.099s |
10倍以上速くなりました。ただしcountの意味自体も変わっていて、Phase 1は「確定処理1バッチごとに再帰した回数」、Phase 2は「実際に分岐した回数」なので、単純に数字だけを比べるのはフェアではありません。それでも実行時間で10倍以上の差が出ているので、deepcopyが犯人だったという診断は当たっていたと言えそうです。
Phase 3 naked pair・pointing pairを足す
Phase 2で十分満足していたんですが、ここで終わるのも物足りなかったので、もう少しだけ人間っぽい解き方のテクニックを足してみることにしました。
- naked pair 同じユニット内に、候補が全く同じ2つの数字だけの2マスがあれば、そのユニットの他のマスからその2つの数字を除外できる
- pointing pair エリア内で、ある数字の候補が1つの行（または列）に収まっているなら、その数字をエリア外の同じ行（列）から除外できる
どちらも「確定はしないけど、候補は減らせる」タイプの手筋です。naked single・hidden singleだけでは手が止まってしまうマスでも、これで候補が減れば、また新しいsingleが生まれることがあります。分岐する前にワンクッション挟むイメージです。
| count | no_cnt | 実行時間 | |
|---|---|---|---|
| Phase 2 | 321 | 160 | 0.099s |
| Phase 3（naked pair・pointing pair追加） | 61 | 30 | 0.050s |
分岐の回数がさらに5分の1くらいまで減りました。実際にnaked pairが34回、pointing pairが95回、この問題を解く過程で発火していることも計測して確認しています。ちゃんと効いていました。
まとめ
「世界一難しい数独」を解く時間で並べると、こうなりました。
| 段階 | 実行時間 |
|---|---|
| 3年前の最終版（当時のPCで計測） | 1.969s |
| Phase 1（可読性のみ、今のMacで計測） | 1.110s |
| Phase 2（ビットマスク + in-place backtrack） | 0.099s |
| Phase 3（naked pair・pointing pair追加） | 0.050s |
Phase 1と3年前の最終版は、実は全く同じアルゴリズムです。3年分マシンが新しくなった差だけで1.969秒→1.110秒なので、環境差はこの程度でした。そこから先、Phase 1からPhase 3までは同じ手元の環境での比較なので、こちらは正真正銘22倍です。「3年前と比べて何倍速くなったか」を言いたくなるところですが、そこには環境の違いが混ざってフェアではなくなるので、胸を張って言えるのはこの22倍の方だと思っています。
最後に
自分だけで見返していたら、多分「アルゴリズムをもっと工夫しなきゃ」という方向にしか頭が向かず、deepcopyのコストには気づけなかった気がします。AIに客観的な診断をしてもらうところから始めたのが、今回一番効いたポイントでした。
3年前に書いたコードを恥ずかしがらずに晒しておくと、こうやって後から手を入れるきっかけになるんだな、というのも今回の発見です。次に読み返すのは何年後になるか分かりませんが、その時はまた別の切り口で高速化できていたらいいなと思っています。
3年前の記事はこちら
今回のソースはこちら