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

L search memorandam (2) Block select number

U search では、candy matrix ( Row vs Column ) から　Swordfish　に該当する　3 Pattern を見つけ出した。
L　search　や　T search　はこれに相当する　matrix　は、g_matrix　になる。
　すなわち、　Lb search　は　gb_matrix　（Block vs Number )
                       Lr search    は　gl_matrix   （ Row vs Number )
                       Lc search   は　gc_matrix    ( Column vs Number )
である。

L　search　の３種類の　chainr matrix を作成する。

 Select Case kind1
 Case "B"
 two_hidden_number_in_block
 Case "R"
 two_hidden_number_in_row
 Case "C"
 two_hidden_number_in_column
 Case Else
  MsgBox ("No place in hidden digit!")
 End Select

各Block　の候補の入っているセルの数を数えて　chainc　の右端　(z+1)列　に書き込む。
chainc　は　work　area　である。

   num = 0
 For kosu = 1 To z
  For i = 1 To z
 If chainr(i, z + 1) = kosu Then
   num = num + 1
   For j = 0 To z + 1
   chainc(num, j) = chainr(i, j)
   Next j
 End If
  Next i
 Next kosu

ひとまず、　chainr　に移す。

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

同様のことを　列（　Digit )　についても行う。

    num = 0
 For kosu = 1 To z
  For j = 1 To z
 If chainr(z + 1, j) = kosu Then
   num = num + 1
   For i = 0 To z + 1
      chainc(i, num) = chainr(i, j)
   Next i
 End If
  Next j
 Next kosu
 For i = 0 To z + 1
  For j = 1 To z
       chainr(i, j) = chainc(i, j)
  Next j
 Next i

Block 1（左上のブロック）の　gb-matrix　より　chairr　matrixを作る。

以上は　L search （　Hidden )　の場合であるが、T　search　の場合には、その転置行列を作成してそれを使う。

つまり、Hidden　の場合には、3つの部屋を占める3人を求めるのだが、Naked の場合には、3人が占める可能性がある3つの部屋を探すのである。

　　　　Lsearch　　Hidden　　（　Block,　Number　）
　　　　Tsearch　　Naked　　（　Number,　Block　）
　　　
 If kind = "naked" Then
 For i = 0 To z + 1
  For j = 0 To z + 1
       chainc(j, i) = chainr(i, j)
  Next j
 Next i
 For i = 0 To z + 1
  For j = 0 To z + 1
       chainr(i, j) = chainc(i, j)
  Next j
 Next i
 End If
 

L search memorandam (1)

Lsearch　は、「三国同盟」または「陰の三国同盟」と呼ばれる。または「定員確保」や「予約」などと呼ばれることがある。

L search は先に示した　U　search　と同じアルゴリズムを使って首尾よく求めることができる。U　search　は　Candy　matrix　を使って、Ur（行）　と　Uc(列）　の２種類があったが、L　search　はLb(ブロック）,　Lr(行）、　Lc（列）の３種類がある。そして、gb-、ｇｒ-　gc-　の3種類の　g_matrix　をcandy　matrixのかわりに使う。　T　search　も同じマクロを使い、殆んど同じアルゴリズムで求められる。

さらに、U　search　でみたように、room=2,3,4,5　は同じマクロで求められる。このあたりの関係や記号の扱いは、

http://kmatsu4.blogspot.jp/2012/11/u-search-memorandam-1.html

を参照されたい。

特に、Pencil　Work　の経験から開発された「定員確保」と「陰の定員確保」の技の名称は、PCを使った　Candidate　Table　（Candy　matrix）から来る　”　Hidden ”　と　”Naked　”のNaming　と逆の印象を与え、理解しにくい面があるので、注意を要します。

大雑把な説明をすると、３部屋に特定の３人しか入れないのに、それ以外の予約客が紛れ込んでいて（特定客が隠れた状態になっている）その部屋から追い出す（消去する）のが、Hidden　Triple　という技で、単に「三国同盟」とか「定員確定」とか呼ばれています。
　また、3部屋宛に特定の三人で予約が決まっていて、ハッキリと裸の状態にあるのに、他の部屋にも、Double　Booking　されているので、その予約を取り消す（消去する）というのが、Naked　Triple　という技です。

”Ryuzen”ソフトでは、数学用語により、　Explicit　=  Naked ,    Implicit = Hidden を使っています。

 L ( Implicit Triples ) を例にとり、search　flow を説明しよう。　

①　L_search ( M45, 5 )
              > Lb_search    ( M45, 8)
              > Lr_search    ( M45, 9)
              > Lc_search    ( M45, 10)

②　Lb_search >  hot_candy
                           Vb_Vr_Vc
                           Qb_Qr\Qc
                           Gb_Gr_Gc
                           deform_Lb     ( M46,10)  
                           scf
                           Bcf

③　deform_Lb
                      room=3
                      hidden_block_basic_deform  

④　hidden_block_basic_deform  ( M46,  4)
                      basic_setting
             　　　kind = "hidden"
　　　          　kind1 = "B"
　　          　　flagM = kind & kind1 & room
        For igrp=1 to z
                     empty_cell_in_block  (M46, 1)
                     block_select_menber  ( M46, 11)
                      column_block_judge ( M46,111 )
        Next igrp

⑤　deform_Lr
                      room=3
                      hidden_row_basic_deform  

⑥　hidden_row_basic_deform  
　　　　　　basic_setting
　　　　　kind = "row"
　　　　　kind1 = "R"
　　　　　flagM = kind & kind1 & room

　　　　For ilin = 1 To z
　　　　　row_select_number
　　　　　column_row_judge
　　　　Next illin

⑦　deform_Lc
                       room=3
                      hidden_column_basic_deform 

⑧　 hidden_column_basic_deform  
　　　　　　basic_setting
　　　　　kind = "collumn"
　　　　　kind1 = "C"
　　　　　flagM = kind & kind1 & room

　　　　For ilin = 1 To z
　　　　　row_select_number
　　　　　column_row_judge
　　　　Next illin

　To be continue :