CodeZine(コードジン)

特集ページ一覧

SQLによる数独の解法

SQLの宣言的な記述を積み重ねて、数独の簡単な問題を解く

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

基本的なデータ構造

 次のような数独の盤面を格納するテーブルを作成します(この問題は荻原上さんのサイト:ナンバープレース滝野川から許可を得て掲載しています)。

問題1
問題1

問題格納テーブル:problems

 数独の盤面をリレーショナルデータベースのテーブルに格納する方法はいろいろ考えられますが、ここでは、上の盤面を下のようなテーブル「problems」に格納することにしましょう。例えば、上から1行、左から2列目のマスには「4」が入っているので、row=1, col=2, val=4というデータが入っています。数字が入っていないマスに対応するvalは「0」とします。idは盤面の識別番号です(当分使いません)。この番号を変えることで、一つのテーブルで複数の盤面を管理できます。

problems
idrowcolval
0110
0124
0135
0212
0220
0981
0990

 テーブル「problems」を生成するSQL文は次のとおりです。

problems
DROP TABLE IF EXISTS problems//

CREATE TABLE problems (
  id INT NOT NULL DEFAULT 0,
  row INT NOT NULL,
  col INT NOT NULL,
  val INT NOT NULL,
  CONSTRAINT pro_pri PRIMARY KEY(id,row,col),
  INDEX (id), INDEX (row), INDEX (col), INDEX (val)
)//

 3×3のブロックのどこに相当するかをあらかじめ計算して格納しておいた方が速くなることが予想されますが、先に述べたように、アルゴリズムはあまり工夫しないでおきたいので、ここでは上のような単純なデータ構造を用います。

候補格納テーブル:candidates

 数独のルールから、今解いている盤面の、1行1列に入りうる数字は1, 6, 7, 8, 9のいずれかです。推論すればさらに絞り込むこともできますが、ここではルールからすぐに分かる数字だけで十分です。このような数字の候補を、次のようなテーブルで管理しましょう。

candidates
idrowcolval
0111
0116
0117
0118
0119
0141
0142
0146

 テーブル「candidates」を作成するSQL文は次のとおりです。

candidates
DROP TABLE IF EXISTS candidates//

CREATE TABLE candidates (
  id INT NOT NULL,
  row INT NOT NULL,
  col INT NOT NULL,
  val INT NOT NULL,
  INDEX (id), INDEX (row), INDEX (col), INDEX (val)
)//

 インデックスをどう設定するかは難しい問題です。例えば、テーブル「problems」には主キーがあった方が高速です。テーブル「candidates」では、SQL Server版なら(row,col), (row,val), (col,val)のインデックスがあるほうが高速ですが、MySQL版ではそういうことはなさそうです。

 「検索や結合に使うカラムにはインデックスを設定する」というのが基本です。しかし、インデックスが作成されていると更新は必ず遅くなるにも拘わらず、検索は必ずしも速くはなりません。そもそも、作成したインデックスが本当に使われるかどうかも(それを明示的に強制しない限りは)定かではありません。後述のプロシージャ:makeCandidatesには、id, row, colのすべてを指定しての検索がありますから、これらを組み合わせた主キーがテーブル「problems」にあると速くなります(解いているのはパズルですし、第3部で圧倒的に速い方法を紹介するので、ここでこの問題を追及するのはやめておきます)。

問題の入力と出力

 盤面の入出力は次のように行います。「数独を解く」という本題から離れたくないので、入出力方法の実装についての説明は「補足」に回しました。

盤面の入力

 入力は次のような形で行います。入力のためのストアド・プロシージャ:initializeは、盤面のサイズとその平方根(ふつうは9と3)をグローバル変数@maxNum@mにセットします。

CALL initialize(CONCAT(
' 45      ',
'2    97  ',
'3    8 6 ',
'      97 ',
'    3    ',
' 62      ',
' 9 3    4',
'  14    2',
'      51 '))//

盤面の出力

 盤面idを指定してストアド・プロシージャ:displayを呼び出すと、盤面を整形して表示します。

CALL display(0)//

0 4 5 0 0 0 0 0 0
2 0 0 0 0 9 7 0 0
3 0 0 0 0 8 0 6 0
0 0 0 0 0 0 9 7 0
0 0 0 0 3 0 0 0 0
0 6 2 0 0 0 0 0 0
0 9 0 3 0 0 0 0 4
0 0 1 4 0 0 0 0 2
0 0 0 0 0 0 5 1 0

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

修正履歴

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

バックナンバー

連載: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