CodeZine(コードジン)

特集ページ一覧

動的SQLによる数独の超高速解法

宣言的に書けるというSQLの性質を最大限に活用し、数独を1行のSELECT文で解く

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

ダウンロード mysql-meta.sql (2.0 KB)
ダウンロード sqlserver-meta.sql (2.3 KB)
ダウンロード Suudoku.java (1.7 KB)

目次

JDBCを用いる実装

 まず、「JavaでSELECT文を生成し、JDBCを介してRDBMS上で実行する」という戦略を実装しましょう。以下のコードは「Suudoku.java」にまとめてあります。実行方法は「実行」の項を参照してください。

準備

 配列problemに問題を格納します(以下では、行頭のインデントを一部省略しています)。

int[][] problem={{1,0,0,0,0,7,0,9,0},
                 {0,3,0,0,2,0,0,0,8},
                 {0,0,9,6,0,0,5,0,0},
                 {0,0,5,3,0,0,9,0,0},
                 {0,1,0,0,8,0,0,0,2},
                 {6,0,0,0,0,4,0,0,0},
                 {3,0,0,0,0,0,0,1,0},
                 {0,4,0,0,0,0,0,0,7},
                 {0,0,7,0,0,0,3,0,0}};
int maxNum=problem.length;
int m=(int)java.lang.Math.sqrt(maxNum);

 SELECT文の構成句を格納するコレクションを作成します(Javaの基本的なコレクションについては、文献2など別の資料を参照してください)。

Collection<String> selectItems=new LinkedList<String>();
Collection<String> fromItems=new LinkedList<String>();
Collection<String> whereItems=new TreeSet<String>();

SELECT文の生成

 各マス目の値を調べながらSELECT文を生成します。

for(int row1=0;row1<maxNum;++row1){
  for(int col1=0;col1<maxNum;++col1){
    String label1,label2;
    String item1,item2;
    label1="R"+(row1+1)+"C"+(col1+1);

SELECT節

 次のようなSELECT節を生成します。

SELECT 1 AS R1C1,tR1C2.n AS R1C2, ... ,tR9C9.n AS R9C9

 数字が入っているなら「1 AS R1C1,」、入っていないなら「tR1C2 AS R1C2,」のような文字列を生成し、コレクションselectItemsに入れておきます。

if(problem[row1][col1]!=0)
  //数字が入っている場合
  item1=Integer.toString(problem[row1][col1]);
else item1="t"+label1+".n";
selectItems.add(item1+" AS "+label1);

FROM節

 次のようなFROM節を生成します。

FROM nums tR1C2,nums tR1C3, ... ,nums tR9C9

 数字が入っていないマス目すべてに対し、「nums tR1C2」のような文字列を生成し、コレクションfromItemsに入れておきます。

    if(problem[row1][col1]==0) fromItems.add("nums t"+label1);

 行・列の順番でfor文を書いているので、各マス目に対応するテーブルの結合もこの順序で行われます。本当は、tR1C4とはtR2C3よりもtR2C4が早くに結合されるべきなので、ここで採用した方法は最善とは言えませんが、これでも実行時間は満足できる程度に早いです(最適な結合順序はオプティマイザによって決められるのが理想なのですが、クエリヒントを紹介した際に述べたように、本稿ではテーブルの結合順序の決定にはオプティマイザを使いません)。

WHERE節

 次のようなWHERE節を生成します。

WHERE 1!=tR1C2.n AND 1!=tR1C3.n AND ... AND tR9C8.n!=tR9C9.n

 WHERE節中で「!=」で結ぶべきマス目のペアをすべて列挙し、コレクションwhereItemsに入れておきます。列挙するのは、(1)同じ行にあるもの、(2)同じ列にあるもの、(3)同じブロックにあるものです。

 「tR9C8.n!=tR9C9.n」と「tR9C9.n!=tR9C8.n」のような重複する条件はオプティマイザが削除してくれるのでそのままにしても良いのですが、SQL文の長さに制限のあるRDBMSのことも考慮し、あらかじめ取り除いておきます。条件を格納するコレクションwhereItemsSetなので、「!=」の左右の項を辞書順で並べ替えてから格納することで重複を取り除くことができます。

    for(int row2=0;row2<maxNum;++row2){ //問題の数字をもう一度列挙する
      for(int col2=0;col2<maxNum;++col2){
        // どちらかが未定の場合に条件句を作る
        if(problem[row1][col1]==0 || problem[row2][col2]==0){
          if((row1==row2 && col1!=col2)    // 行が同じもの
            || (row1!=row2 && col1==col2)  // 列が同じもの
            || ((row1!=row2 && col1!=col2) // ブロックが同じもの
              && row1/m==row2/m && col1/m==col2/m)){
            label2="R"+(row2+1)+"C"+(col2+1);
            if(problem[row2][col2]!=0)
              //数字が入っている場合
              item2=Integer.toString(problem[row2][col2]);
            else item2="t"+label2+".n";
            if(item1.compareTo(item2)<0)
              whereItems.add(item1+"!="+item2); //ペアを辞書順で並べる
            else whereItems.add(item2+"!="+item1);
          }
        }
      }
    }
  } // col1のfor文
} //row1のfor文

SELECTの完成

 SELECT節とFROM節、WHERE節の各項が、それぞれコレクションselectItemsfromItemswhereItemsに格納されました。コレクションを文字列にするには「Arrays.toString(コレクション.toArray()」を使います。「[1, 2, 3]」のような文字列になりますから、両端の括弧を取り除き、区切り記号を適切なものに置き換えます。

String sql=
 "SELECT"+Arrays.toString(selectItems.toArray())
  .replaceAll("\\[|\\]"," ").replaceAll(", ",",")
+"FROM"+Arrays.toString(fromItems.toArray())
  .replaceAll("\\[|\\]"," ").replaceAll(", ",",")
//for PostgreSQL
//+"FROM"+Arrays.toString(fromItems.toArray())
//  .replaceAll("\\[|\\]"," ").replaceAll(", "," CROSS JOIN ") 
+"WHERE"+Arrays.toString(whereItems.toArray())
  .replaceAll("\\[|\\]"," ").replaceAll(","," AND");

クエリの実行

JDBCコネクションの生成

 問い合わせのための環境を準備します。データベース:testに、ユーザー名:test、パスワード:passで接続します(ここではJDBCの利用方法は説明しないので、詳しく知りたい場合は文献2など別の資料を参照してください)。

Class.forName("com.mysql.jdbc.Driver").newInstance();
Connection conn = DriverManager.getConnection(
  "jdbc:mysql://localhost/test","test","pass");
Statement stmt = conn.createStatement();

テーブル:numsの準備

 候補の数字を入れておくテーブル「nums」を生成します。この記法はMySQLのものなので、別のRDBMSを使うときは、適切な形に書き換えてください。

stmt.execute("DROP TABLE IF EXISTS nums");
stmt.execute("CREATE TABLE nums (n INT NOT NULL PRIMARY KEY)");
for(int n=1;n<=maxNum;++n)
  stmt.execute("INSERT INTO nums VALUES ("+n+")");

結果の取得

 結果の1行が数独の1つの解に相当します。特定のマス目に入る数字は、「R1C1」のようなラベルを使って取り出せます。

ResultSet rs=stmt.executeQuery(sql);
int count=0;
while(rs.next()){
  System.out.println("Solution No."+(++count));
  for(int r=0;r<maxNum;++r){
    for(int c=0;c<maxNum;++c)
      System.out.print(rs.getInt("R"+(r+1)+"C"+(c+1))+" ");
    System.out.println("");
  }
}

実行

 一連の処理を「Suudoku.java」にまとめ、次のように実行します。

javac Suudoku.java
java -classpath ".;mysql-connector-java-5.0.3-bin.jar" Suudoku

Solution No.1
1 6 2 8 5 7 4 9 3
5 3 4 1 2 9 6 7 8
7 8 9 6 4 3 5 2 1
4 7 5 3 1 2 9 8 6
9 1 3 5 8 6 7 4 2
6 2 8 7 9 4 1 3 5
3 5 6 4 7 8 2 1 9
2 4 1 9 3 5 8 6 7
8 9 7 2 6 1 3 5 4
time: 0.609

 1秒程度で解けました。


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

修正履歴

  • 2007/09/21 14:33 「JDBCを用いる実装」のWHERE節生成部を修正(ellerさんのご指摘に従って)

バックナンバー

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