transformed matrix

特性行列（ g- , candy matrix )は、単に候補の一覧表をまとめたもので、たまたま候補が一つであればそのまま解として求められました。これを基本技と呼びました。

　基本技で取りつくしたとき、さらに基本技が使えるようになるまで、特性行列を変換（tranform ）します。その方法は、unit　（block、row、columnの総称、buddy：相棒とも言います）間での拘束条件を見極めて、あり得ない候補を消去（eliminate）します。特性行列を作るときには、block、row、columnなど単独の拘束条件（1から9の数字が一つずつ入るというルール）は満足していますがunit間に潜む関係は必ずしも満たされているとは限りません。数字配列のランダム性の中に数字のunit間の関係する法則を見出します。

transformed matrix 作るには、まず関係するかどうかの条件を調べます。しかる後、その条件によって、あり得ない候補が消去されます。最後は、基本技によって、決定されます。

前回の問題の第12手目で具体的に見てみましょう。

右上のBlock3において、ピンクのセルの7は、二つしかない候補（ pair candidate ）で、しかも共に第7列にあります。Block　ルールにより、第7列において、このBlockのどちらかのセルに入るので、同列のBlock6、9の空白セルには入りません。Block3のピンクのセルの候補はそのままで、( (1,7)=2678, (2,8)=679 )　第7列の（5,7）、（8,7）のセルから7が消去され transformed matrix が出来上がります。

しかる後、基本技　R：レッツミーにより白色のセルが埋まります。

transformed　matrix作成では、「条件の探索」「消去」のステップを踏み、基本技で決めます。本図では、関係のあるものだけピックアップして書いていますが、実際には、条件を満足するものが多数あり、実際に消去するセルがない場合、また基本技で取れるものがない場合など、むしろそのケースの方が多いのです。　
　
この技は、VbｃR　と略記されます。Vb　はいづれにしても理論（Block)、ｃは列方向、Rは決め技です。

candy matrix で決める基本技

もう一つの基本技は、ある place（セル）に注目して、そこに入る 一つだけの数字（single number）を探す方法です。これは、候補の一覧表（candy matrix)を作ってやると、ハッキリと（Explicit）目につきます。

candy matrix は、次のように定義しています。
　　　　　　　　　can( i, 1) = place (cell)
                         can( i,2) = row
                         can ( i,3) = column
                         can ( i, 4) = block
                         can ( i, 5) = no of candidate
                         can ( i, 6) = first candidate
                         can( i , 5+n) = n-th candidate
ここに、i は空白セルの順番を表す番号です。

M （　Explicit（Naked) Single、マスミーなど）の技は、
　　　　　　　　　can( i,5) =1
を満たす空白セルです。

基本技は、number　place　の characteristic matrix (g- and candy matrix) だけで、一度に答えが求まるもので、4種類となります。ナンプレ本などでは、この Explicit single は、pencil work では、見つけにくいため基本技に含めない説明のものもありますが、解法のアルゴリズムの観点から構造的に分かりやすいので、ここでは　basic soluｔion method として4種類としています。


朝日新聞8月25日Be　夏休み数独特集第5問の「次の一手」です。

　

1   (1,9)= 1     B1   Block 3

2   (1,6)= 4     B1   Block 2

3   (8,8)= 4     B1   Block 9

4   (9,3)= 4     C1   Column 3　説明図

5   (1,4)= 8     M1   Cell (1,4)

6   (8,4)= 5     M1   Cell (8,4)

7   (3,4)= 3     M1   Cell (3,4)

8   (7,5)= 3     B2   Block 8

9   (9,1)= 3     B3   Block 7

10   (5,3)= 3     B4   Block 4

11   (6,7)= 3     B5   Block 6

12   (8,3)= 7     VbR            説明図

13   (8,5)= 2     R1   Row 8

14   (6,6)= 2     B2   Block 5

15   (4,9)= 2     B3   Block 6

16   (4,4)= 9     B3   Block 5

17   (5,7)= 5     B4   Block 6

18   (5,4)= 7     B4   Block 5

19   (6,1)= 9     B4   Block 4

20   (6,2)= 4     B5   Block 4

21   (4,5)= 5     B5   Block 5

22   (2,3)= 9     B5   Block 1

23   (3,1)= 4     B6   Block 1

24   (2,6)= 5     B6   Block 2

25   (2,5)= 1     B7   Block 2

26   (3,2)= 5     B7   Block 1

27   (5,6)= 1     B8   Block 5

28   (1,3)= 2     B8   Block 1

29   (7,1)= 5     B8   Block 7

30   (3,5)= 6     B8   Block 2

31   (4,2)= 1     B9   Block 4

32   (9,4)= 1     B9   Block 8

33   (3,7)= 2     B9   Block 3

34   (7,2)= 2     B9   Block 7

35   (9,9)= 5     B9   Block 9

36   (1,1)= 6     B9   Block 1

37   (6,5)= 8     B9   Block 5

38   (6,8)= 1     B10   Block 6

39   (2,7)= 6     B10   Block 3

40   (4,3)= 6     B10   Block 4

41   (2,2)= 7     B10   Block 1

42   (4,1)= 7     B10   Block 4

43   (7,3)= 8     B10   Block 7

44   (3,8)= 9     B10   Block 3

45   (5,8)= 6     B11   Block 6

46   (1,7)= 7     B11   Block 3

47   (6,9)= 7     B11   Block 6

48   (3,9)= 8     B11   Block 3

49   (5,2)= 8     B11   Block 4

50   (9,6)= 8     B11   Block 8

51   (9,7)= 9     B11   Block 9

52   (7,9)= 6     B12   Block 9

53   (7,8)= 7     B12   Block 9

54   (4,8)= 8     B12   Block 6

55   (8,7)= 8     B12   Block 9

56   (7,6)= 9     B12   Block 8

第四手目

第5手目　( 1, 4) = 8 が、今回述べたMの技できまります。上図をみて確認してください。また第5手の　8　が決まると、第6手、第7手とたて続けに、Mの技で決まります。　


第12手目

g-matrix で決める基本技

g-matrix は、数字 (number)のはいる 場所（place) の候補に関する3次元行列です、
　　　　　　　　　　　g (place,number,1)= place
                              g (place,number,2)=number of candidate
                              g (place,number,3)= first candidate
                              g (place,number, n+2)= n-th candidate
place は、3種類あり、block、row、column　をそれぞれ
　　　　　　　　　　　gg matrix, gr matrix, gc matrix
と名付けます。

number-place（ナンプレ、数独）の基本技の3つ（implicit single )は、g-matrix を使って次の条件を満たすものがあれば、決まります。

　B　　　　　　gg(block,number,2)=1         Implicit(Hidden) Single of Block    、ブロッケン
　R　　　　　　gr(row,number,2)=1            Implicit(Hidden) Single of Row      、レッツミー
　C　　　　　　gc(column,number,2)=1       Implicit(Hidden) Single of Column    、レッツミー

朝日新聞8月25日　Be　夏の数独特集の第４問を取り上げます。第一問★★、第二問★★★は、基本技　Bだけで解ける問題でした。これらの問題は、[Beginner]と呼んでいます。第三問★★★★および今回取り上げる第四問★★★★は、さらにR or/and C の技を必要とします。このLevel　2を「Very　Easy」と呼んでいます。

1   (1,3)= 1     B1   Block 1

2   (1,9)= 5     B1   Block 3

3   (4,5)= 6     B1   Block 5

4   (2,1)= 3     B2   Block 1

5   (3,6)= 7     R1   Row 3   　説明図

6   (3,5)= 5     B2   Block 2

7   (7,4)= 7     B2   Block 8

8   (9,6)= 5     B3   Block 8

9   (9,2)= 7     B3   Block 7

10   (9,1)= 2     B4   Block 7

11   (8,1)= 1     B5   Block 7

12   (5,2)= 2     B5   Block 4

13   (7,8)= 2     B5   Block 9

14   (2,7)= 2     B6   Block 3

15   (6,5)= 2     B6   Block 5

16   (5,1)= 5     B6   Block 4

17   (8,2)= 5     B6   Block 7

18   (1,4)= 2     B7   Block 2

19   (8,3)= 8     B7   Block 7

20   (1,5)= 3     B8   Block 2

21   (7,3)= 6     B8   Block 7

22   (8,4)= 3     B9   Block 8

23   (2,5)= 8     B9   Block 2

24   (2,6)= 4     B10   Block 2

25   (8,5)= 4     B10   Block 8

26   (3,2)= 4     B11   Block 1

27   (7,5)= 9     B11   Block 8

28   (9,5)= 1     B12   Block 8

29   (2,2)= 6     B12   Block 1

30   (7,9)= 1     B13   Block 9

31   (3,7)= 6     B13   Block 3

32   (1,2)= 9     B13   Block 1

33   (5,7)= 1     B14   Block 6

34   (3,1)= 8     B14   Block 1

35   (1,8)= 8     B14   Block 3

36   (4,1)= 9     B14   Block 4

37   (4,2)= 8     B15   Block 4

38   (9,7)= 8     B15   Block 9

39   (9,8)= 3     B16   Block 9

40   (5,4)= 8     B16   Block 5

41   (4,4)= 4     B17   Block 5

42   (6,9)= 8     B17   Block 6　　　二重枠

43   (6,8)= 7     B18   Block 6

44   (5,8)= 4     B19   Block 6

45   (2,9)= 7     B19   Block 3

46   (4,3)= 7     B19   Block 4

47   (6,3)= 4     B20   Block 4

48   (5,9)= 6     B20   Block 6

49   (2,8)= 9     B20   Block 3  　  二重枠

50   (5,3)= 3     B21   Block 4

51   (8,8)= 6     B21   Block 9

52   (6,7)= 9     B21   Block 6

53   (8,9)= 9     B21   Block 9

54   (6,6)= 3     B22   Block 5

55   (4,7)= 3     B22   Block 6

56   (5,6)= 9     B22   Block 5

第5手目は、三行目に注目下さい。Block 1 の 7、5 列目、7 列目の 7（空色で表示）の存在により、白色のセルには、R　Implicit（Hidden） Single の技を使って　7が決まります。このセルには、4、5、7の三つの候補があり、7の候補はむき出し(Naked)ではないので、隠れた（Hidden）Single と呼ばれる所以です。

 　

　　

g-matrix の発明

数独は number-place （ナンプレ）と呼ばれていたもので、1～9までの数字を、81のセルに、最初から与えられた数字（表出数、givens、ヒントとか言います）をヒントに残りの場所に数字を埋めるパズルです。解き方の基本は、数字を決めて場所を探す方法（B：ブロッケンとかR,C:マスミー）と場所を決めて数字を探す方法（M:マスミー）があります。

PCによる数独解析において、candy matrix は、候補の一覧表を表したもので、その場所に入る候補がハッキリと（Explicit）分かります。候補が一つだけしかないとき、Explicit Single ( Naked Single)と呼び、解が決定します。

ところが、鉛筆と消しゴムで解く場合（Pencil workといいます）、ある数字に狙いを定め場所を探します。つまり、場所（place）の一覧表を紙上で再現しているのです。

外国において、幾多の数独ソフトが開発されていますが、場所の一覧表（これをg-matrixと総称します）らしきものを使ったものは見かけません。その理由は、Variant変数により、g-matrixを作成する発想と表現法にたどり着くに至らなかったからでしょう。

g-matrixの発明とその応用により、数独のいろいろな技の数学的構造の説明と解法や「次の一手」の明快な表現が可能になりました。g-matrix発明にいたる経緯やそのアルゴリズムは昔のブログに詳しくかいてありますので、興味のある方は参照ください。
                                       http://numberplace.blogspot.jp/2009/09/45-vba.html


今回の次の一手は、朝日新聞8月25日夏の数独特集　第3問★★★★を取り上げます。

　Total　point　97　、　Technical  59
                                    Visual point   38  ( artistic  26,   creative  12 )

 Ranking   BBB－
 Level 　2　 Very Easy

1   (7,3)= 1     B1   Block 7

2   (2,4)= 3     B1   Block 2

3   (3,2)= 8     B1   Block 1

4   (7,8)= 8     B1   Block 9

5   (4,3)= 8     B2   Block 4

6   (8,4)= 8     B2   Block 8

7   (8,6)= 1     B3   Block 8

8   (6,5)= 8     B3   Block 5

9   (2,8)= 1     R1   Row 2     Fig. 1

10   (7,9)= 5     R1   Row 7    Fig. 2

11   (6,7)= 5     B2   Block 6

12   (9,7)= 6     B2   Block 9

13   (5,7)= 1     B3   Block 6

14   (4,6)= 5     B3   Block 5

15   (3,9)= 6     B3   Block 3

16   (6,4)= 1     B4   Block 5

17   (4,9)= 2     B4   Block 6

18   (1,4)= 5     B4   Block 2

19   (1,2)= 6     B4   Block 1

20   (1,8)= 9     B4   Block 3

21   (3,5)= 1     B5   Block 2

22   (2,3)= 5     B5   Block 1

23   (4,1)= 6     B5   Block 4

24   (2,9)= 7     B5   Block 3

25   (8,9)= 9     B5   Block 9

26   (5,2)= 3     B6   Block 4

27   (9,2)= 5     B6   Block 7

28   (4,8)= 3     B7   Block 6

29   (8,7)= 3     B8   Block 9

30   (5,8)= 7     B8   Block 6

31   (7,1)= 3     B9   Block 7

32   (6,9)= 4     B9   Block 6

33   (9,8)= 4     B9   Block 9

34   (4,5)= 7     B9   Block 5

35   (9,5)= 3     B10   Block 8

36   (5,3)= 4     B10   Block 4

37   (3,6)= 7     B10   Block 2

38   (9,3)= 9     B10   Block 7

39   (9,6)= 2     B11   Block 8

40   (1,3)= 7     B11   Block 1

41   (3,4)= 9     B11   Block 2

42   (6,1)= 9     B11   Block 4

43   (1,5)= 2     B12   Block 2

44   (6,2)= 7     B12   Block 4

45   (3,7)= 2     B13   Block 3

46   (5,4)= 2     B13   Block 5

47   (2,6)= 4     B13   Block 2

48   (8,1)= 7     B13   Block 7

49   (2,1)= 2     B14   Block 1

50   (3,1)= 4     B14   Block 1

51   (1,7)= 4     B14   Block 3

52   (8,2)= 4     B14   Block 7

53   (7,5)= 4     B14   Block 8

54   (5,6)= 6     B14   Block 5

55   (7,4)= 6     B15   Block 8

56   (5,5)= 9     B15   Block 5

57   (7,6)= 9     B15   Block 8

第9手目

第10手目

     
　　

数独解析はmatrixで。

行列（matrix）は19世紀中葉になって、英国のケーリーらによって発明された。コンピューター解析には不可欠なものであるので、日本では1973年（昭和48年）から高校数学に取り入れられ、高校3年の「数C」で学び、さらに大学では線形代数として履修する。ところが、昨年度（平成23年度）からの高校の指導要綱では、この行列が姿を消したという。（京極一樹著：中学・高校数学のほんとうの使い道）

数独は9×9の行列で表されるので、その解析には、matrix　計算や表現がふさわしい。数独解析ソフトの心臓部である　candy matrix　や　g-matrix　の理解は行列の知識が前提になっている。

また、（ i, j ) ,  Aij , can( i, j) などの表現は、マトリックス演算に使われているものを使用している。Excel　VBAでの表に対応する　matrix　では、(0,0)　や　( i , 0 ) 、( 0, j )を　問題番号、行や列の Indexとして使える。

朝日新聞8月25日号　Be 「夏の数独特集」第2問　★★★の「次の一手」の全手筋を示そう。

この問題は、B　（ブロッケン）だけで解ける問題です。

1   (8,8)= 1     B1   Block 9

2   (8,2)= 5     B1   Block 7

3   (6,9)= 6     B1   Block 6

4   (7,8)= 7     B1   Block 9

5   (1,1)= 8     B1   Block 1

6   (8,3)= 9     B1   Block 7

7   (4,1)= 5     B2   Block 4

8   (8,7)= 8     B2   Block 9

9   (7,9)= 9     B2   Block 9

10   (6,8)= 5     B3   Block 6

11   (9,4)= 8     B3   Block 8

12   (5,1)= 9     B3   Block 4

13   (1,9)= 5     B4   Block 3

14   (9,5)= 7     B4   Block 8

15   (2,5)= 5     B5   Block 2

16   (6,4)= 7     B5   Block 5

17   (5,2)= 7     B6   Block 4

18   (2,3)= 7     B7   Block 1

19   (1,7)= 7     B8   Block 3

20   (2,7)= 6     B9   Block 3

21   (3,2)= 6     B10   Block 1

22   (2,2)= 3     B11   Block 1

23   (2,1)= 1     B12   Block 1

24   (3,8)= 3     B12   Block 3

25   (9,3)= 3     B12   Block 7

26   (1,6)= 1     B13   Block 2

27   (9,2)= 1     B13   Block 7

28   (3,1)= 2     B13   Block 1

29   (5,9)= 3     B13   Block 6

30   (2,8)= 9     B13   Block 3

31   (6,3)= 1     B14   Block 4

32   (4,4)= 1     B14   Block 5

33   (1,8)= 2     B14   Block 3

34   (7,2)= 2     B14   Block 7

35   (1,5)= 6     B14   Block 2

36   (3,4)= 9     B14   Block 2

37   (4,7)= 9     B14   Block 6

38   (9,1)= 4     B15   Block 7

39   (8,6)= 6     B15   Block 8

40   (6,5)= 9     B15   Block 5

41   (8,5)= 3     B16   Block 8

42   (8,9)= 4     B16   Block 9

43   (8,4)= 2     B17   Block 8　　二重枠

44   (9,9)= 2     B17   Block 9

45   (4,6)= 3     B17   Block 5    二重枠

46   (7,6)= 4     B17   Block 8

47   (2,6)= 2     B18   Block 2

48   (4,5)= 2     B18   Block 5

49   (2,4)= 4     B18   Block 2

50   (6,6)= 8     B18   Block 5

51   (5,5)= 4     B19   Block 5

52   (4,2)= 8     B19   Block 4

53   (6,2)= 4     B20   Block 4

54   (4,8)= 4     B20   Block 6

55   (5,8)= 8     B20   Block 6