数独の解法3（バックトラック）
これが第1部で解けなかった問題です（この問題はTom Davis “The Mathematics of Sudoku”で、難問として紹介されているものです）。
CALL initialize(CONCAT( ' 7 94 ', ' 7 9 5', '3 5 7 ', ' 874 1 ', '463 8 ', ' 7 8 ', '8 7 ', '7 28', ' 5 268 '))// CALL simpleDeduction(0)// CALL display(0)// 0 0 0 0 7 0 9 4 0 0 7 0 0 9 0 0 0 5 3 0 0 0 0 5 0 7 0 0 8 7 4 0 0 1 0 0 4 6 3 0 8 0 0 0 0 0 0 0 0 0 7 0 8 0 8 0 0 7 0 0 0 0 0 7 0 0 0 0 0 0 2 8 0 5 0 2 6 8 0 0 0 -- 0（未定部分）がある、つまり解けていない。
ここではアルゴリズムを工夫するのではなく、計算パワーに頼ることにしましょう。「数字を仮定して作業を進め、矛盾が生じたら仮定を棄却する（バックトラック）」という戦略を実装します。
例えば、今の段階では1行1列に入る数字は次のとおりです。
SELECT * FROM candidates WHERE row=1 AND col=1// +----+-----+-----+-----+ | id | row | col | val | +----+-----+-----+-----+ | 0 | 1 | 1 | 1 | | 0 | 1 | 1 | 2 | | 0 | 1 | 1 | 5 | | 0 | 1 | 1 | 6 | +----+-----+-----+-----+
1行1列の数字を「1」に仮定して、先に進んでみます。それでもし数字を埋められない事態になったら、仮定（つまり1行1列を「1」にしたこと）が間違っていたことになりますから、そこまで戻って、今度は「2」を試します。このような手続きを「バックトラック」と言います。解が複数ある場合にも対応できるように、もし「2」で成功したとしても（実際そうなのですが）、「5」と「6」も試すことにしましょう。
バックトラック
一般的に、バックトラックは手続きを再帰的に呼び出すことで実現します。しかしながら、MySQLのストアド・プロシージャは再帰呼び出しをサポートしていませんから、別の方法で実現しなければなりません（SQL Serverも再帰の深さに32という上限があります）。そのための補助的な手続きを用意しましょう（「再帰をサポートしていない」というのは、SQLでふつうにパズルを解こうとする際の、最大の欠点だと筆者は思います。しかしながら、数独の場合は第3部の解法があるため、このことは大した問題ではありません）。
盤面のコピー
識別idがtheIdであるような盤面をコピーして、そのr行c列の値をvにするようなファンクション:copyProblemを実装します。
新たに生成される盤面のidは、それまで使われているidの最大値+1とします。
SELECT MAX(id)+1 INTO newId FROM problems;
盤面をコピーして、値を設定します。
INSERT INTO problems SELECT newId AS id,row,col,val FROM problems WHERE id=theId; UPDATE problems SET val=v WHERE id=newId AND row=r AND col=c;
全体を次のようなファンクション:copyProblemにまとめておきます。プロシージャではなくファンクションにする理由は後で説明します（ファンクション中でUPDATEを実行できないRDBMSもあるので注意してください）。
DROP FUNCTION IF EXISTS copyProblem// CREATE FUNCTION copyProblem(theId INT,r INT,c INT,v INT) RETURNS INT MODIFIES SQL DATA BEGIN DECLARE newId INT; SELECT MAX(id)+1 INTO newId FROM problems; INSERT INTO problems SELECT newId AS id,row,col,val FROM problems WHERE id=theId; UPDATE problems SET val=v WHERE id=newId AND row=r AND col=c; RETURN 1; END;//
仮定
値が決まっていない場所を一つ選びましょう。
-- 値の決まらない場所を一つ選択 SELECT row,col FROM problems a WHERE val=0 AND EXISTS ( SELECT * FROM candidates b WHERE b.id=0 AND a.row=b.row AND a.col=b.col) GROUP BY row,col LIMIT 1// +-----+-----+ | row | col | +-----+-----+ | 1 | 1 | +-----+-----+
この1行1列に入り得るすべての数字をいったん別のテーブル「tmp」に格納します。
-- 選択した場所に入り得る数字を取得 CREATE TEMPORARY TABLE tmp SELECT val FROM candidates WHERE id=0 AND row=1 AND col=1//
盤面を4つコピーし、それぞれの1行1列に1、2、5、6を入れます。先ほど、copyProblemをプロシージャではなくファンクションにしていたのは、この作業を一つのSELECT文で書くためでした。
-- 数字を仮定して、新しい盤面を作る SELECT copyProblem(0,1,1,val) FROM tmp//
実際に盤面がコピーされていることを確認してみましょう。
CALL display(1)// 1 0 0 0 7 0 9 4 0 0 7 0 0 9 0 0 0 5 3 0 0 0 0 5 0 7 0 0 8 7 4 0 0 1 0 0 4 6 3 0 8 0 0 0 0 0 0 0 0 0 7 0 8 0 8 0 0 7 0 0 0 0 0 7 0 0 0 0 0 0 2 8 0 5 0 2 6 8 0 0 0 CALL display(2)// 2 0 0 0 7 0 9 4 0 0 7 0 0 9 0 0 0 5 3 0 0 0 0 5 0 7 0 0 8 7 4 0 0 1 0 0 4 6 3 0 8 0 0 0 0 0 0 0 0 0 7 0 8 0 8 0 0 7 0 0 0 0 0 7 0 0 0 0 0 0 2 8 0 5 0 2 6 8 0 0 0 CALL display(3)// 5 0 0 0 7 0 9 4 0 0 7 0 0 9 0 0 0 5 3 0 0 0 0 5 0 7 0 0 8 7 4 0 0 1 0 0 4 6 3 0 8 0 0 0 0 0 0 0 0 0 7 0 8 0 8 0 0 7 0 0 0 0 0 7 0 0 0 0 0 0 2 8 0 5 0 2 6 8 0 0 0 CALL display(4)// 6 0 0 0 7 0 9 4 0 0 7 0 0 9 0 0 0 5 3 0 0 0 0 5 0 7 0 0 8 7 4 0 0 1 0 0 4 6 3 0 8 0 0 0 0 0 0 0 0 0 7 0 8 0 8 0 0 7 0 0 0 0 0 7 0 0 0 0 0 0 2 8 0 5 0 2 6 8 0 0 0
以上の手続きを一つのプロシージャ:expandにまとめます（copyProblemの戻り値を入れる変数iはダミーです）。
DROP PROCEDURE IF EXISTS expand// CREATE PROCEDURE expand(theId INT) BEGIN DECLARE ro,co,i INT; -- 値の決まらない場所を一つ選択 SELECT row,col INTO ro,co FROM problems a WHERE id=theId AND val=0 AND EXISTS ( SELECT * FROM candidates b WHERE b.id=theId AND a.row=b.row AND a.col=b.col) GROUP BY row,col LIMIT 1; IF ro IS NOT NULL THEN DROP TABLE IF EXISTS tmp; -- 選択した場所に入り得る数字を取得 CREATE TEMPORARY TABLE tmp SELECT val FROM candidates WHERE id=theId AND row=ro AND col=co; -- 数字を仮定して、新しい盤面を作る SELECT SUM(copyProblem(theId,ro,co,val)) INTO i FROM tmp; END IF; END;//
プロシージャ:makeCandidatesの複数盤面対応
これまで、表示したい盤面のidを指定しなければならないプロシージャ:displayだけは、複数盤面対応ができていました。他のプロシージャも複数盤面対応してなければなりません。次のように修正しましょう。
DROP PROCEDURE IF EXISTS makeCandidates// CREATE PROCEDURE makeCandidates(theId INT) BEGIN DELETE from candidates WHERE id=theId; INSERT INTO candidates SELECT theId AS id,a.n AS row,b.n AS col,c.n AS val FROM nums a,nums b,nums c WHERE EXISTS ( SELECT * FROM problems WHERE id=theId AND val=0 AND row=a.n AND col=b.n) AND NOT EXISTS ( SELECT * FROM problems WHERE id=theId AND val=c.n AND (row=a.n OR col=b.n OR ((row-1) DIV @m=(a.n-1) DIV @m AND (col-1) DIV @m=(b.n-1) DIV @m))); END;//
プロシージャ:updateProblemの複数盤面対応
updateProblemも複数盤面に対応させます。
DROP PROCEDURE IF EXISTS updateProblem// CREATE PROCEDURE updateProblem(theId INT) BEGIN UPDATE problems JOIN ( SELECT a.id,a.row,a.col,a.val FROM candidates a JOIN ( SELECT row,col FROM candidates WHERE id=theId GROUP BY row,col HAVING COUNT(val)=1 ) tmp ON tmp.row=a.row AND tmp.col=a.col WHERE a.id=theId UNION SELECT a.id,a.row,a.col,a.val FROM candidates a JOIN ( SELECT row,val FROM candidates WHERE id=theId GROUP BY row,val HAVING COUNT(val)=1 ) tmp ON tmp.row=a.row AND tmp.val=a.val WHERE a.id=theId UNION SELECT a.id,a.row,a.col,a.val FROM candidates a JOIN ( SELECT col,val FROM candidates WHERE id=theId GROUP BY col,val HAVING COUNT(val)=1 ) tmp ON tmp.col=a.col AND tmp.val=a.val WHERE a.id=theId UNION SELECT a.id,a.row,a.col,a.val FROM candidates a JOIN ( SELECT val,(row-1) DIV @m AS x,(col-1) DIV @m AS y FROM candidates WHERE id=theId GROUP BY x,y,val HAVING COUNT(val)=1 ) tmp ON tmp.x=(a.row-1) DIV @m AND tmp.y=(a.col-1) DIV @m AND tmp.val=a.val WHERE a.id=theId ) tmp2 ON problems.id=tmp2.id AND problems.row=tmp2.row AND problems.col=tmp2.col SET problems.val=tmp2.val; END;
