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のことも考慮し、あらかじめ取り除いておきます。条件を格納するコレクションwhereItems
はSet
なので、「!=
」の左右の項を辞書順で並べ替えてから格納することで重複を取り除くことができます。
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
節の各項が、それぞれコレクションselectItems
とfromItems
、whereItems
に格納されました。コレクションを文字列にするには「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秒程度で解けました。