2013年6月10日月曜日

U search memoramdum (9) Example of Swordfish

Swordfish の実例として、「世界で一番美しくて難しいナンプレ 4」より 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 があぶり出されます。


  
 

2013年6月5日水曜日

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
'

2013年6月4日火曜日

U search memoramdum (6) column_fish_judge

 ある数字(nb)に注目し、各行、各列にある候補の数を拡大matrix chainb に作成し、work area の chainc を使って、候補の数が少ない順に、行・列を並び替えた chainr matrix を作成しました。

room=3 は、関係するセルの数です。それ以上のものは関係なく取り除きます。新しく関係するセルだけを含む matrix jun を作成します。
'
Sub column_fish_judge()
  Erase chainc
 ReDim chainc(z + 1, z + 1)

chainr の最下行にある候補の数を調べて、room より多いのは省きます。
work area の chainc に借り置きします。

roomより少ない列がnumある。


 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

jun  jnn matrix 登場。
Erase jun, jnn
 ReDim jun(z + 1, z + 1), jnn(z + 1, z + 1)

先に作った絞り込み Matrix を jun に移す。

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

絞り込んだ列の数(roomより少ない関係する列)を 左下のセル(z+1,0)=num
に書き込む。

 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

room国同盟に足りない場合はおさらば。
三国同盟をするのに二国しか該当しない。

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

room に応じて次のマクロに分かれる。

Select Case room
Case 2
 column_X_wing
Case 3
 column_swordfish
Case 4
 column_jellyfish
Case 5
 column_squirmbag
Case Else
 MsgBox ("This case available ! ")
End Select


2013年6月3日月曜日

U search memoramdum (5) select_number

 Select_number は3部屋を占有する組み合わせを求め易くするための、chainr matrixを作るマクロである。

chainb はCandy matrix を拡大したもので、次のサイズを持つ。

ReDim chainb(z + 1, z + 1), chainr(z + 1, z + 1)

z=9 、chainb(0,z+1),  (z+1,0) は、タイトル、(i,z+1),(z+1,j) は候補の数が入る。

matrixを空にする。   Erase chainb, chainr

chainb を作成する。  画面を chainb に移す。
 For i = 1 To z
  For j = 1 To z
   chainb(i, j) = Sheets("Sheet1").Cells(ppp + i, qqq + j)
  Next j
 Next i

 空白セルの候補を、 chainb に書き込む。
 For i = 1 To empty_cell
    ikumi = can(i, 5)
     i1 = can(i, 2): j1 = can(i, 3)
     candidate = ""
       For k = 1 To ikumi
     candidate = candidate & can(i, 5 + k)
       Next k
  chainb(i1, j1) = candidate
 Next i 

chainb の上に、C1,C2・・・ 左端に R1,R2,R3・・・を書き込む。
  For j = 1 To z
 chainb(0, j) = "C" & j
 chainb(j, 0) = "R" & j
  Next j

chainr の作成 chainbより、現在対象としている digit nb を抜き出す。
chainr は特定の候補に絞ったmatrix

For i = 1 To z
 For j = 1 To z
  k = Len(chainb(i, j))
 If k <> 1 Then
  For m = 1 To k
    If Int(Mid(chainb(i, j), m, 1)) = nb Then
    chainr(i, j) = nb
    End If
   Next m
 End If
 Next j
Next i

chainr にタイトルをつける。
For j = 1 To z
 chainr(0, j) = "C" & j
 chainr(j, 0) = "R" & j
Next j 

各行について、nbの数を持つセルの数を数えて、chainr(i,z+1) 一番右端に書き込む。

For i = 1 To z        'row i no kosuu
 num = 0
For j = 1 To z
If chainr(i, j) <> "" Then
num = num + 1
End If
Next j
 chainr(i, z + 1) = num
Next i

各列に対して、同様にセルの数を数えて、chainr (z+1, j) 一番下に書き込む。

For j = 1 To z         'column j no kosuu
 num = 0
For i = 1 To z
If chainr(i, j) <> "" Then
num = num + 1
End If
Next i
 chainr(z + 1, j) = num
Next j

chainr matrix はこのようになる。(Examle U-78 nb=7)


chainc の登場。
chainrを列、行を並び替えて、arranged matrix chainc を作成する。

 Erase chainc
 ReDim chainc(z + 1, z + 1)

行の並び替え。1,2,3、の順に候補の数が少ない順に上からchainc に書き込む。

   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 に戻す。
chaincは単なるwork area である。
 For i = 1 To z
  For j = 0 To z + 1
     chainr(i, j) = chainc(i, j)
  Next j
 Next i

同じことを、列に対して行う。

 Erase chainc
 ReDim chainc(z + 1, z + 1)
    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

列を並び替えた結果をchainc  から chainr に戻す。

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

kind="column"の場合にはこのまま終わる。




kind="row"の場合には chainr の転置行列にする。

 If kind = "row" 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



2013年5月19日日曜日

U search memoramdum (4) U_search

ここに、Usearch を例にとりメモとして残そうと企てる理由は3つある。

 一つは、本来の目的のそのアルゴリズムを今一度思い出し、メモとして書き記すためである。何しろプログラムを書いてから2年以上もたつというのに、そのプログラム本体以外に何もメモが残っていないからである。当時の記憶はだんだんと薄れていき、自分で書いたプログラムなのに、その意味が分からなくなってしまっている。ただそんなに詳しくは書くつもりはない。あくまでも私に対するメモで、他人にもすぐに理解できるような代物を目指したものではない。

 二つ目は、「次の一手」を説明できるようなコメントの部分を追加することにある。今の状態は答えは出てくるものの何故そうなるのかという情報のアウトプットがされていない。

 三つ目は、このルーチンのアルゴリズムを使って、拡張した探索法を見つけることである。実際、三次以上の Finned fish や Sasimi Fish などの技は今のアルゴリズムには含まれていない。そしてまた多重Chain や多重Loop といったものへの発展が期待される可能性の探査も含んでいる。

 U ( Sword fish) を例にとり、search flow を説明しよう。 

① U_search ( M45, 5 )
              > Ur_search    ( M45, 6)
              > Uc_search    ( M45, 7)

② Ur_search >  hot_candy
                           deform_Ur     ( M45,10)  
                           scf
                           Bcf

③ deform_Ur
                      room=3
                      row_fish_basic_deform  

④ row_fish_basic_deform  ( M45,  1)
                      basic_setting

    kind = "row"
    kind1 = "R"
    flagM = "fish" & kind1 & room

        For nb=1 to z
                      select_menber  ( M44, 1)
                      column_fish_judge ( M45 )
        Next nb

⑤ deform_Uc
                      room=3
                      column_fish_basic_deform  

⑥ column_fish_basic_deform  
      basic_setting
     kind = "column"
     kind1 = "C"
     flagM = "fish" & kind1 & room

    For nb = 1 To z
     select_number
     column_fish_judge
    Next nb

 To be continue
        

 

U search memorandum (3) search_type_choice

  ippatsu (M4) でまず、基本技の探索を search_process_choice (M4) で行う。基本技だけで決まる、Beginner, Very Easy,  Easy のレベルの問題はここで終了する。

次に、 > search_type_choice ( M4) において、技の種類別に次の macro に分かれる。

① search_macro (M41)         VQGP・・・・などの単独技
② combine_macro ( M41)      v w q g  ・・・などの組み合わせ技
③ playback_macro
④ A_birdy_search ( M4)       "?"
⑤ A_eargle_search ( M4)      "#"
⑥  Deform_candidate_search   "e"
⑦ destroy_macro                  "d"
⑧ extra_input_from_database  ( M4)  X
 
①の search_macro はそれぞれの記号別に次に示す具体的な search macro にうつる。
'
Sub search_macro()
 Range("AW1") = "search"
Select Case md(si5)
Case "V": V_search          '          M23
Case "W": W_search        '          M15
Case "Λ": Λ_search         '          M26
Case "Q": Q_search         '          M17
Case "G": G_search          '          M16
Case "P": P_search           '          M18
Case "Φ": Φ_search          '          M18
Case "K": K_search         '          M40
Case "S": S_search           '          M21
Case "Ξ": Ξ_search          '          M18
Case "Δ": Δ_search          '          M33
Case "H": H_search         '          M22
Case "Ω": Ω_search        '          M22
Case "Y": Y_search        '          M25
Case "Π": Π_search        '          M26
Case "Θ": Θ_search       '          M26
Case "L": L_search        '          M47
Case "T": T_search        '          M47
Case "U": U_search       '          M45
Case "N": N_search       '          M47
Case "O": O_search       '          M47
Case "J": J_search          '          M45
Case "F": F_seach         '          M47
Case "Z": Z_search       '          M47
Case "I": I_search         '          M45
Case "Γ": Γ_search       '          M33
'Case "?": Bcf               '          M41
 Case Else
     MsgBox ("No search name appear !  ")
 End Select
End Sub
'