2007年9月21日金曜日

動的SQLによる数独の超高速解法(by CodeZine)

SQLele利用スクリプト第4弾。
みんな大好きCodeZine様より転載しました。元記事は動的SQLによる数独の超高速解法。よって今回の記事を利用する場合はCodeZine様の規約に従ってください。
元記事の章・節に合わせたコメントが付いています。

……しかしこれはすごいですね。
SQLで数独を解くという発想もさることながら、その速度が充分実用的な点に驚かされます。
解法が複数ある場合でもすべて示してくれるのも素晴らしいです。

WHERE節の条件重複を回避するためにxnoteaddを利用しようとしたのですが、原因不明のエラーで落ちてしまうので独自命令で対応しています。生成されるSQL文を元記事と全く同じにするためにはWHERE節のソートも必要だったのですが、sortnoteの仕様(空行追加)がややこしかったので考慮していません。
// http://codezine.jp/a/article/aid/1629.aspx
// 動的SQLによる数独の超高速解法
#runtime "hsp3cl" 
#include "sqlele.hsp"
#module
// 文字列の置換(参考:サンプルスクリプトcompbj/comtest9.hsp)
#deffunc replace var target, str before, str after
    newcom o_reg, "VBScript.RegExp"
    comres target
    o_reg( "Pattern" ) = before         // 検索パターンの設定
    o_reg( "Global" ) = 1               // すべて置換する
    o_reg -> "Replace" target, after    // 検索の実行
    delcom o_reg
    return
// xnoteadd代替命令(今回は問題ないが、完全互換ではない点に注意)
#deffunc xnoteadd_ var target, str add
    if instr( target, 0, add + "\n" ) < 0 {
        target += add + "\n"
    }
    return
#global
    dim problem, 99
    problem(00) = 1,0,0,0,0,7,0,9,0
    problem(01) = 0,3,0,0,2,0,0,0,8
    problem(02) = 0,0,9,6,0,0,5,0,0
    problem(03) = 0,0,5,3,0,0,9,0,0
    problem(04) = 0,1,0,0,8,0,0,0,2
    problem(05) = 6,0,0,0,0,4,0,0,0
    problem(06) = 3,0,0,0,0,0,0,1,0
    problem(07) = 0,4,0,0,0,0,0,0,7
    problem(08) = 0,0,7,0,0,0,3,0,0
    max_num = length( problem )
    m = intsqrtlength( problem ) ) )

    sdim select_items, 6400
    sdim from_items, 6400
    sdim where_items, 30000

    // SELECT文の生成
    for row1, 0, max_num
        for col1, 0, max_num
            label1 = "R" + ( row1 + 1 ) + "C" + ( col1 + 1 )
            // SELECT節
            if problem( col1, row1 ) != 0 {
                item1 = str( problem( col1, row1 ) )
            } else {
                item1 = "t" + label1 + ".n"
            }
            select_items += item1 + " AS " + label1 + ","
            // FROM節
            if problem( col1, row1 ) == 0 {
                from_items += "nums t" + label1 + ","
            }
            // WHERE節
            for row2, 0, max_num
                for col2, 0, max_num
                    if ( problem( col1, row1 ) == 0 ) | ( problem( col2, row2 ) == 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( col2, row2 ) != 0 {
                                item2 = str( problem( col2, row2 ) )
                            } else {
                                item2 = "t" + label2 + ".n"
                            }
                            if ( item1 != item2 ) < 0 {
                                xnoteadd_ where_items, item1 + "!=" + item2
                            } else {
                                xnoteadd_ where_items, item2 + "!=" + item1
                            }
                        }
                    }
                next
            next
        next
    next
    // SELECTの完成
    sdim sql, 30000
    poke select_items, strlen( select_items ) - strlen"," ), 0        // 最後の余計なカンマを削除
    poke from_items, strlen( from_items ) - strlen"," ), 0            // 最後の余計なカンマを削除
    replace where_items, "\\n"" AND "                                 // 改行を削除
    poke where_items, strlen( where_items ) - strlen" AND " ), 0      // 最後の余計なANDを削除
    sql = "SELECT " + select_items + " FROM " + from_items + " WHERE " + where_items
;   notesel sql : notesave "sql.txt"

// クエリの実行
    // テーブル:numsの準備
    sql_open ":memory:"
    sql_q "CREATE TABLE nums (n INTEGER NOT NULL PRIMARY KEY);"
    repeat 91
        sql_q "INSERT INTO nums VALUES (" + prm_i(cnt) + ");"
    loop
    // 結果の取得
    sql_q sql
    repeat stat1
        mes "Solution No." + cnt
        for r, 0, max_num
            s = ""
            for c, 0, max_num
                s += strf("%1d "sql_i"R" + ( r + 1 ) + "C" + ( c + 1 ) ) )
            next
            mes s
        next
        sql_next
    loop

    sql_close
    stop

2 件のコメント:

sprocket さんのコメント...

数独ってやったことなかったんで、Wikipedia にあったサンプルのをやってみました。あれが SELECT 一回で解けるんですね。

欲しい結果の条件さえ与えれば結果を求める方法を考えなくてもいいというのが SQL の便利なところですが、パズルの拘束条件から解答を得るような使い方は、SQL を考案した人たちにも思いもよらなかったでしょうね。

eller さんのコメント...

返信遅くなりました。

数独はルールが単純なので、コンピュータに向いているのかもしれません。それでもSELECT一回でOKというのは凄いことですが。

>SQLの便利なところ...思いもよらなかった
確かにそうですね。よく思いついたなぁと感心します。