SHOEISHA iD

※旧SEメンバーシップ会員の方は、同じ登録情報(メールアドレス&パスワード)でログインいただけます

CodeZine編集部では、現場で活躍するデベロッパーをスターにするためのカンファレンス「Developers Summit」や、エンジニアの生きざまをブーストするためのイベント「Developers Boost」など、さまざまなカンファレンスを企画・運営しています。

SQLで解く数独

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

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


  • X ポスト
  • このエントリーをはてなブックマークに追加

ダウンロード 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秒程度で解けました。

次のページ
ストアド・プロシージャを用いる実装

修正履歴

この記事は参考になりましたか?

  • X ポスト
  • このエントリーをはてなブックマークに追加
SQLで解く数独連載記事一覧

もっと読む

この記事の著者

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

静岡県榛原町生まれ。一橋大学経済学部卒業後、NECにてシステム企画業務に携わるが、2003年4月に念願かなってフリーライターに転身。Microsoft MVP for Visual Studio and Development Technologies。執筆コミュニティ「WINGSプロジェクト」代表。主な著書に「独習シリーズ(Java・C#・Python・PHP・Ruby・JSP&サーブレットなど)」「速習シリーズ(ASP.NET Core・Vue.js・React・TypeScript・ECMAScript、Laravelなど)」「改訂3版JavaScript本格入門」「これからはじめるReact実践入門」「はじめてのAndroidアプリ開発 Kotlin編 」他、著書多数

※プロフィールは、執筆時点、または直近の記事の寄稿時点での内容です

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

WINGSプロジェクトについて>有限会社 WINGSプロジェクトが運営する、テクニカル執筆コミュニティ(代表 山田祥寛)。主にWeb開発分野の書籍/記事執筆、翻訳、講演等を幅広く手がける。2018年11月時点での登録メンバは55名で、現在も執筆メンバを募集中。興味のある方は、どしどし応募頂きたい。著書記事多数。 RSS X: @WingsPro_info(公式)、@WingsPro_info/wings(メンバーリスト) Facebook

※プロフィールは、執筆時点、または直近の記事の寄稿時点での内容です

この記事は参考になりましたか?

この記事をシェア

  • X ポスト
  • このエントリーをはてなブックマークに追加
CodeZine(コードジン)
https://codezine.jp/article/detail/1629 2007/09/21 14:35

おすすめ

アクセスランキング

アクセスランキング

イベント

CodeZine編集部では、現場で活躍するデベロッパーをスターにするためのカンファレンス「Developers Summit」や、エンジニアの生きざまをブーストするためのイベント「Developers Boost」など、さまざまなカンファレンスを企画・運営しています。

新規会員登録無料のご案内

  • ・全ての過去記事が閲覧できます
  • ・会員限定メルマガを受信できます

メールバックナンバー

アクセスランキング

アクセスランキング