CodeZine(コードジン)

特集ページ一覧

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

宣言的に書けるというSQLの性質を最大限に活用し、数独を1行のSELECT文で解く

  • LINEで送る
  • このエントリーをはてなブックマークに追加
2007/09/18 14:00

ダウンロード mysql-meta.sql (2.0 KB)
ダウンロード sqlserver-meta.sql (2.3 KB)
ダウンロード Suudoku.java (1.7 KB)

目次

対象とする数独の問題と考え方

 次のような数独の問題を解きます。これはPinskiさんの記事で紹介されている難問で、AlEscargotという名前がついています。

AlEscargot
AlEscargot

数独を解くSELECT文

 SQLでは「何が欲しいか」を書くものだと言いましたが、次のようなSELECT文ではさすがに解けません。

SELECT 解答
FROM すべてのあり得る盤面
WHERE 数独のルールに反しない

 コンピュータが解釈できる程度まで、分かりやすく書き直しましょう。そのためにまず、各マス目を次のような名前で表すことにします。

各マス目のラベル
各マス目のラベル

 AlEscargotの解を見つけるためのSELECT文は次のようになります。

SELECT 1 AS R1C1,tR1C2.n AS R1C2, ... ,tR9C9.n AS R9C9
FROM nums tR1C2,nums tR1C3, ... ,nums tR9C9
WHERE 1!=tR1C2.n AND 1!=tR1C3.n AND ... AND tR9C8.n!=tR9C9.n

FROM節

 値が決まっていないマス目に入り得るすべての数字の組み合わせを、FROM節にテーブルを列挙することで生成します。1から9までの整数が入っているテーブル「nums」を使えば、あり得るすべての数字の組み合わせは次のように書けます(R1C1のように既に値が決まっているものを書く必要はありません)。同じテーブルを使うので、区別するためにラベルを付けておきます(テーブルを表す「t」を付けました)。

FROM nums tR1C2,nums tR1C3, ... ,nums tR9C9
注意
 PostgreSQLでは書き方が変わります(後述)。

 今解こうとしている問題ではR1C1(1行1列)の値は決まっているため、「nums tR1C1」はFROM節に入っていません。これを書いてもWHERE節に「tR1C1.n=1」という条件を追記すれば、大抵のRDBMSでは解けると思われます。処理がとても重くなるということもないでしょう。しかし、後述するように結合できるテーブルの数の制限が厳しいRDBMSもあるため、不要なテーブルはFROM節には入れないようにします。

SELECT節

 SELECT節には「欲しいもの」を列挙します。欲しいのは各マス目の値ですから、次のように書けばよいでしょう(後の処理を単純にするために、R1C1のように既に値の決まっているものも書いておきます)。

SELECT 1 AS R1C1,tR1C2.n AS R1C2, ... ,tR9C9.n AS R9C9

WHERE節

 WHERE節には「欲しいもの」の条件を書きます。「数独のルールに反しない」という条件を具体的に書けば、「各行・各列・各ブロックに同じ数字がない」ということになります。この条件はSQLで表現可能ですが、ちょっと複雑そうなので、もう少しかみ砕いて、各マス目レベルでルールを記述します。

WHERE 1!=tR1C2.n AND 1!=tR1C3.n AND ... AND tR9C8.n!=tR9C9.n

クエリヒント

 SQLが実行されるときには、最適と思われる方法(プラン)が、プランナ(オプティマイザ)によって選ばれるのがふつうです。しかし、ここで作ったSELECT文には、そういう戦略はあまり役に立ちません。例えば、テーブルの最適な結合順序を考えるのは、おそらく時間の無駄です。そういうことをしないように、OracleとSQL Server、PostgreSQLには「指示したとおりの順番でテーブルを結合せよ」という意味のクエリヒントを与えます。DerbyとMySQL、SQLiteでは、このような指示は不要です。

Oracle

 SELECTの直後に「 /*+ ORDERED */ 」を挿入します。

SQL Server

 SELECT文の最後に「 OPTION (FORCE ORDER)」を追記します。

PostgreSQL

 FROM節を次のように書くことによって、テーブルの結合順序を明示します。

FROM nums tR1C1 CROSS JOIN nums tR1C2
  CROSS JOIN ... CROSS JOIN nums tR9C9

RDBMSの制限

 上で紹介したようなSELECT文は、どんな場合でも使えるというわけではありません。

 例えば、MySQLでは結合できるテーブル数の上限が61です(参考:結合の制限)。ここで解こうとしている問題AlEscargotの空白は58個なので問題ありませんが、空白部分が62個以上(数字が19以下)の問題は、ここで紹介している方法では解けません。「『SQLによる数独の高速解法』を使って空白を減らし、空白が61個以下になったら本稿の方法で一気に解く」という戦略が必要になります(Minimum Sudokuで数字が17個の問題が多数紹介されています)。ちなみに、SQL Serverではテーブル数の上限が256なので、ひとまわり大きな盤面でもそのまま解けるはずです(参考:SQL Server 2005 の最大容量仕様)。現実的な時間で解けるかどうかは実験してみないと分かりませんが。

 また、実行できるSQL文の長さに制限のあるRDBMSでは、盤面が大きくなってSELECT文が長くなると解けなくなるおそれがあります(ここで紹介しているSELECT文は15KB程度なので問題ありません)。

動的なSQL文の生成

 前章で何気なく書いたSELECT文ですが、省略せずに書くと次のような膨大なものになります。

 とりあえず試したい場合は、次のように、テーブル「nums」を作成してからSELECT文を実行してください(コマンドプロンプトからの接続では、クエリが長すぎて実行できない可能性があります)。

CREATE TABLE nums (n INT NOT NULL PRIMARY KEY);
INSERT INTO nums VALUES (1);
INSERT INTO nums VALUES (2);
INSERT INTO nums VALUES (3);
INSERT INTO nums VALUES (4);
INSERT INTO nums VALUES (5);
INSERT INTO nums VALUES (6);
INSERT INTO nums VALUES (7);
INSERT INTO nums VALUES (8);
INSERT INTO nums VALUES (9);

 PostgreSQLでは次のSELECT文を使ってください(FROM節中のテーブルを「CROSS JOIN」で結合しています)。

 このSELECT文を手で書くのは現実的ではありません。そこで、本稿の主題である「動的SQL」です。SQL文自体を実行時に生成するのです。

 動的SQLは珍しいものではありません。多くのWebアプリケーションにおいて、サーバサイド言語(JavaやPHP、Perl、Ruby)で文字列としてSQL文を作成し、それを使ってデータベース管理システム(MySQLやSQL Server)に問い合わせ、結果を受け取ります。実行されるSQL文がいつも同じではなく実行時に決まるなら、「動的SQL」と呼んでいいでしょう。

 SQLに限らず、プログラムを動的に生成するというのは、非常に強力な手法です。典型的な例はプログラミング言語Lispにおけるマクロでしょう。Lispのコードは、それ自体がLispの基本的なデータ構造である構文木(S式)を使って表現されているため、プログラムからとても扱いやすいのです。残念ながら本稿では、SQLを単なる文字列として操作するだけで、LispにおけるS式のような扱いやすさはありません。それでも、「はじめに」で紹介したようなパフォーマンスが得られるのですから、試してみる価値は大きいです。

 本稿では、動的にSQLを生成する方法を2つ紹介します。一つはJDBCを使う方法で、これはPHPやPerl、Rubyといったデータベースへのアクセス手法が用意されている他の言語でも簡単に応用できるでしょう。もう一つはストアド・プロシージャを用いた方法で、データベースだけで話が完結します(CALCULATE_GS_V3と比較するために実装しました。分かりやすさという点ではJDBC版がお勧めです)。


  • LINEで送る
  • このエントリーをはてなブックマークに追加

修正履歴

  • 2007/09/21 14:33 「JDBCを用いる実装」のWHERE節生成部を修正(ellerさんのご指摘に従って)

バックナンバー

連載:SQLで解く数独

著者プロフィール

  • WINGSプロジェクト 矢吹 太朗(ヤブキ タロウ)

    <WINGSプロジェクトについて> 有限会社 WINGSプロジェクトが運営する、テクニカル執筆コミュニティ(代表 山田祥寛)。主にWeb開発分野の書籍/記事執筆、翻訳、講演等を幅広く手がける。2018年11月時点での登録メンバは55名で、現在も執筆メンバを募集中。興味のある方は、どしどし応募頂...

  • 山田 祥寛(ヤマダ ヨシヒロ)

    静岡県榛原町生まれ。一橋大学経済学部卒業後、NECにてシステム企画業務に携わるが、2003年4月に念願かなってフリーライターに転身。Microsoft MVP for ASP/ASP.NET。執筆コミュニティ「WINGSプロジェクト」代表。 主な著書に「入門シリーズ(サーバサイドAjax/XM...

あなたにオススメ

All contents copyright © 2005-2021 Shoeisha Co., Ltd. All rights reserved. ver.1.5