Access で数独を解く

初めに

概要

準備

解析

確定値の反映

　まずは確定値の反映である。
　確定値は可能世界要素で候補が一つしかない欄の候補である。 ある欄が確定するとその欄と行・列・エリアが同じ欄から確定した値を候補から除外する。
　例えば、確定値が次の通りならば

H	V_1	V_2	V_3	V_4	V_5	V_6	V_7	V_8	V_9
1
2
3
4
5					5
6
7
8
9

　各欄の候補は次のようになる。

H＼V	1	2	3	4	5	6	7	8	9
1	123456789	123456789	123456789	123456789	123456789	123456789	123456789	123456789	123456789
2	123456789	123456789	123456789	123456789	123456789	123456789	123456789	123456789	123456789
3	123456789	123456789	123456789	123456789	123456789	123456789	123456789	123456789	123456789
4	123456789	123456789	123456789	123456789	123456789	123456789	123456789	123456789	123456789
5	123456789	123456789	123456789	123456789	5	123456789	123456789	123456789	123456789
6	123456789	123456789	123456789	123456789	123456789	123456789	123456789	123456789	123456789
7	123456789	123456789	123456789	123456789	123456789	123456789	123456789	123456789	123456789
8	123456789	123456789	123456789	123456789	123456789	123456789	123456789	123456789	123456789
9	123456789	123456789	123456789	123456789	123456789	123456789	123456789	123456789	123456789

　ここで確定値を候補から削除すると次のようになる。

H＼V	1	2	3	4	5	6	7	8	9
1	123456789	123456789	123456789	123456789	12346789	123456789	123456789	123456789	123456789
2	123456789	123456789	123456789	123456789	12346789	123456789	123456789	123456789	123456789
3	123456789	123456789	123456789	123456789	12346789	123456789	123456789	123456789	123456789
4	123456789	123456789	123456789	12346789	12346789	12346789	123456789	123456789	123456789
5	12346789	12346789	12346789	12346789	5	12346789	12346789	12346789	12346789
6	123456789	123456789	123456789	12346789	12346789	12346789	123456789	123456789	123456789
7	123456789	123456789	123456789	123456789	12346789	123456789	123456789	123456789	123456789
8	123456789	123456789	123456789	123456789	12346789	123456789	123456789	123456789	123456789
9	123456789	123456789	123456789	123456789	12346789	123456789	123456789	123456789	123456789

　確定値は次の SQL で挙げられる。

SELECT 可能世界要素.H, 可能世界要素.V, 可能世界要素.A, First(可能世界要素.num) AS num
FROM 可能世界要素
GROUP BY 可能世界要素.H, 可能世界要素.V, 可能世界要素.A
HAVING (((Count(可能世界要素.num))=1));

　確定値自体を取得するために使用する集計関数は適切なもの (Avg,Sum,Max,Min)ならなんでもいいが、こういう場合でしか使えそうに無い「First」を持ってきた。
　確定値があるとその数字はその欄の同じ行・列・エリアには無いので削除する。

DELETE *
FROM 可能世界要素 AS W
WHERE Exists (SELECT
            *
        FROM 
            確定値 T
        WHERE
            ((T.A = W.A) AND ((T.H <> W.H) OR (T.V <> W.V)) AND (T.num=W.num))
            OR ((T.H = W.H) AND (T.V <> W.V) AND (T.num=W.num))
            OR  ((T.H <> W.H) AND (T.V = W.V) AND (T.num=W.num))
    );

　あとは繰り返しこれを実行すれば不要な可能世界要素が逐次削除される。

唯一値確定

　唯一値は、ある行・列・エリアである数字が候補となっている欄が唯一の数値とその欄である。
例えば、次の通り可能要素があるとする。

H＼V	1	2	3	4	5	6	7	8	9
1	1	279	79	4	6	8	5	279	3
2	349	49	3489	5	7	2	169	1469	469
3	6	2457	457	9	1	3	27	247	8
4	459	6	2	3	8	7	19	159	59
5	79	8	79	1	4	5	2679	3	679
6	357	157	357	2	9	6	4	1578	57
7	457	3	1	68	2	9	678	45678	4567
8	8	49	469	7	5	1	369	469	2
9	2579	2579	5679	68	3	4	6789	56789	1

この時点で確定値はすべて反映し終わっている。
この中で縦・横・エリアで唯一となっている数値があるのは 上記の色の付いた欄である。
　唯一値の欄で他の数値を削除して確定すると次のようになる。

H＼V	1	2	3	4	5	6	7	8	9
1	1	279	79	4	6	8	5	279	3
2	349	49	8	5	7	2	169	1469	469
3	6	2457	457	9	1	3	27	247	8
4	4	6	2	3	8	7	19	159	59
5	79	8	79	1	4	5	2	3	679
6	357	1	357	2	9	6	4	8	57
7	457	3	1	68	2	9	678	45678	4567
8	8	49	469	7	5	1	3	469	2
9	2	2579	5679	68	3	4	6789	56789	1

また確定値反映を行えるようになった。
　唯一値は次で挙げられる。

SELECT
    H,
    FIRST(可能世界要素.V) AS V,
    num
FROM
    可能世界要素
GROUP BY
    H,num
HAVING
    COUNT(可能世界要素.V)=1
UNION
SELECT
    FIRST(可能世界要素.H) AS H,
    V,
    num
FROM
    可能世界要素
GROUP BY
    V,num
HAVING
    COUNT(可能世界要素.H)=1
UNION SELECT
    FIRST(可能世界要素.H) AS H,
    FIRST(可能世界要素.V) AS V,
    num
FROM
    可能世界要素
GROUP BY
    A,num
HAVING
    COUNT(可能世界要素.H)=1
    AND COUNT(可能世界要素.V)=1;

　唯一値が存在する欄はその値で確定だからその欄の値以外の候補を削除する。

DELETE *
FROM 可能世界要素 AS W
WHERE EXISTS (
        SELECT
            *
        FROM
            唯一値 U
        WHERE
            (U.H = W.H)
            AND (U.V = W.V)
            AND (U.num <> W.num));

　これにより確定値が増えたら「確定値反映」で確定値を反映していく。
::::::::::::::::::以下作成中:::::::::::::::::::::::::

行ブロック射影・列ブロック射影

要素数と領域数の一致する部分閉包

　次のようなケースを考える。

H＼V	1	2	3	4	5	6	7	8	9
1	149	3	49	6	19	8	2	5	7
2	5	14689	4689	3	2	7	148	689	1469
3	1689	2	7	4	19	5	3	689	169
4	168	1568	68	58	7	4	9	2	3
5	3	7	2	89	89	1	6	4	5
6	469	4569	469	259	3569	236	7	1	8
7	24689	4689	1	258	3568	236	458	7	469
8	246789	4689	5	1278	168	26	148	3	1469
9	678	68	3	1578	4	9	158	68	2