数独の解法1（単純な場合）
「数字の候補が一つしか無いマス目には、その数字を入れる」という戦略を実装します。
候補の列挙
空白部分に入り得る数字を決めていきます。まず、すべての可能性を列挙し、そこからルールに反するものを除外します。
すべての可能性
すべての可能性は、テーブル「nums」を3つ使って生成することができます（「複数のテーブルを結合して組み合わせを生成する」というテクニックを使っています）。
-- すべての可能性 SELECT 0 AS id,a.n AS row,b.n AS col,c.n AS val FROM nums a,nums b,nums c//
| id | row | col | val |
| 0 | 1 | 1 | 1 |
| 0 | 1 | 1 | 2 |
| 0 | 1 | 1 | 3 |
| 0 | 1 | 1 | 4 |
| 0 | 1 | 1 | 5 |
| 0 | 1 | 1 | 6 |
| 0 | 1 | 1 | 7 |
| 0 | 1 | 1 | 8 |
| 0 | 1 | 1 | 9 |
| 0 | 1 | 2 | 1 |
| 0 | 1 | 2 | 2 |
| … | … | … | … |
未定の部分
上述の「すべての可能性」というのはちょっと考えがなさ過ぎます。考えるべきは盤面の空白部分、つまりテーブル「problems」で値が0のところについてだけです（図の水色部分）。
空白部分は次のように得られます。
-- 空白部分 SELECT * FROM problems WHERE val=0//
ですから、先述のSELECT文は、次のように改良できます（条件を結合する条件は「row=a.n AND col=b.n」です）。
-- すべての可能性 SELECT 0 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 val=0 AND row=a.n AND col=b.n)//
このように、「小さい文から始めて、条件や副問い合わせを追加しながら目的の文に近づけていく」というのがSQL文を書くコツです。この作業をさらに続けます。
数独のルール
数独のルールを適用しましょう。例えば、5行3列に入れられない数字は、第5行あるいは第3列、5行3列が属するブロックに登場するものです（水色部分にある数字）。
これらは次のように取得することができます（商を求めるのに「DIV」を使うのはMySQL独自の書き方で、「/」を使うのが一般的です）。
-- 特定のマス目に入らない数字 SELECT * FROM problems WHERE val!=0 AND (row=5 OR col=3 OR ((row-1) DIV 3=(5-1) DIV 3 AND (col-1) DIV 3=(3-1) DIV 3))// +----+-----+-----+-----+ | id | row | col | val | +----+-----+-----+-----+ | 0 | 6 | 2 | 6 | | 0 | 1 | 3 | 5 | | 0 | 6 | 3 | 2 | | 0 | 8 | 3 | 1 | | 0 | 5 | 5 | 3 | +----+-----+-----+-----+
一般化して言えば、a.n行b.n列にc.nが入り得るためには、テーブル「problems」の(1) a.n行、(2) b.n列、(3) a.n行b.n列が属するブロックに、数字c.nがあってはいけません。先ほどのSELECT文にこの条件を加えると、次のようになります（結合条件を入れて書き換えています）。
SELECT 0 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 val=0 AND row=a.n AND col=b.n) AND NOT EXISTS ( -- 特定のマス目に入らない数字 SELECT * FROM problems WHERE val=c.n AND (row=a.n OR col=b.nv OR ((row-1) DIV 3=(a.n-1) DIV 3 AND (col-1) DIV 3=(b.n-1) DIV 3)))//
プロシージャ:makeCandidates
指定したidの盤面だけに対して、これまで紹介した操作を行うプロシージャ:makeCandidatesは次のようになります（引数のtheIdで盤面idを与えます）。
DROP PROCEDURE IF EXISTS makeCandidates// CREATE PROCEDURE makeCandidates(theId INT) BEGIN DELETE FROM candidates; INSERT INTO candidates -- 結果をテーブルに挿入 SELECT 0 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 val=0 AND row=a.n AND col=b.n) AND NOT EXISTS ( SELECT * FROM problems WHERE 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;//
プロシージャを実行します。
CALL makeCandidates(0)//
数字の当てはめ
7行8列に注目してください。
ここに入る数字は「8」しかないことは、数独のルールからすぐに分かります。実際に、テーブル「candidates」でもそうなっています。
SELECT val FROM candidates WHERE row=7 AND col=8// +-----+ | val | +-----+ | 8 | +-----+
ですから、この場所は「8」に決まりです。
このように、入り得る数字が一つしかない場所は、その数字に決まりです。この作業のためにまず、入り得る数字の候補が一つしかない場所を取り出します（今の場合1カ所しかありません）。
SELECT row,col FROM candidates GROUP BY row,col HAVING COUNT(val)=1// +-----+-----+ | row | col | +-----+-----+ | 7 | 8 | +-----+-----+
その場所に入る数字を知るために、テーブル「candidates」と結合させます。
SELECT a.row,a.col,a.val FROM candidates a JOIN ( `` SELECT row,col FROM candidates GROUP BY row,col HAVING COUNT(val)=1`` ) tmp ON tmp.row=a.row AND tmp.col=a.col// +-----+-----+-----+ | row | col | val | +-----+-----+-----+ | 7 | 8 | 8 | +-----+-----+-----+
実はこの操作は、MySQLに限っては次のように書くこともできますが、SQL Serverではエラーになるので、ここでは使いません。
SELECT row,col,val FROM candidates GROUP BY row,col HAVING COUNT(val)=1//
候補が一つしかない場所に、その数字を当てはめるようなストアド・プロシージャ:updateProblemにまとめておきましょう。
DROP PROCEDURE IF EXISTS updateProblem// CREATE PROCEDURE updateProblem(theId INT) BEGIN UPDATE problems JOIN ( SELECT a.row,a.col,a.val FROM candidates a JOIN ( SELECT row,col FROM candidates GROUP BY row,col HAVING COUNT(val)=1 ) tmp ON tmp.row=a.row AND tmp.col=a.col ) tmp2 ON problems.row=tmp2.row AND problems.col=tmp2.col SET problems.val=tmp2.val; END;//
解法1のまとめ
今挑戦している問題は、makeCandidatesとupdateProblemを繰り返せば解けます。この操作をストアド・プロシージャ:simpleDeductionにまとめておきましょう。空白部分（値が0のところ）の数が変わらなくなるまで繰り返します。
DROP PROCEDURE IF EXISTS simpleDeduction// CREATE PROCEDURE simpleDeduction(theId INT) BEGIN DECLARE oldResult,newResult INT DEFAULT 0; REPEAT -- 繰り返し。終了条件はUNTILに SET oldResult=newResult; -- 候補を求める。 CALL makeCandidates(0); -- 数字を当てはめる。 CALL updateProblem(0); -- 空白部分を数える。 SELECT COUNT(*) INTO newResult FROM problems WHERE val=0; UNTIL (newResult=0 || oldResult=newResult) END REPEAT; END;//
実際に解けることを確認します。
CALL initialize(CONCAT( ' 45 ', '2 97 ', '3 8 6 ', ' 97 ', ' 3 ', ' 62 ', ' 9 3 4', ' 14 2', ' 51 '))// CALL simpleDeduction(0)// CALL display(0)// 8 4 5 7 6 3 1 2 9 2 1 6 5 4 9 7 3 8 3 7 9 2 1 8 4 6 5 1 3 4 8 5 2 9 7 6 9 5 8 6 3 7 2 4 1 7 6 2 1 9 4 8 5 3 5 9 7 3 2 1 6 8 4 6 8 1 4 7 5 3 9 2 4 2 3 9 8 6 5 1 7 -- 0（未定部分）がない、つまり解けた。
