盤面のチェック
数字を仮定するため、途中でルールに反する状態になる可能性があります。その状態を検出できるようにしましょう。実験のために、1行1列に「7」が入ってしまったとしましょう。これはルールに反しています。
問題3：ルール違反の盤面
CALL initialize(CONCAT( ' 7 94 ', ' 7 9 5', '3 5 7 ', ' 874 1 ', '463 8 ', ' 7 8 ', '8 7 ', '7 28', ' 5 268 '))// SELECT copyProblem(0,1,1,7)// CALL display(1)// 7 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
1行目にルール違反があることは、次のように確認できます。
SELECT row,val FROM problems WHERE id=1 AND val!=0 GROUP BY row,val HAVING COUNT(val)>1// +-----+-----+ | row | val | +-----+-----+ | 1 | 7 | +-----+-----+
列についても同様です。
SELECT col,val FROM problems WHERE id=1 AND val!=0 GROUP BY col,val HAVING COUNT(val)>1// +-----+-----+ | col | val | +-----+-----+ | 1 | 7 | +-----+-----+
同様に、左上のブロックにルール違反があることは、次のように確認できます。
SELECT (row-1) DIV 3 AS x,(col-1) DIV 3 as y,val FROM problems WHERE id=1 AND val!=0 GROUP BY x,y,val HAVING COUNT(val)>1// +------+------+-----+ | x | y | val | +------+------+-----+ | 0 | 0 | 7 | +------+------+-----+
これらのチェックをファンクション:isValidにまとめておきます。この関数は、盤面がルールに違反していなければ空白の数を、違反していれば-1を返します。
isValid
DROP FUNCTION IF EXISTS isValid// CREATE FUNCTION isValid(theId INT) RETURNS INT READS SQL DATA BEGIN DECLARE i,j,k INT; -- 行に関するルール違反を調べる SELECT row,val INTO i,j FROM problems WHERE id=theId AND val!=0 GROUP BY row,val HAVING COUNT(val)>1 LIMIT 1; IF i IS NOT NULL THEN RETURN -1; END IF; -- 列に関するルール違反を調べる SELECT col,val INTO i,j FROM problems WHERE id=theId AND val!=0 GROUP BY col,val HAVING COUNT(val)>1 LIMIT 1; IF i IS NOT NULL THEN RETURN -1; END IF; -- ブロックに関するルール違反を調べる SELECT (row-1) DIV @m AS x,(col-1) DIV @m AS y,val INTO i,j,k FROM problems WHERE id=theId AND val!=0 GROUP BY x,y,val HAVING COUNT(val)>1 LIMIT 1; IF i IS NOT NULL THEN RETURN -1; END IF; -- 空白の数を返す SELECT COUNT(*) INTO i FROM problems WHERE id=theId AND val=0; RETURN i; END;//
盤面id=0は大丈夫ですが、盤面id=1はルールに違反していることが確認できます。
SELECT isValid(0)// +------------+ | isValid(0) | +------------+ | 53 | +------------+ SELECT isValid(1)// +------------+ | isValid(1) | +------------+ | -1 | +------------+
ファンクション:simpleDeductionの修正
ファンクション:simpleDeductionはほとんど変わりません。複数盤面に対応させ、isValidが0を返した時を終了条件に加えます（盤面を消去します）。
simpleDeduction
DROP PROCEDURE IF EXISTS simpleDeduction// CREATE PROCEDURE simpleDeduction(theId INT) BEGIN DECLARE oldResult,newResult INT DEFAULT 0; SET newResult=1; WHILE 0<newResult AND oldResult!=newResult DO SET oldResult=newResult; CALL makeCandidates(theId); -- 候補を求める CALL updateProblem(theId); -- 数字を当てはめる SELECT isValid(theId) INTO newResult; -- ルール違反を調べる IF newResult<0 THEN -- ルール違反をしていたら盤面を消去 DELETE FROM problems WHERE id=theId; END IF; END WHILE; END;//
主要プロシージャ:solve
バックトラックを使って数独を解く手続きを、プロシージャ:solveにまとめます。この手続きは次のように進みます。
- まだ解いていない盤面を、
simpleDeductionで解く - すべて数字が決まったなら結果を表示する
- 空白が残っているなら、そこに仮に数字を入れた盤面を作り、1.に戻る
solve
DROP PROCEDURE IF EXISTS solve// CREATE PROCEDURE solve() BEGIN DECLARE theId,result INT DEFAULT 0; DELETE FROM problems WHERE id>0; DELETE FROM candidates; REPEAT -- まだ解いていない盤面を、simpleDeductionで解く CALL simpleDeduction(theId); -- すべて数字が決まったなら結果を表示する SELECT COUNT(*) INTO result FROM problems WHERE id=theId AND val!=0; IF result=@maxNum*@maxNum THEN CALL display(theId); ELSE -- 空白が残っている（盤面は残っているからルール違反は無い） IF result!=0 THEN CALL expand(theId); -- 仮に数字を入れた盤面を作る END IF; DELETE FROM problems WHERE id=theId; END IF; DELETE FROM candidates WHERE id=theId; SET theId=theId+1; SELECT MAX(id) INTO result FROM problems; UNTIL result<theId OR result IS NULL END REPEAT; END;//
CALL initialize(CONCAT( ' 7 94 ', ' 7 9 5', '3 5 7 ', ' 874 1 ', '463 8 ', ' 7 8 ', '8 7 ', '7 28', ' 5 268 '))// CALL solve()// 2 1 5 8 7 6 9 4 3 6 7 8 3 9 4 2 1 5 3 4 9 1 2 5 8 7 6 5 8 7 4 3 2 1 6 9 4 6 3 9 8 1 7 5 2 1 9 2 6 5 7 3 8 4 8 2 6 7 4 3 5 9 1 7 3 4 5 1 9 6 2 8 9 5 1 2 6 8 4 3 7 1 row in set (7.88 sec) Query OK, 0 rows affected, 665 warnings (24.64 sec) -- 0（未定部分）がない、つまり解けた。
