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 :
        

U search memoramdum (9) Example of Swordfish

Swordfish の実例として、「世界で一番美しくて難しいナンプレ　４」より　78番の問題を取り上げます。

　　　　
　　　　　　　　　　　　　Rank　　AA－　　Level 17　　Beetle　　Published Level 　Devillish
　　　　　　　　　　　　　
　　　　　　　　　　　　　Total point　150　、　Technical　82、　Visual　　68

Final answer

Order　and Strategy

　

この問題では、基本技の他に使う上級技は、15手目に表れる　Swordfish　が一回だけです。

14手目が終わった段階で、盤面はこのようになっています。

この次の一手が問題です。一応、Candy matrix を示しておきますが、これでもどこがどうなっているのかが見当もつきません。

7の候補に注目します。

Sword fish(R) は、2行目、4行目、9行目にある白いセルのPair　が構成します。結果として、2列目、5列目、9列目では白いセル以外では7の候補はもちません。

同様に9の数字に注目します。

これも、7の場合と同様に、 (2,2,2) 型の　Swordfish(R)　が成立しています。

これらを考慮して、7と9の候補の消去をします。下の赤いセルのようになり、(5,2)=2　のsingle candidate があぶり出されます。

　　
　

U search memoramdum (8) column_fish_room_division

jnn matrix のすべての組み合わせに対して、room_selection マクロにてswordfish として成立する組み合わせを選別して次のマクロに入る。
選別されたmatrixの形は、 ( f(i), d(j) ) で表される。

 column_fish_room_divisionマクロ

該当するswordfish　の組み合わせをOUTPUTする。

  cnum = 19 + i6

Sheets("Sheet8").Cells(19, 54) = "number/room"
'
Sheets("Sheet8").Cells(cnum, 51) = Sheets("Sheet1").Range("D2")
Sheets("Sheet8").Cells(cnum, 52) = flagM
Sheets("Sheet8").Cells(cnum, 54) = nb & " ( " & room & ")"
 aa = ""
For i7 = 1 To room
 d(i7) = jnn(0, i7)
 aa = aa & jnn(0, i7)
Next i7
Sheets("Sheet8").Cells(cnum, 53) = aa

 knum = 0
 For i8 = 1 To z
  If jnn(i8, room + 1) <> 0 Then
  knum = knum + 1
  f(knum) = jnn(i8, 0)
Sheets("Sheet8").Cells(cnum, 54 + knum) = jnn(i8, 0)
  End If
Next i8
'
candy matrix より、swordfish を構成する候補数字を消去する。

empty_cell = Sheets("Sheet1").Range("K2")
For i6 = 1 To knum
If Left(f(i6), 1) = "C" Then
    x2 = Int(Right(f(i6), 1))
   For i7 = 1 To empty_cell
  
      For j8 = 1 To knum
       x1 = Int(Right(d(j8), 1))
    If can(i7, 2) = x1 Then GoTo conti77
      Next j8
  
    If can(i7, 3) = x2 Then
     ikumi = can(i7, 5)
            For j3 = 1 To ikumi
              If nb = can(i7, 5 + j3) Then
                 For k1 = j3 To ikumi
                 can(i7, 5 + k1) = can(i7, 6 + k1)
                 Next k1
                can(i7, 5) = ikumi - 1
                can(i7, 5 + ikumi) = ""
                Exit For
              End If
            Next j3
      End If
conti77:
   Next i7
ElseIf Left(f(i6), 1) = "R" Then
    x1 = Int(Right(f(i6), 1))
   
   For i7 = 1 To empty_cell
      For j8 = 1 To knum
       x2 = Int(Right(d(j8), 1))
    If can(i7, 3) = x2 Then GoTo conti7
      Next j8
    If can(i7, 2) = x1 Then
     ikumi = can(i7, 5)
            For j3 = 1 To ikumi
              If nb = can(i7, 5 + j3) Then
                 For k1 = j3 To ikumi
                 can(i7, 5 + k1) = can(i7, 6 + k1)
                Next k1
                can(i7, 5) = ikumi - 1
                can(i7, 5 + ikumi) = ""
                Exit For
              End If
            Next j3
      End If
conti7:
   Next i7
End If
Next i6

U search memoramdum (7) column_swordfish

chainr  matrix より縮小したjun　matrix が作成された。次のステップとして、room　に応じたmatrixの形式を選別する。例えば、swordfish は、room=3　であるが、3行でswordfishを構成するにはroomより少ない候補を持つセルでも成立する。
(2,2,2) (2,2,3) (2,3,3) (3,3,3) などである。ここで、列・行を候補の数が少ない順にわざわざ並べ替えた意味がわかるだろう。room=3の場合には、上に示した4つのケースに絞られる。

jun　matrix より、room_selection マクロにより、swordfish に該当するmatrix が　jnn　matrixとして、導かれる。

column_swordfish は、jun matrix より、次のようにあらゆる組み合わせを検定して、抽出する。　
'
Sub column_swordfish()
 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

　　　   room_selection

    Next k9
  Next j9
Next i9
End Sub

ある組み合わせが該当するかどうかを調べる。
 Sub room_selection()

各行に対して候補を持つセルの数を調べて　jnn　の　room+1列目に書き込む。
       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

該当する行の数を jnn　matrix　の右下のセル (z+1,room+1)にかきこむ。
         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

判定条件は、この数が、room　に一致することである。

     If knum > room Then
      Exit Sub
     ElseIf knum = room Then

該当する　jnn matrix をoutput　する。
       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

jnn matrix(z+1, room+1)  の output は次のようになります。

そして、つぎのマクロで、この同列にあるこの行の候補数字を消去する。

       column_fish_room_division

     Else
      MsgBox ("Qurious Case to be noticed !")
      Exit Sub
     End If
   End Sub
'