技の種類は多岐にわたり、その探索する順番は数え切れない。しかし今現在、使っているのは、次の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 が始まる。大文字は単独技、小文字は複合技を表す。
2012年12月1日土曜日
2012年11月29日木曜日
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
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
2012年4月17日火曜日
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 となります。
通常、消去（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 のケースを下記の問題で確かめて下さい。
次に、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 となります。
2012年4月13日金曜日
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
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 で解く場合には、その場所を見つける簡単な方法が、「レッツミー」として、紹介されている。
再び、「ニコリ数独名品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 で解く場合には、その場所を見つける簡単な方法が、「レッツミー」として、紹介されている。
2012年4月11日水曜日
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 という。この個数が多いほど取っ掛かりが得やすい。と同時に、いろいろな手順が選べることが分かる。
最近になって、ニコリ社が「ブロッケン」という愛称をつけているが、ニコリ「数独」名品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 という。この個数が多いほど取っ掛かりが得やすい。と同時に、いろいろな手順が選べることが分かる。
2012年3月16日金曜日
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 であることを確認せよ。
探し方は「相棒」でない場所を探す。相棒とはある数字のはいったセル（場所）と同じブロック、行、列のことで、そこには同じ数字は入らない。
上図は、ニコリ社の数独通信に掲載されている最も基本的な解法である。
まず、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 であることを確認せよ。
登録:
投稿 (Atom)