SQLによる数独の解法 #deim2010


2/28から3/2にかけて開催されたDEIM2010で発表してきました。

ワークショップの様子

  1. Togetter – まとめ「DEIM2010 初日」
  2. Togetter – まとめ「DEIM2010 2日目」
  3. Togetter – まとめ「DEIM2010 最終日」

「データベースの授業で使いたい」というコメントを多くの方からいただいたので、そのためのマテリアルを公開します。

論文の最終版は後で公開します。

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

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

寛容なMySQLを非寛容にすること(その3)


結論:MySQLのsql_modeには、ONLY_FULL_GROUP_BYを入れておく

ユーザを管理するテーブルを考える。ユーザはa, bという2つの属性を持つ。テーブルはこんな感じ。

CREATE TABLE users (
id INT NOT NULL AUTO_INCREMENT PRIMARY KEY,
a INT,
b INT,
INDEX (a),
INDEX (b)
);
INSERT users (a,b) VALUES (1,1);
INSERT users (a,b) VALUES (1,2);
INSERT users (a,b) VALUES (1,3);
SELECT * FROM users;
+----+------+------+
| id | a    | b    |
+----+------+------+
|  1 |    1 |    1 |
|  2 |    1 |    2 |
|  3 |    1 |    3 |
+----+------+------+

属性aが1の人数は、次のように求められる。

SELECT count(*)
FROM users
WHERE a=1;
+----------+
| count(*) |
+----------+
|        3 |
+----------+

何かの事情でaの値も取得したいとき、安易に次のように書いてしまうかもしれない。

SELECT a,count(*)
FROM users
WHERE a=1;
+------+----------+
| a    | count(*) |
+------+----------+
|    1 |        3 |
+------+----------+

上のSELECT文は、手元のMySQL 5.0.84と5.1.37-1ubuntu5, 5.4.3-beta-communityでは動作する。しかし、MySQL 5.0.45-logでは次のようなエラーになる。

ERROR 1140 (42000): Mixing of GROUP columns (MIN(),MAX(),COUNT(),...) with no GROUP columns is illegal if there is no GROUP BY clause

リファレンスマニュアルの3.3.4.8. Counting Rowsには、上のようなSELECT文は可能だという記述があるのだが、うまくいかない環境もある(「SET sql_mode='';」としてもだめ)。

次のように書けば、どの環境でも動く。一般的に、集約関数があるときは、SELECTするものはGROUP BYの対象になっていなければならない(最初のSELECT文を実行できたのは、MySQLの独自の拡張のため)。

SELECT a,count(*)
FROM users
WHERE a=1
GROUP BY a;

SELECT a,count(*) FROM users GROUP BY a HAVING a=1;」と書いてもいいが、これを素朴実行したらさすがに遅いだろう(オプティマイザが上の形に変換してくれるとも思えない)。

このようなバージョンによる振る舞いのぶれを無くすためには、「SET sql_mode='ONLY_FULL_GROUP_BY';」として、SQLモードを変更し、MySQLの独自の拡張を無効にすればよい。こうすることによって、以下のSELECT文はすべてのバージョンでエラーになる。(ちなみに、現在のSQLモードは「SELECT @@sql_mode;」でわかる。)

SET sql_mode='ONLY_FULL_GROUP_BY';
SELECT a,count(*)
FROM users
WHERE a=1;
ERROR 1140 (42000): Mixing of GROUP columns (MIN(),MAX(),COUNT(),...) with no GROUP columns is illegal if there is no GROUP BY clause

そもそも、曖昧なSELECT文を実行させるような独自拡張に何の意義があるのだろうか。リファレンスマニュアルの12.16.3 MySQL Handling of GROUP BYには、You can use this feature to get better performance by avoiding unnecessary column sorting and groupingとあるから、パフォーマンスがよくなる可能性はある。本稿の例ではaの値は1しかないため、「GROUP BY a」をしなくて済むならそれに越したことはない。しかし、これはわざと作った例であり、実際にこういうことがうれしいという状況にあるときは、何かおかしなことをしているという自覚があるべきだろう(先に書いた「何かの事情」とはそういうことだ)。

それよりも、何か間違ったことをしているのに、MySQLの寛容さのためにその発見が遅れることがこわい。そういうことにならないための安全策として、普段から、曖昧なSELECT文を許容しないようにMySQLを設定しておくといいだろう。具体的には、my.cnfあるいはmy.iniの[mysqld]のセクションに、「sql-mode="ONLY_FULL_GROUP_BY"」と書いておけばよい。

もっと非寛容にしたい向きは、リファレンスマニュアルの5.1.7. Server SQL Modesから、それらしいものを見繕ってくればいい。TRADITIONAL(STRICT_TRANS_TABLES, STRICT_ALL_TABLES, NO_ZERO_IN_DATE, NO_ZERO_DATE, ERROR_FOR_DIVISION_BY_ZERO, NO_AUTO_CREATE_USERをまとめたもの)あたりから試すのがおすすめか。

お約束ですが、こういう話を基本から学びたいという方には、拙著『Webアプリケーション構築入門 実践!Webページ制作からマッシュアップまで 』(森北出版, 2011)がおすすめです。

SQL Server Express Editionで大量のデータを読み込む方法


拙著『Webアプリケーション構築入門』では、ウェブアプリの簡単な例として、郵便番号検索システムを、Javaを使って構築しています。(改訂版

ウェブアプリに関してはもう1冊著書があります。『Microsoft Visual Web Developer 2008 Express Edition入門』です。こちらはASP.NET(C#あるいはVisual Basic)なのですが、『Webアプリケーション構築入門』で作成した程度の簡単な郵便番号検索システムなら、こちらのほうが簡単に構築できます。

しかし、郵便番号データをSQL Server Express Editionで使えるようにするのが少し面倒なので、その方法を紹介します。(この点に関して言えば、SQL Server Express EditionよりもMySQLのほうがはるかに簡単です。)

まず、郵便番号データをダウンロードします。「読み仮名データの促音・拗音を小書きで表記するもの」の「全国一括」でいいでしょう。ダウンロードしたファイルを展開し、テキストファイル内の二重引用符を削除し、カンマをタブに置き換えておきます(後述のformat.fmtの「\t」を「,」にするなら、カンマの変換は実は不要です)。

Visual Web Developer(VWD, Visual Studioのウェブアプリ用無償版)上では、大量のデータを読み込むためのBULK INSERT文が(たぶん)使えないので、SQL Server Management Studioでデータベースとテーブルを作り、それをVWDで使うことにします。

データベースを作ります。

データベース名は「mydb」にしましょう。

GUIでテーブルを作るのは面倒なので、SQLを使います。

実行するSQLはこんな感じです。

USE [mydb]
GO
SET ANSI_NULLS ON
GO
SET QUOTED_IDENTIFIER ON
GO
SET ANSI_PADDING ON
GO
CREATE TABLE [dbo].[zips](
[jis] [char](10) NOT NULL,
[old_zip] [char](5) NOT NULL,
[zip] [char](7) NOT NULL,
[addr1_ruby] [ntext] NOT NULL,
[addr2_ruby] [ntext] NOT NULL,
[addr3_ruby] [ntext] NOT NULL,
[addr1] [ntext] NOT NULL,
[addr2] [ntext] NOT NULL,
[addr3] [ntext] NOT NULL,
[establishment_ruby] [ntext] NOT NULL,
[establishment] [ntext] NOT NULL
) ON [PRIMARY] TEXTIMAGE_ON [PRIMARY]
GO
SET ANSI_PADDING OFF
GO
ALTER TABLE [dbo].[zips] ADD  CONSTRAINT [DF_zips_jis]  DEFAULT ('') FOR [jis]
GO
ALTER TABLE [dbo].[zips] ADD  CONSTRAINT [DF_zips_addr1_ruby]  DEFAULT ('') FOR [addr1_ruby]
GO
ALTER TABLE [dbo].[zips] ADD  CONSTRAINT [DF_zips_addr1]  DEFAULT ('') FOR [addr1]
GO
ALTER TABLE [dbo].[zips] ADD  CONSTRAINT [DF_establishment_ruby]  DEFAULT ('') FOR [establishment_ruby]
GO
ALTER TABLE [dbo].[zips] ADD  CONSTRAINT [DF_establishment]  DEFAULT ('') FOR [establishment]
GO

貼り付けて、右クリック→実行。

できたテーブルは「デザイン」で確認できます。

実は、先にあげたSQL文は、GULで作ったテーブルを「スクリプト化」したものです。(GUIは説明には不向きです。)

テーブルができたので、テキストファイルのデータをテーブルにロードします。

まず、テキストファイルとテーブルの対応関係を記述したファイルformat.fmtを用意します。(ファイルの書き方SQLCHAR等について

format.fmt
10.0
10
1 SQLCHAR 0 10 "\t" 1 jis ""
2 SQLCHAR 0 5 "\t" 2 old_zip ""
3 SQLCHAR 0 7 "\t" 3 zip ""
4 SQLCHAR 0 500 "\t" 4 addr1_ruby ""
5 SQLCHAR 0 500 "\t" 5 addr2_ruby ""
6 SQLCHAR 0 500 "\t" 6 addr3_ruby ""
7 SQLCHAR 0 500 "\t" 7 addr1 ""
8 SQLCHAR 0 500 "\t" 8 addr2 ""
9 SQLCHAR 0 500 "\t" 9 addr3 ""
10 SQLCHAR 0 500 "\r\n" 0 dummy ""

BULK INSERT文で郵便番号データを読み込みます。(参考:BULK INSERT文の詳細)。

BULK INSERT [dbo].[zips]
FROM 't:\KEN_ALL_CP932.TSV'
WITH(FORMATFILE='t:\format.fmt',CODEPAGE=932)

データを読み込み終わったら、データベースを「デタッチ」します。

このデータベースのファイルmydb.mdfをVWDのソリューション・エクスプローラでフォルダApp Dataにドラッグ&ドロップすれば、ウェブアプリから利用できます。

完成したデータベースのファイルmydb.mdf

「郵便番号検索システムの作成(ASP.NETチュートリアル)」に続く

米MS、特許主張しない約束をC#とCLI標準に適用、Monoはソースコードを2分割へ

動的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. (PDF)

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

SQLによる数独の解法


SQLを使って数独を解く方法の解説記事を書きました。3部構成のうちの第1部がCodeZineで公開されています

  1. SQLによる数独の解法
  2. SQLによる数独の高速解法(9/11に公開)
  3. 動的SQL数独の超高速解法(9/18に公開)

ナンプレ VOW

この記事を書くきっかけになったのは、Nintendo DSのゲーム「ナンプレ VOW」です。巷で売られている数独の問題はかなり簡単で、あまり頭を使わずに解けるのですが、解くときの爽快感と、VOWのおもしろさのために、つい何時間かはまってしまいました

ちなみに、少し頭を使わないと解けない問題は商品にならないそうです。難問を集めたはずの『激辛数独1』にさえ、次のような記述があります(試行錯誤が推理に含まれないのか、などということは別にしても私には納得できないのですが)

本書のすべての問題は、試行錯誤(このマスがもし○ならば、こうなってこうなってダメなので△我はいる。というような解き方)をすることなく、推理力を駆使して解けるようになっています

はまってしまったパズルゲームから抜け出す手段として、「パズルを解くプログラムを書く」というものがあります。「コンピュータで簡単に解けるようなパズルで時間を浪費するな」と自分を説得するのです(私にも「機械を差別する心」があるようです)

プログラムは簡単に書けるのでそれで終わりだったはずなのですが(せいぜい「数独ウォッチ」につっこみを入れるくらい)、ふと読んだこんな文章にひっかかりました

ここで示した解法プログラムは、まずまず高速です。図1の「Ai Escargot」パズルを2.4GHzのCPUと1GBのRAMを搭載したマシンで解いたところ、5分20秒で解答が導かれました。(高パフォーマンスなストアドプロシージャの設計

これはSQLのストアド・プロシジャの書き方を解説した記事なのですが、例題として取り上げた数独の問題を解くのに、5分20秒もかかったというのです

一度プログラムを書いているので、今のコンピュータなら数独を解くのにそんな時間はかからないということはすぐにわかります。読んだ人が「SQLダメじゃん」と思ってしまわないかも心配でした(はい、SQL好きです)。そこで、「こうやって書けば速いんじゃないかな」という方法を紹介することにしたのです

どのくらい速くなるかは第3部でのお楽しみということで

(CodeZineがMS系フォントをスタイル指定するのをやめますように)

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

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