SQLによる数独の高速解法

続「SQLによる数独の解法」 数独の難問を解く

本稿では、SQLを使って数独を解くことを通じて、SQLが持つ宣言的な言語の特徴を紹介します。3編構成の第2部では、バックトラックを用い、第1部で解けなかった問題に挑戦します。

はじめに

　SQLを使って数独を解く方法の第2部です。第1部で解けなかった問題に挑戦します（本稿を読み進める前に第1部「SQLによる数独の解法」をお読みください）。バックトラック（パズルを解く際によく用いられる手法）を実装するので、どんな問題でも解けるようになります。

　タイトルにある「高速」というのは、Gene Pinski著 『高パフォーマンスなストアドプロシージャの設計』で公開されているコード（以下CALCULATE_GS_V3）に比べて、という意味です。Pinskiさんの方法は、AlEscargotと呼ばれる問題を解くのに、筆者の環境で200秒ほどかかります（書き間違えではありません。Pinskiさんも2.5GHzのCPUと1GBのRAMを搭載したマシンで5分20秒かかったと書かれています）。本稿で紹介する方法は、同じ問題を24秒ほどで解けます。測定は筆者の環境（Athlon64 X2 3800+、2GB Memory、Windows XP 32-Bit、RDBMSのチューニングは無し）で行いました。

AlEscargotを解くのにかかるおおよその時間

	MySQL	SQL Server
CALCULATE_GS_V3		200秒
本稿（第2部）	40秒	25秒

　CALCULATE_GS_V3は控えめに言っても「遅すぎる」ので、これに比べて「高速」であっても、「数独」の解法として特別高速なわけではありません（数独をコンピュータで解いた経験のある人なら、標準的なサイズ9×9の数独を、今日の計算機は数秒で解くことはご存じでしょう）。しかしながら、本稿で紹介するSQLの書き方は、さまざまな場面で応用できるはずです。ここで紹介する方法よりも劇的に速い方法を第3部で紹介しているので併せてお読みください（1秒程度で解けます）。

対象読者

• 計算機でパズルを解くことに興味のある方
• 数独を知っている方（数独自体についての説明はしません）
• ストアド・プロシージャについて学びたい（ストアド・プロシージャ自体については説明しませんが、雰囲気は分かると思います）
• データベース管理システムで「データの管理」を超えたことをしてみたい方

必要な環境

　本文のコードをそのまま実行するにはMySQL 5が必要です。AlEscargotを解いて結果を表示するためのコードをファイルにまとめてあります。ファイルも最後のほうで盤面を設定していますから、そこを書き換えれば、別の問題を解くことができます。PinskiさんのコードがSQL Server用なので、比較のためにSQL Server版も用意しました（ただし9×9の数独にしか対応させていません）。

• MySQL版（MySQL 5.0.37で動作を確認しました）
• SQL Server版（SQL Server 2005 Express Editionで動作を確認しました）

　ストアド・プロシージャをサポートするRDBMSなら、本稿のアイディアを実装できるはずですが、ストアド・プロシージャの書き方はRDBMSによって大きく異なるので、書き直すのはかなり面倒でしょう。

本稿の概要

　本稿で紹介する手法の構成要素を簡単に紹介しておきます。太字のものは本稿で始めて登場するものです。太字でないものの詳細については、第1部を参照してください。

テーブル

名前	用途
nums	整数を入れておく（通常は1から9が入っている）
problems	数独の盤面を格納する
candidates	マス目に入り得る数字を管理する

ストアド・プロシージャ

名前	用途
initialize	盤面を入力する
display	盤面を出力する
makeNumSeq	テーブル「nums」に1からn（引数）までの整数を格納する
makeCandidates	入り得る数字の候補を求める
updateProblem	候補の中から数字を決定する
simpleDeduction	makeCandidatesとupdateProblemを繰り返す
copyProblem	盤面をコピーする（関数として実装）
expand	決められない部分の数字を仮定して新しい盤面を作る
isValid	盤面が数独のルールに違反していないかを調べる
solve	数独を解く