Shoeisha Technology Media

CodeZine(コードジン)

記事種別から探す

SQLによる数独の高速解法

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

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

本稿では、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を解くのにかかるおおよその時間
MySQLSQL Server
CALCULATE_GS_V3200秒
本稿(第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候補の中から数字を決定する
simpleDeductionmakeCandidatesとupdateProblemを繰り返す
copyProblem盤面をコピーする(関数として実装)
expand決められない部分の数字を仮定して新しい盤面を作る
isValid盤面が数独のルールに違反していないかを調べる
solve数独を解く

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

修正履歴

  • 2007/09/21 17:08 第3部へのリンクを追加

著者プロフィール

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

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

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

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

バックナンバー

連載:SQLで解く数独
All contents copyright © 2005-2017 Shoeisha Co., Ltd. All rights reserved. ver.1.5