動的SQLによる数独の超高速解法


途絶えることを知らない「どのプログラミング言語を使うべきか」論争は、あまり生産的ではないように思う。少なくとも現時点では「至高の言語」なんてものはなくて、問題によって言語を使い分けるのが最良の戦略なのではないだろうか。(チームワークにおいて言語を統一しなければならないような状況では、「そういう状況」のための最適な言語を探せばいい。その際の決定が、普遍的なものであるとは限らない。)

Doukaku?なんかを見ても、「生産性が高い」というふれこみで人気のある言語でも、問題によってはかなり悲惨な状況になることがわかる。

さて、ここに「数独」という問題がある。数独を解くルーチンsuudoku(int **p)を標準ライブラリに持っているような高級言語を残念ながら私は知らない。だから、コンピュータで数独を解きたいときは、ちょっとしたプログラムを書かなければならない。

Ai Escargot

取り得る戦略を次のように分類してみる。

  1. 数独を解くルーチン(知らない)
  2. 制約条件を記述
  3. 制約条件と解決のための具体的な手続きを記述

よくある言語論争は、「C, C++, Java, C#, Perl, Python, Rubyのどれがいい?」みたいな感じだけれど、これらの言語だと、ここに挙げた戦略の3番目しか採れない。

もうちょっと別の方法があるということを見せたいと思って、「SQLで解く」という方法を実装した。これは上に挙げた戦略では2番目に近い。

じゃあ、「数独のような問題にはSQLが最適なのか」といえば、そう単純でもなくて、ここで実装した方法は、JavaとSQLの組み合わせ。ネタとしてSQLのみでも書いたが、明らかに「組み合わせ」のほうが易しい(Javaの部分はほかの言語で置き換え可能)。

あたりまえの結論:言語は問題にあわせて選択するといいかもしれない。一つにこだわるよりも複数を組み合わせた方がいいと思われる場合もある。

「使うべき言語」ではなく「学ぶべき言語」については、少し違った議論もできると思う。何度も書いているように、私は「サピア=ウォーフの仮説」が好き。でも、人生は(今のところ)有限(しかもかなり短い)から、誰かが「学ぶべき」と言ったものを全部学べるとはとても思えない。

補足:「どのプログラミング言語を使うべきか」論争の最近の例

論文:矢吹太朗, 佐久田博司. SQLによる数独の解法とクエリオプティマイザの有効性. 日本データベース学会論文誌. Vol.9, No.2, pp.13–18, 2010.

上記論文ではDB2ではうまく行かないと報告していますが、「DB2 for IBM i でも数独が解ける!?」によれば、論文で使ったのとは別のバージョンのDB2ではうまく行くそうです。

参考:数独の平凡な解法(C言語Mathematica

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です