はじめに
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のチューニングは無し）で行いました。
| 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 | 数独を解く |
