L-search memorandam (9) Example of Lc-search(2)

room=3 （三国同盟のように、3つのセルと3つの数字が関係する技）の場合、マクロを共有します。

            Strategy                Notation       Used  matrix & Coordinate          Used matrix

　Implicit Triple （ Block )　　Lb         Place (Block , Number )       　     gg_matrix ( gb-matrix)
　Implicit Triple （ Row   )　　Lr         Place  (Row   , Number )       　     gr_matrix (gl-matrix )
　Implicit Triple （ Column )　Lc         Place  (Number , Column )       　   gc_matrix

  Explicit Triple  ( Block )      Tb        Place  ( Number , Block )           Transposed matrix of gg_matrix
  Explicit Triple  ( Row  )       Tr        Place  ( Number , Row )             Transposed matrix of gr_matrix
  Explicit Triple   ( Column )   Tc       Place  ( Column , Number )         Transposed matrix of gc_matrix

  Swordfish   ( Row )              Ur      Number ( Row , Column )            Candy_matrix
  Swordfish  ( Column )           Uc      Number ( Column, Row )           Transposed_matrix of candy_matrix

　where,  Implicit means term of  "Hidden" and Explicit means that of "Naked" respectively.

今回の実例の場合、Lc（Implicit Triple　of Column ）で初めて当てはまるケースが見つかります。探索には、gc-matrix　を使います。

先に示した　candy matrix より、gc-matrix を作成します。

                                          Fig 1   gc-matrix converted from candy matrix

黄色のセルは、3国同盟を形成する第7列目にある3つに部屋　cdh　でそこに　379　の数字の候補が入ります。candy matrix では、他の候補とまぎれた”hidden”の状態ですが、この gc-matrix では、”naked”　の状態になります。

ここに、念のため記しておきますが、部屋の呼び名は、それぞれの列で、上から順にa,b,c,・・となります。

Fig. 2   Notation of each place at column 7

Lc_search　に入ると、一列目（icol=1）から順に三国同盟が成立するかを調べていきます。

第7列になったときのgc-matrix　より作成した　chainr-matrix　は次のようになっています。

Fig.3 Candidates of place for each number

第7列目で、候補の数字を持つ場所(Place)がmatrixの値となります。

Step 1 の candy matrix で、上の表の意味を確認下さい。

右端および下端の数は、placeおよびnumber　の候補の数です。chainr-matrix (Fig.3)からColumn　7ですでに決まった数字を持つ3つの場所を除き、候補の数が少ない順に列および行を並べ変えます。

　　　　　　　　　　　Fig.4　　Aranged　chainr-matrix
さらに、三国同盟（room=3）を形成するのは、knum<=room つまり候補の数が3以下の場合なのでそれ以上の候補を持つ行、列を除きます。

Fig. 5　Condensed chainr-matrix　called　as　jun-matrix

　さらに、該当する行と列だけに絞り込みます。

Fig.5 　Rearanged　jnn-matrix

最終的に三国同盟を形成する3つの数字が入る3つのセルがもとまりました。

Fig.6　Implicit　Triple　derived  from gc-matrix of column 7

Lc-search では、C7-c, -d, -h の3つのセルは、379で占有されるので、それ以外の候補の数字があれば、これらのセルから消去されます。

その結果として、これらのセル以外の場所で、これらの数字以外候補が基本技で決まる（場合がある）ことになります。

何と言っても、このアルゴリズムの凄いところは、三国同盟を形成する候補の組み合わせを全て一つのマクロでカバーしていることです。

L search memorandam (8) Example of Lc-search

Lc-search （ Implicit Triple of Column,  三国同盟）のわかりやすい例として、「ナンプレ超上級編30」の３１番の問題を取り上げます。

　　　　　　　　　　　「ナンプレ超上級編30」031番　☆☆☆☆☆☆　作・西山ゆかり

この問題は、第一手目がいきなり、Lc （Implicit Triple of Column ）の技を使います。それ以降はすべて基本技で取れるという L-search の練習のような 問題です。

　ここでは、”Ryuzen”　ソフトが如何にして、第一手　(8,4)=6　LcR　を見つけだすかを説明します。

最初に第1手の　Candy matrix を示しておきます。

　　　　　　　　　
Pencil Player の場合には、熟練の勘で、これらの候補の中から　第7列（C7)において　379が3つのセルを独占する（三国同盟）のを見つけます。

379　の候補だけのCandy matrix は次のようになっています。ここで、379の数字が3つのセルだけにしか表れないというのがポイントです。第1行や第4行でも379で占める3つのセルが存在しますが、他のセルにも3や7や9が存在するので三国同盟にはなり得ません。

これさえ見つければ、あとは簡単で、第一手は次のようになります。

ピンクのセルの三国同盟で、 (8,7) のセルには、39　しか入らないので、8行目において、6が入るのは、白いセルの（8,4）=6　となります。

最終結果と決まる順番です。

　　　　　　　　　　　　　　　　　Final Answer

                                       Order and used strategy


それでは、”Ryuzen”　ソフトでは、如何にしてこの379の三国同盟を見つけ出すのでしょうか？

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　To be continue

L search memorandam (7) Example of Lb-search

L-search の例として、「超難問ナンプレAAA4」に掲載の次の問題を取り上げます。

                                              Original Puzzle :  AAA4-No.63 by Trickmachin


最終結果および決定順序と使用する技はつぎのようなものです。

                                        Final Answer : Blue cells mean determined value be Hidden Triple

                                           Small font blue number shows determined order
                                           and color of cells indicate used strategy such as
                                                White cell  :  Hidden Single of Block
               

さまざまな技が出てきますが、L-search が関係するのは、赤色のセルの値です。

解は次のような順に決まっていきます。

第6手目で、初めて　Lb ( Implicit Triple of Block )の技を使います。

第5手目までの盤面です。

この段階で、第6手目が　( 2, 3) = 8 であると言われても、どうして　(1,2)　に　8　が入り得ないのか皆目見当もつきません。

とりあえず　Candy matrix を示すと次の図になります。

　Block 1 に注目して下さい。　gg-matrix　を示すと次のようになります。

Block 1　は一行目に相当します。Block　1　の 9 つの部屋（ abcdefjhi ）の内、abd の3つの部屋は、数字　123で独占されることが分かります。

Candy　matrix　で　123　だけの候補を示せばもっとよくわかります。

Block 1 において、3つのセル( 1, 1) ( 1, 2) ( 2, 1) が  1, 2, 3 で占有されます。前に示した
Candy　matrix　では、他の候補とまぎれて（隠れて、hidden）見つけにくかった候補の123もくっきりと浮かび上がります。

Implicit Triple　の技は、この3つのセルから、123以外の候補を追い出す（消去する）ことです。
その結果、(1,2)のセルから　458　が消去され、Block　1において、(3,2)=8　が　Single　candidate　（ブロッケン）となります。

Implicit Triple of　Block  ( Lb ) で見つけ、Implicit　Sigle　（B)　で決めるので、　LbB と書き表します。 　

L search memorandam (6) column_block_room_division

Sub column_block_room_division()

Select Case kind1
Case "B"
Sheets("Sheet8").Cells(cnum, 54) = "B" & igrp & " ( " & room & ")"
Case "R"
Sheets("Sheet8").Cells(cnum, 54) = "R" & ilin & " ( " & room & ")"
Case "C"
Sheets("Sheet8").Cells(cnum, 54) = "C" & icol & " ( " & room & ")"
End Select
 aa = ""
For i7 = 1 To room
 d(i7) = jnn(0, i7)
 aa = aa & jnn(0, i7)
Next i7

If kind = "hidden" Then
  For i5 = 1 To room
   fd(0, i5) = Int(Right(d(i5), 1))
  Next i5
 
ElseIf kind = "naked" Then
  For i5 = 1 To room
   fd(0, i5) = d(i5)
  Next i5
End If

 knum = 0
 For i8 = 1 To z
  If jnn(i8, room + 1) <> 0 Then
  knum = knum + 1
  f(knum) = jnn(i8, 0)
 
   For i9 = 0 To room
   fd(knum, i9) = jnn(i8, i9)
   Next i9
  End If
Next i8


If kind = "hidden" Then
num = 0      'exchange column
For kazu = 1 To z
  For j1 = 1 To room
   If Int(Right(d(j1), 1)) = kazu Then
   num = num + 1
       For i1 = 0 To knum
       df(i1, num) = fd(i1, j1)
       Next i1
   End If
  Next j1
Next kazu

For i1 = 0 To knum
 For j1 = 1 To room
 fd(i1, j1) = df(i1, j1)
 Next j1
Next i1
End If

Lsearch(hidden)　と　Tsearch(naked)に分けて、fd-matrix（condenced allay matrix）またはdf matrix を作成する。（上の例は、hidden）
If kind = "hidden" Then
 
 For i7 = 1 To empty_cell
  For i6 = 1 To room
    If can(i7, 1) = f(i6) Then
          ikumi = can(i7, 5)
     For i8 = 1 To ikumi
      can(i7, 5 + i8) = ""
     Next i8
         num = 0
        For k1 = 1 To room
         If fd(i6, k1) <> "" Then
         num = num + 1
          can(i7, 5 + num) = fd(0, k1)
          can(i7, 5) = num
         End If
        Next k1
      End If
  Next i6
 Next i7

ElseIf kind = "naked" Then
   For i6 = 1 To room
    x1 = Int(Right(fd(i6, 0), 1))
  
   For i7 = 1 To empty_cell
      For i4 = 1 To room
      If can(i7, 1) = d(i4) Then GoTo conti7
      Next i4
 
      For j8 = 1 To knum
        iii = Int(Mid(d(j8), 2, 1))
        jjj = Int(Mid(d(j8), 4, 1))
       Select Case kind1
      Case "B"
        group_search
    If can(i7, 4) = grp Then GoTo conttrue
      Case "R"
    If can(i7, 2) = iii Then GoTo conttrue
      Case "C"
    If can(i7, 3) = jjj Then GoTo conttrue
      Case Else
       MsgBox ("no unit !"):    Exit Sub
      End Select
      Next j8
GoTo conti7
conttrue:

candy-matrix よりありえない候補を消去する。

         ikumi = can(i7, 5)
            For j3 = 1 To ikumi
              If can(i7, 5 + j3) = x1 Then
                 For k1 = j3 To ikumi
                 can(i7, 5 + k1) = can(i7, 6 + k1)
                Next k1
               End If
            Next j3
conti7:
   Next i7
   Next i6
End If

L search memorandam (5) column_triple_ally

jnn(z+1,room+1) matrix より、jun(room+1,room+1) に縮小する。

'
Sub column_triple_ally()
 flagL = ""
 ksum = jun(z + 1, 0)
For i9 = 1 To ksum
 For j9 = i9 + 1 To ksum
  For k9 = j9 + 1 To ksum
    For m = 0 To z + 1
    jnn(m, 0) = jun(m, 0)
    jnn(m, 1) = jun(m, i9)
    jnn(m, 2) = jun(m, j9)
    jnn(m, 3) = jun(m, k9)
    Next m

   ally_room_selection

  If flagL <> "" Then Exit Sub
    Next k9
  Next j9
Next i9
End Sub


'
 Sub ally_room_selection()
      For i5 = 0 To z + 1
      For j5 = 0 To z + 1
'     Sheets("Sheet8").Cells(6 + i5, 52 + j5) = jun(i5, j5)
     Sheets("Sheet8").Cells(6 + i5, 52 + j5) = jnn(i5, j5)
      Next j5
      Next i5
 
       For i3 = 1 To z
          inum = 0
        For j3 = 1 To room
          If jnn(i3, j3) <> "" Then
           inum = inum + 1
          End If
        Next j3
           jnn(i3, room + 1) = inum
        Next i3
         knum = 0
        For i4 = 1 To z
         If jnn(i4, room + 1) <> 0 Then
           knum = knum + 1
         End If
        Next i4
         jnn(z + 1, room + 1) = knum
     If knum > room Then
      Exit Sub
     ElseIf knum = room Then
       For i5 = 0 To z + 1
        For j5 = 0 To room + 1
          Sheets("Sheet8").Cells(6 + i5, 63 + room + j5) = jnn(i5, j5)
       Next j5
        Next i5
       
       column_block_room_division
     Else
'      MsgBox ("Qurious Case to be noticed !")
      Exit Sub
     End If
   End Sub

L search memorandam (4) column_block_judge

chainr　matrix　の各列の候補の数によって該当する行列に縮小する。
chainc　は　work　area　である。

Sub column_block_judge()
 Erase chainc
 ReDim chainc(z + 1, z + 1)
 num = 0
 For j = 1 To z
     aa = chainr(z + 1, j)
  If aa = "" Or aa = 1 Then GoTo contj
  If aa <= room Then
   num = num + 1
   For k = 0 To z + 1
   chainc(k, num) = chainr(k, num)
   Next k
  End If
contj:
 Next j

 For i = 0 To z + 1
   chainc(i, 0) = chainr(i, 0)
 Next i

Erase jun, jnn
 ReDim jun(z + 1, z + 1), jnn(z + 1, z + 1)
For i = 0 To z + 1
 For j = 0 To z + 1
 jun(i, j) = chainc(i, j)
  Sheets("Sheet8").Cells(6 + i, 40 + j) = jun(i, j)
 Next j
Next i
 num = 0
For j = 1 To z
If jun(z + 1, j) <> "" Then
 num = num + 1
End If
Next j
 chainc(z + 1, 0) = num
 jun(z + 1, 0) = num
If jun(z + 1, 0) < room Then
Exit Sub
End If
For i = 1 To z
 inum = 0
 For j = 1 To z
 If jun(i, j) <> "" Then
   inum = inum + 1
 End If
 Next j
 jun(i, z + 1) = inum
 chainc(i, z + 1) = inum
Next i
 For i = 0 To z + 1
  For j = 0 To z + 1
  Sheets("Sheet8").Cells(6 + i, 40 + j) = jun(i, j)
  Next j
 Next i

flagM = kind & kind1 & room
flagL = ""

room　に応じて振り分ける。

Select Case room
Case 2
 column_double_ally
Case 3
 column_triple_ally
Case 4
 column_fourth_ally
Case 5
 column_fifth_ally
Case Else
 MsgBox ("This case available ! ")
End Select
End Sub

L search memorandam (3) Two_hidden_number_in_block

Lb_search の　chainr　matrix　を整える。
chainr　matrix　の　行は　Block番号（左上から右下まで　B1からB9）　列は　Digit（　1から9）である。Matrixの値は、候補の存在するセルの場所である。

chainr　を作成するとともに、Sheet8　にoutput　する。

   Sheets("Sheet8").Cells(6, 28) = "Place"

 For j = 1 To z
   Sheets("Sheet8").Cells(5, 30) = "Chainr Matrix"
   zzz = j
 place_from_number
  
 For iii = 1 To z
  For jjj = 1 To z
        group_search
        banti = 3 * (iii - igs) + (jjj - jgs) + 1
  If banti = zzz And igrp = grp Then
     cc = "(" & iii & "," & jjj & ")"
   Sheets("Sheet8").Cells(6 + j, 28) = cc
    chainr(j, 0) = cc
    GoTo contj:
  End If
  Next jjj
 Next iii
contj:
   chainr(0, j) = "n" & j
'   chainr(j, 0) = "B" & igrp & "-" & cc
 Next j

候補の場所の数を数えて、chainr　の最下行(z+1)に記入する。 

For numb = 1 To z
    num = 0
    ikumi = gg(igrp, numb, 2)
    num = num + 1
    For k = 1 To ikumi
     cc = gg(igrp, numb, 2 + k)
     row_column_number
     iii = aa: jjj = bb
     group_search
     banti = 3 * (iii - igs) + (jjj - jgs) + 1
     Sheets("Sheet8").Cells(6 + banti, 28 + numb) = cc
     chainr(banti, numb) = cc
    Next k
    Sheets("Sheet8").Cells(6 + 10, 28 + numb) = ikumi
     chainr(z + 1, numb) = ikumi
  Next numb
 
  num_within_row