U search memorandam(2) Search Order

技の種類は多岐にわたり、その探索する順番は数え切れない。しかし今現在、使っているのは、次の123種の連続技である。

 msd1 = "WVΛQGPΦΔKSΞHΩYVΛQGPΔKSΞHΩYvwqgpφksξhωvVqQgGpPφPξkKsShHΩωLTUltulΓLtTuUVQGPΦΔKSHYΠΘΩvqgpφksξhω
NJOnNjJoOFIZfiznojLTUNJOFIZfizA"

この中には、基本技は含まれていない。基本技は、
　　　fmsd　= "BRCM"
として、最初にこの順で検索される。

Level 3 ( Beginner, Very Easy , Easy ) までは、この fmsd だけでもとまる。

上記の連続技の探索の順番では、58番目から、一連の　　U-search　が始まる。大文字は単独技、小文字は複合技を表す。

U-search memorandam (1)

周りを整理していたら、U-search　に関するメモ書きが出てきたので、そのアルゴリズムを書き残しておこうとおもう。

U-searchは、龍涎ソフトの重要な技の一つであり、このマクロにより、次の上級技をすべて、カバーしている。

  1.　　　L           Lb ,   Lr ,  Lc       Hiden Triple         三国同盟
  2.        N          Nb,   Nr ,  Nc       Hiden  Forth        四国同盟
  3.        F           Fb ,   Fr ,  Fc        Hiden  Fifth          五国同盟　　
  4.　　　T           Tb ,   Tr ,  Tc       Naked Triple         陰の三国同盟
  5.        O          Ob,   Or ,  Oc       Naked  Forth        陰の四国同盟
  6.        Z           Zb ,   Zr ,  Zc        Naked  Fifth          陰の五国同盟
  7.        U           Ur ,    Uc              Swordfish
  8.        J             Jr ,     Jc               Jellyfish
  9.        I             Ir ,     Ic                Squirmbag

Q , G （二国同盟）の場合には、二部屋を二人が占有するので、その組み合わせは二通りしかないが、三国同盟では、六通り、四国同盟では二十四通り・・というようにまともにやれば、凄く複雑なプログラミングになる。実は、私も、最初は、三国同盟を、333、332、322、233、223、222 と分けてプログラミングを考えていたが、Lb　だけでも、ものすごい量のものになってしまった。

しかし、上記の　9種類の技（24　strategies like Lb,Lr・・・・　）は、ナンプレの構造を利用すると、candy_matrix　および　g_matrix　とその transposed matrix　（転置行列）　を使って、同じアルゴリズムによる共通のマクロで書き表されるを発見した。おそらく世界初ではないだろうか？

room=3（三国同盟など）の場合を例に取り、関係する　matrix　との関連をまとめると次のようになる。

            Strategy                Notation       Used  matrix & Coordinate          Used matrix

　Implicit Triple （ Block )　　Lb         Place (Block , Number )       　     gb_matrix ( gg-matrix)
　Implicit Triple （ Row   )　　Lr         Place  (Row   , Number )       　     gl_matrix (gr-matrix )
　Implicit Triple （ Column )　Lc         Place  (Column , Number )       　   gc_matrix

  Explicit Triple  ( Block )      Tb        Place  ( Number , Block )           Transposed matrix of gb_matrix
  Explicit Triple  ( Row  )       Tr        Place  ( Number , Row )             Transposed matrix of gl_matrix
  Explicit Triple   ( Column )   Tc       Place  ( Number , Column )         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.

room=4　、5　の場合も同じマクロでカバーすることになる。

　room=3の場合を例として、実際にどのような解法の流れでそれを実現するのか、その詳細について、メモしていくつもりである。思い出しながら・・

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　to be continue
　
　

　

      

Locked Candidate （いずれにしても理論）

基本技は、たった一つの数字 ( Single number ) とたった一つの場所 ( Single place ) を見つける方法でした。次の手筋は、一つの数字　( one digit ) と二ヶ所の場所 ( Pair place ) に関する配置の特徴を利用して、あり得ない候補を抹殺する方法です。

　通常、消去（eliminate）という術語が使われていますが、私は、defoｒm　（変形）と呼ぶことにしています。Diagram　の候補の変わり行く状態を表す言葉として相応しいからです。また、その結果として、Singles　が浮かび上がってきます。最後に決めるのは、基本技（basic）であるので、deformはその状態を作り出す操作であるといえます。

　普通、一回だけの Deform でSingle が得られます。新ヴァジョンのソフトでは、56種類の　deform macro を備えていますが、さらに難問ナンプレでは、二回のdeform　(double　deform）を経てSingleが得られるというものもあります。単体deform　macro（52）の組み合わせは膨大な数になるので、現在では、105種類だけ探索法として採用しています。

　閑暇休題、Locked Candidate　は、Deform の最も簡単でよく使われる手筋です。

Vb   あるblockの二択候補が同行にあれば、その行には同じ候補はもたない。
Vr　ある行の二択候補が一つのblockにあれば、そのBlock には、同じ候補はない。
Vc　ある列の二択候補が一つのblockにあれば、そのBlock には、同じ候補はない。　

　
パズル通信ニコリ別冊「数独通信」11年秋号Vol.21から引用しました。Locked candidate Vb　の例題です。

　ブロック2（上段中）で　Digit 1　が入る候補の場所は★印のついた( 3, 4) と ( 3, 6) の二か所だけです。この Block 2 の二か所は、同じ　3行目にあるため、「いずれに入っても」他の Block 1 や　3の3行目には、1の候補は理論的に入り得ません。つまり、1の候補はBlock　2に固定（Locked）された状態になり、他のBlock の同行の1の候補は消去されます。結果として、block　3において、4か所あった候補の場所は、( 2, 8) = オ　だけになります。オには、他に　256　といった候補と混在しますので、1は、implicit (hidden) single　となります。この場合、Block　2　にlockされるので、Vbの作用により、消去された後、B　（Implicit　single　of　block　：ブロッケン）によりきまるので、VbB　で表します。

　( 9, 3) = 1 は、VbM　であることを確認下さい。また、Vr　や　Vc　のケースを下記の問題で確かめて下さい。

上の問題は、ニコリ数独名品100選のNo.89（作内山正樹）の問題です。盤面は、 ( 9, 1) = 3が入った状態で、次の一手を考えます。Vc　の例題として紹介します。

次に、candy matrix を示します。

次の一手は　（ 9, 7） = 6 です。　なぜなら、
Column 1 において、digit 6　に注目します。6の候補をもつセルは2か所でしかもblock　7にあります。ゆえにこのどちらかに6がはいるので、Block　７のの他のセルの6の候補は消去されます。Block 7のRow 9の2ヶ所の6も姿をけします。結果、Row　9　において、digit 6 は　implicit single of Row 9 となります。

Explicit Single （マスミー）

すでに述べたように、candy table において、咋に読み取れる　Single candidate である。Naked Single と呼ばれる。
　
　Pencil　work　では、場所を特定して、候補の数を調べて行かねばならず面倒くさい。ニコリ社では、「マスミー」と呼ぶ手法が示されている。

　
　この方法は、名前とは裏腹に前の3つの方法とは見つけにくいため、難易度を計算する格付けソフトでは、
　　　　　　　　　　　　　B　　　Implicit Single of Block          1  point
                                　 R         Implicit Single of Row            2  point
                                    C        Implicit Single of Column        2  point
                                    M     　Explicit Single                         5  point 

となっています。これを basic point と呼びます。

　以上、基本技は、4 種類ですが、（ある解説本では、行(Row）と列(Column)をまとめて一つに数え　3種類となっているのもあります）この基本技がどの程度の頻度で使われるのか、database により調べた結果つぎのようになりました。

　ニコリ数独名品100選　　　　　100　題　　　B 5032          R 238       C 160      M 114
  ニコリ決定版数独　　　　　　 　120　題　　　B 6109          R 298       C 170      M  95 　　　　　　
　激辛数独　Vol.　10                  105　題　　　B 5060          R 365       C 339      M 289
  ナンプレ超上級　28                  101　題　　　B 4859          R 341       C 323      M 270

探索法は、BRCM　の順の「反映取り切り」とした場合の数値です。実際に　pencil work で解く場合には、 きまった Single digit の答えを反映させ、次の解を得る手掛かりとして使います。だから　B　だけで、final　answer　に達することがあり、このようにBだけで取りきった場合、Level　1のBeginner　とランク付けします。
　手筋（stratage）による　level　はすでに書きました。

　　　　　http://kmatsu4.blogspot.jp/2011/10/blog-post.html

             

Implicit Single of Row, Column （レッツミー）

よく使われる基本技の二番目と三番目は、Impicit Sigle of Row と Implicit Single of Column である。ニコリ流にはこれを合わせて「レッツミー」と呼んでいる。この技も Hidden Single であるので、盤面からは他の候補にまぎれて見分けにくい。

　再び、「ニコリ数独名品100選」の一番の問題を使って、Candy Diagram を、Row Number Diagram , Number Column Diagram に変換して、表すと Single place が一目瞭然であるのがわかる。

　　　              　　　　　　　　　　　Fig  1　　　Row Number Diagram　 

                                                      Fig  2          Number Column Diagram   

  　Fig. 1 には5つの　Row Single Place が、また Fig. 2 には、5つの Column Single Place があるのを確認頂きたい。

　Pencil work で解く場合には、その場所を見つける簡単な方法が、「レッツミー」として、紹介されている。

Implicit Single of Block （ブロッケン）

ナンプレの最も多く使われる基本技、しかも初心者用の問題ではこの技（Stratage）だけで解ける基本中の基本技である。

最近になって、ニコリ社が「ブロッケン」という愛称をつけているが、ニコリ「数独」名品100選が発売された2006年（H18)ごろには、初級パターンその①となっている。外国の文献では、Hidden　Single　として紹介されている。ブロッケンが、あるブロックの中で一つしかない候補の場所を特定する手法であるため、他の候補とまぎれて隠れているためである。

私は、Implicit　Single　と呼ぶことにする。この技と反対に、ある場所で、一人ぼっちの候補を見つける技（マスミー）を Naked Singes となずけているので、その好からぬ印象を避けるためである。

また、Implicit　Single　は Block, Row, Column において　3種類あるため、その略称として、
　　　　　　　　
　　　　　　　　B　　　　Implicit Singles of Block          
                      R           Implicit Singles of Row            
                      C           Implicit Singles of Column

を用いることにする。

　なお、旧ヴァージョンでは、R　の代りに　L　を使っていました。新ヴァージョンでは、Lは　Implicit Triples （陰の三国同盟）の略称として使っています。
　　　　http://numberplace.blogspot.jp/2009/09/49-b-search-l-search-and-c-search.html           

　例をもって示そう。ニコリ数独名品100選の第一問の　candy table （候補の一覧表）は次のように求められる。

　Naked　Single は一目瞭然であるのに対して、例えばブロック1の Hidden Single である　1はこの図ではわかりづらいのが確認できるだろう。

 これを、　Block number diagram で表してみると、次のような diagram になる。

　このように、candy matrix を変換して、　block number matrix ( gb matrix ） にすると hidden singe place が今度は一目瞭然である。つまり、block　1において　digit　1が入る場所は、B1-i （ 3, 3) しかない。

　この例では、最初の段階で、この技を使える場所が、4か所あることが分かる。この個数を　No of Entrance of Block という。この個数が多いほど取っ掛かりが得やすい。と同時に、いろいろな手順が選べることが分かる。

　　

Pencil Puzzle の解き方

鉛筆と消しゴムを使って解くのが、Pencil　Puzzle。この場合どんな順序で解くかというと、まず、探す「数字」を頭の中に思い浮かべる。1から順に始める人もあれば、表出数の多い数字の順に始める人もいる。どれでもよい。まず、数字を決めてその数字の残りの数字が入ることができる「場所」を探す。

　探し方は「相棒」でない場所を探す。相棒とはある数字のはいったセル（場所）と同じブロック、行、列のことで、そこには同じ数字は入らない。

　上図は、ニコリ社の数独通信に掲載されている最も基本的な解法である。

まず、1　という数字を決めてブロック　1　において矢印で相棒を消している。残った場所は　アの場所だけであるので、ここにしか　1を入れることはできない。この場所には　1以外にも23　以外の数字が候補として存在することに留意して頂きたい。

　　　
　この　Diagram　で　candy　matrix　を示すと上図のようになる。Block　１において　1の数字の候補は　（２，３）　にしかないのがおわかりいただけるであろうか。Block　にたった一つしかない候補だけれど、この盤面からでは、まぎれてよくさがしだせない。そのため、この候補の数字（digit）のことを、　　hidden　single digit  of  Block と呼ばれている。

　この　1の存在は、次に示す　block-number diagram を見れば、一目瞭然である。

　
　見ずらいけれども、　（B1,n1)= f　になっているのがわかる。つまり　１という数字は　Block 1 において、入る場所は一か所　( 2,3) = f の場所しかないことを示している。

　ゆえに、これは、　Naked single place of　Block ということがいえる。　Naked　は「やらしい」想像を伴うので、わたしは、Hidden 　には、Implicit ,　Naked には　Explicit　を使うようにしている。

　ブロッケンと呼ばれる、基本中の基本である解法は、Implicit single と呼ぶ。


　問題　イ　は　(B9,n1) = g  　であると同時に　（R9,n1 )= g であることを確認せよ。

Place Number Table

 Candy table を　9×9　の二次元マトリックス　can ( i , j )で表す。このマトリックスの作り方は前に述べた。
            　http://numberplace.blogspot.com/2009/06/23.html

 場所の候補を表す　マトリックスを　Place Number Table で定義する。これには、Block Number Table ,  Row Number Table , Number Column Table の3種類がある。それぞれ、数字の入る場所の番地の候補を表している。

　Fig .5 の問題に対して、このマトリックスを示せば次のような　Diagram　になる。

Fig. 7  Block Number Table

Fig. 8  Row Number Table

                                                              Fig.  9   Number Column Table


　ナンプレを解くには、
　　　①　数字をきめて、その数字が入る場所を探す　か
　　　②　場所をきめて、そこに入る数字の候補を探す　かのどちらかである。

　場所を探す①ときには、Place Number Table　（ Fig. 7 , Fig. 8 , Fig. 9 ) を使う。

　数字を探す②ときには、Candy　Table （ Fig. 6 ) を使う。

Candy Table

基本的なナンプレの解法を説明する前に、具体的なナンプレを例にとり、構造解析に必要なDiagram　を示しておこう。

　例題として、「ニコリ名品100選」の1番を取り上げよう。

　　
　　　　　　　　　　　　　　　　　　Fig.　5　Row　Column　Diagram

　まず最初に、Fig.5 の空白セル( Empty Cell ) のそれぞれに入る候補の数字を小文字で挿入すれば、Fig. 6 で表される。

　　　　　　　　　　　　　　　　　　　　Fig. 6　　Number　Candidate　Diagram

　この候補の一覧表を　Candy　Table　と呼ぶこととする。

ナンプレの構造

ナンプレ（ number place ）は、構造的には、数字と場所を探すパズルである。数字は1から9までの9種類、場所は、9個の　block、row、column　のセルにそれぞれ　9ヶ所ある。

　この4つの　number、block、row、column　を2次元座標で表現する。( row , column ) 座標で表したDiagram （ Fig.1 ） が、通常のナンプレ本に表れる　Diagram（盤面）である。

Fig. 1  Number place diagram

　場所を示す番地を、block ,  row , column 毎に、Fig. 1 の　1 から 9 までの数字に対応して表す。番地であることがわかるように、数字の代りに、a b c d e f g h i を使うことにする。

　例えば、 ( 2 , 3 ) に対応する場所は、block-number 座標では、B1-f　となる。同様に、 row-number 座標では、R2-c　、number-column 座標では、　C3-b　である。

　上の　Diagrum　をそれぞれの座標をもつ　Diagram に変換すると次のようになる。

Fig. 2      Block-Number Diagram

Fig. 3    Row-Number　Diagram

Fig. 4    Number-Column Diagram

    最初は慣れていないので、わかりづらいが、やがてナンプレ解法の構造が容易に理解できるようになるだろう。