Search macro

 Search macro は、次の　3種類に大分類される。

（１）　Basic search
　　　　Single　candidate　を探し、セルの値を決定するマクロで　4種類からなる。

　　　　①　B_search　　Single　candidate　in　Block
　　　　②　R_search　　Single　candidate　in　Row
　　　　③　C_search　　Single　candidate　in　Column
　　　　④　M_search　　Single cell　in　any　digit

（２）　Deform　search
　　　Candidate　を　logical　な方法で、消去する。よく　eliminate　が使われるが、ここでは　doformを使う。

　　　中分類で、23種類の　deform　macro　が登録されている。

　　V、W,　Q, G, P,　Φ、Δ、　K,　S、　Ξ、　H、Ω、Y,　Π、Γ、Λ
　　L,　T,　U、N,　J,　O,　F,　I,　J,　A　
　
　　小分類では、さらに　3個の　deform　macro　に分かれる。
　
　　例えば、　V_deform　は、Vb_deform、　Vr_deform,　Vc_deform　よりなる。

　（３）　Combine　macro
　　複数の　deform　macro　の組み合わせた　deform　macroで　小文字で表す。
　　”ｖ”、”ｑ”、によって、複数の変形と複数の探索を行う。
　　”ｑ”の時には、"vq"、"wq"　の変形をおこなう。

　探索の方法（search_macro）の紹介は「ナンプレの構造」を使って次回以降説明します。

Ranking List

 　　現在使っている数独のレベル表示

      26 Stratage Levels  presented by Ryuzen ; Numberplace Ranking Program

①　Beginner　　　　　　　　　B（1）

②　Very　Easy　　　　　　　+R(2)､C(3)

③　Easy　　　　　　　　　　+　M(4)

④　Cute　　　　　　　　　　+V(5)

⑤　Sweet　　　　　　　　　+W(6)

⑥　Lovely　　　　　　　　　+Q(7)

⑦　Smart　　　　　　　　　+G(8)

⑧　Ladybird　　　　　　　+v(31),w(32)

⑨　Pleasant                    +q(33)

⑩　Comfort　　　　　　　+g(34)

⑪　Honeybee　　　　　　+P(9),　＋Φ(10)　+Ξ（13）

⑫　Healthy　　　　　　　　+p(35)　+φ(36)　+ξ（39）

⑬　Joyful　　　　　　　　　+S(12)　+K(11)　+s(38)　+k(37)

⑭　Satisfy　　　　　　　　　+Y(17)　+y(42)

⑮　Dream　　　　　　　　　+H(14)　+Ω(15)　+h(40)　+ω(41)

(16)　Dragonfly　　　　　　　+L(18)　+T(19)

(17)　Beetle　　　　　　　　　+U(20)　+u(45)

(18)　Thunder　　　　　　　　+l(43)　+t(44)

(19)　Nightmare　　　　　　　+N(21)　+O(22)　+J(23)

(20)　Pain　　　　　　　　　　＋n(46)　+o(47)　+j(48)

(21)　Fear　　　　　　　　　　+F(49)　+Z(25)　+I(26)

(22)　Death　　　　　　　　　+f(49)　+z(50)　　+i(51)

(23)　UFS　　　　　　　　　　+Γ

(24)　Birdy　　　　　　　　　　A

(25)　Eargle

(26)　Albatoross

　

　　　

A search memorandum (3)

　numk=1 の　a0 の試行が終了すると、次の段階へと移る。

　numk=2 になったとき、klevel=1  であれば、　　a0 で破綻、逆に　b0 は決まり。
　　　　　　　　　　　　　　klevel=2  であれば、　a0 　 b0 　 ともに健全、　b0　で試行。

　a0　で破綻の場合、klevel=1　であるので、まだ新しい候補　a1、　b1　は読み込まれていないので、当然　a1=""　である。

　この時、　b0　は決まりであるので、　Sheet 　1　のDIAGRAM　に　b0　を代入、これを元の問題とするために、次の　4つのことをする。

　①　b0　の入った問題を新しい出発点とするため、　transfer_A_to_C 　で　C　に移す。
　②　numk=1　に戻す。
　③　Sheet 9　の　D25:K25　の候補の数字を　Erase　する。
　④　これまで、求まった解の数　numa　をつなげる。ippatsu 　の　contrepeat に返る。変わっていないのは、　klevel　だけであり、今後の仮定回数にプラスされる。

　klevel=2　になっている場合、　a0　がまだ生きている。したがって　b0　の試行を行う。
　klevel=2、　numk=2　の場合、a0　b0が残っており、次のステップ　numk=3　に進む。

　　
　

A search memorandum (2)

new_class_search に　klevel=1, numk=1 で入った時、まづ a0 を用いて計算を開始する。numk=numk+1 で　numk=2　にして、　ippatsu にもどり、探索計算を行う。

その結果は次の　3ケースに分かれる。

①　a0　の仮定だけで、msd　を実施、final_answer_check において、 msg="Conouer " となった場合。唯一解の場合には、exit sub とする。

②　a0　の仮定で破綻した場合。can ( i, 5)=0  となる場合で、stopflag="stop" にする。この後、新しい候補を求めないで、 klevel=1  のまま　new_class_search に戻る。マクロの中での判定は、stopflag でもよいが、次の候補は読み込まれていない。つまり　a1=""  であることがわかる。

③　a0　の仮定ではまだ、決着がつかない場合。もう一度の　break though をはかる。　klevel=2  にして、次の候補、 a1, b1 を　Sheet 9 に書き込む。（この段階で、まだ　b0　の試行を行っていないことに注目。）

A search memorandum (1)

A search について、メモしよう。

最初に使用する用語の説明

①　打開　break through    /// klevel
    候補の呼び出し回数を表す指数

②　破綻　failure         /// stopflag
   間違った候補の数字を仮定すると破綻をきたす。このチェックは count_kosuu で行う。セルのもつ候補がない時、明らかに破綻である。　stopflag="stop"  とする。

③　征服　conquer    /// msg="Conquer"
   final_answer_check において、すべての条件を満足すると、 msg="Conquer" となる。唯一解の場合には、ここでとどめてもよい。複数解の場合には続ける。

④　試行　trial      ///  numk
  仮定した数字を用いて解析を進める。numk=2^6=64 で次の階層に入る。ただし、破綻をきたした段階で、numk を元の階層に戻す。

　さて、klevel=0, numk=1　で始まる探索の旅であるが、　fmid　と　msd　で取りつくしても、conquer　に至らぬとき、万策尽きて　A search に突入する。

　まず output_two_candidate により、二択の候補を Sheet 9  の D25:K25 に書き込む。

　簡単のため、 a0 , b0 でもって説明する。

25型（R5C5)JNP

　Number Place を「数字を置く」と訳している人がいるが、これはその構造原理に精通していないからであろう。Number は数字のこと、25型JPNの場合だと、1から25 までの数字のこと、Standard Number Place の場合、1から9までの数字で　digit と呼ばれる事がある。Place　は名詞で（特定の）場所を表す。数独愛好者には、年寄りが多いので、Place の事を「マス」と呼ぶ。だから、｢マス目」は全体の表のことで、 Diagram に相当する。

　PCのprograming では、matrix　演算を使うので、place　は、 cell　(セル）　の事である。そして、i 行、j 列 の place （セル）に入る　number が n であるとき、 ( i , j ) = n とあらわす。 以前は、R i C j のようにセルの位置を matrix 表示することがあるが、表題にも使っているように、R5C5　は縦方向および横方向の Block の数を表す場合に使うことにする。次回の　28型　R7C4 は縦方向に4行のBlock　が ７個、横方向に７列の Block が 4個　ということである。

　Number Place の性質として、9種類の数字の交換則、同じRおよびC block 内での行および列の交換、８種類の対称交換、R block、C block の交換則が成立する。また、あるNumber の9　個のplace の配置（ loop とか cycle とか言う）の説明にも、Rおよび　Cの表現は便利である。

　Q60　の解答　　　Pleasant 291 sec

　　「8」　+　「9」　+　「23」　+　「24」　+　「14」　=　｛　78　｝

　Q62　の解答　　　Pleasant　　　244　sec

　　「14」　+　「17」　+　「6」　+　「23」　+　「10」　=　｛　70　｝

　Q64　の解答　　　Pleasant　　　282　sec

　　「1」　+　「10」　+　「4」　+　「9」　+　「17」　=　｛　41　｝

25型(R5C5)JNP

　「数独の一般解法はあるのか？」と聞かれたら目的によって幾通りも提案されているよ、と答えよう。もし、final answer （最終的な答え）だけを求めたいのならば、数学的な方法やそのアルゴリズは簡単である。唯一解であろうと、多数解であろうとパソコンレベルで数秒とはかからない。問題は条件付き多変数連立方程式の数値解を求める問題だから、いろいろな最適化手法が応用できるし、Dynamic　Programig とか、ブロックデザインとかグラフ理論など応用すればいろんな方法で可能であるし、実際この種のフリーソフトはよく出回っているようだ。
　数独の面白さは、鉛筆と消しゴムをつかって解くことにある。数字の配列の特徴を考慮した探索技術を駆使して final answer に到達したときの達成感は高度な　technic であれば、なおさら高まる。一手一手の中間段階で使われる探索方法が明示されるとき、「理詰め」で解くといわれるようだ。PCアシストは問題ではない。今は数学の試験に電卓を使ってもよいのと同じである。
　この手のソフトも数多く出回っている。PCの使用と「理詰め」とは直接関係がないし、また、試行錯誤法とも全く違った概念である。具体的にその説明から入っていこう。

　Q56　の解答　　Pleasant 382 sec

「11」　+　「20」　+　「16」　+　「4」　+　「19」　=　｛　70　｝

　Q58　の解答　Pleasant　320　sec

「16」　+　「2」　+　「15」　+　「12」　+　「25」　=　｛　70　｝

16型(R4C4)JPN

　引き続き「超難問ナンプレ＆ 頭脳全開数理パズル7・8月号」の16型ジャンボ・ナンプレの解答をしよう。

　Q50　　　「7」 + 「14」 + 「14」 + 「1」 =　{ 36 } Pleasant 44.8 s ( PC time)

Q52 「 12 」+「 12 」+「12」+「11」=　{ 47 } Eagle 473 s ( input time )

Q54 「 8 」+「 15 」+「 6 」+　「15」　= { 44 } Plesant 67 s ( PC time)

ジャンボナンバープレースに挑戦

　「超難問ナンプレ＆頭脳全開数理パズル７・８月号」を例に取り、PCで解くナンプレ・ソフトの内容を、断片的に紹介しているものであるが、今回からジャンボ・ナンバープレース（JNPと記す）　の問題に取りかかろう。　
　使用するソフトの解法はスタンダードナンプレと同じであるので、アルゴリズムもほとんど同じである。JNPの種類によって、16型（R4,C4)JPN　や 25型（R5,C5)　JPN と呼ぶことにする。n^2型JPN は通常正方ナンプレであり、block の大きさは　n×n である。
　正方ナンプレ以外の奇形ナンプレ（例えば、30型（R6,C5)　や　28型（R7,C4)　）も同様に扱える。ただし現在の処、本ソフトでは、99型JNP　までが限界であるが、私が知っている限りでは、49型JNPが問題として存在する最高のものの様である。

　Q48　は　16型（R4,C4)JPN　である。
　　　　　すでに format があるので、input time=5 min 25 sec
PCの consumed time= 77 sec

解答　　13　+　2　+　14　+　12　=　「41」

　　　　　crux　①　42 手目 (8, 10 )= 15　 VbcR
　　　　　　　　　②　43 手目　　(1, 12 )= 15 VrB
③　56手目　　 (3, 11)= 10 QcB
④　63手目　　　(14, 11)= 4 GrB
　　　　　　　　 ⑤ 68手目　　　( 4, 5) = 9 or 15 二択より( 4, 5)=9 A11

Level 24 ( birdy )



　

有村智恵が albatross と holl in one を達成

今朝の朝刊の一面に、プロゴルファー有村智恵選手が　albatoross と eagle (holl in one) を一試合で記録したという。その確率は一日ワンランド周るとして３万年に一回（勿論プロの腕で）であるという。かねてから、私は有村選手を目標にゴルフをやってきた。というのも、私の体重、身長が有村選手と全く同じなのだ。ところが、ロングホールで2オンなどしたこともない。私にはヒラメ筋はないがそれだけではないらしい。飛距離の差がどうしてなのかいろいろと考えてみたが、思い当たることが三つ程ある。
　一つは私は顔が大きく、よって頭がおおきい。通常頭は体重の8％といわれているが、私の場合10％ぐらいはあるだろう。よって、筋肉や骨格の占める割合は彼女より劣るわけである。
　二つ目は、胴の長さのわりに手が短い事である。相撲取りでも自分で尻が拭けない人がいるという。私の場合は無理をすれば、どうにか拭けるが相当な努力が要る。手長猿といわれたゲリィー・プレイヤのように身長は低くても手が長いとスイングの弧が大きくなり、有利であることは確かだ。
　三つ目は猫背であり、ベンホーガンのいう背骨を中心とした平面状の正しい軌道のスイングができない点である。
　このような欠点にもめげずゴルフを続けているのは、いつの日にか　albatross　ができるのを夢見ているからである。
　
　ナンプレのレベル表示にについて話をしよう。よく問題の難易度をあらわすのに、☆の数で表したり、medium とか hard とか言葉で表したりすることがある。一体どんな基準で決めているのかしる由もないが、これまでの例題をみても（すべて　☆４　）大分差がある。
　本ソフトの場合には、使用する探索法のレベルによって、問題の難易度をクラス分けしてランクを２６種類に分類する。これまで出てきた、lovely , thumder はそれぞれレヴェル6 および　18に相当する。　レヴェル24 , 25 , 26 はいずれも仮定法による解法で、一か所の仮定で解が求まるのが、 birdy 、二か所が eagle 、三か所以上が arbatross と呼ぶ。というわけでここでも albatross は最高難易度であるわけである。

　
　Q28　の解答 ( 3, 8)=9 54手目　（全57手の内）
　　Level　11　( Honeybee ) P

　　　crux ① ( 4, 3 )= 4 37%　　 Pr　　 16手目
　　　　　　 ② ( 7, 7 )=8 7% 　　　Pr　　 27手目

　　no of entrance = 11
　　place distance =15

　　np point =76

数独は理詰めに限る？

数独通信’11年春号Vol.20に、ニコリ社の御大の標記座談会が掲載されている。数独の名づけ親鍛冶氏は「自己流の解き方でもなんでもいいから、楽しんで解いてくれればそれでいい。」　（理詰めとかゴジャゴジャ言わずに、解き方が人によって違うから面白いのだ。といったニュアンス）　だから数独が解けたときの達成感を味わうのもさることながら、解き方を競い合うのも楽しみの一つということになるのか。


　Q21は解き方を見るのに適した問題である。


　Q21　の解答　(9,6)=2 　19手目（57手の内）
　　　　レベル18　（ Thunder ） Pl
　　 crux 　①　（7.6）＝9　　　8%　　　　Pr　　10手目
　　　　　　　②　（4,9）＝4　　72％　　　　vl 11手目
　　　　　　　③　（3,7）＝7　　　７％　　　　wl 13手目
no of entrance=12
plane distance=9
np　point=102

これは、激辛9　に換算すれば、11位の難易度になります。


　で、本題ですが理詰めで解くと上記の結果ですが、 forced chain,とか仮定法を使うともっと簡単になり、おそらく読者もこれをえらばれたのでは？
　なぜなら、11手目で　crux　にさしかかり、pair candidate （二択候補）を調べると、なんと35組もあり、そのうち27組が　birdy point （一回の仮定で決まる）であるからです。つまり当てずっぽ取ってやっても、7割以上の確率で成功するというものです。

　「理詰め」という言葉には、人によってあるいは専門分野によって、解釈が異なるようだ。多いのは（数学屋ではない人で理系で線形代数をかじった程度の人）、数独解法のなかで、候補の数字または場所を絞りこみ、一つの数字、一つの場所を順番に決めていく方法を限られた「万人」が容易に認める手順だけを使って解くことと解釈しているようだ。

　数学用語では、演繹的とか決定論的とかいう術語がある。広く「理詰め」に推論を進めていく方法で答えを導き出す。数独解法に当てはめるとどの方法も、演繹的であるから、「理詰め」であるといえる。

　数独の理詰めは、言い換えれば、解を求めることだけでなく、唯一解の証明を必要とする。二択候補で、一方で解がもとまっても、もう一方が解でないことを証明しなければ、理詰めとは言えない。唯一解でない手筋の証明は、破綻をきたすことの証明で、「候補が消える」か「場所がなくなる」ことを証明しなければならない。

　Pencil Work ( 鉛筆だけで解く）を前提とする数独では、たとえ二択仮定法で、解がもとまっても運が良かっただけで、（二択の選び方がよかった）もう一方の破綻の証明まではしない。もし破綻する方を選ぶと、もう一方が正解だとにわかに信じがたい。盤面はゴジャゴジャになっているし、どこかでミスをしたのではないかと不安が先立つ。どちらの場合も、解き味とか達成感とかからはほど遠くもっと明快な「理詰め」の方法を模索する。Pencil　player　からは不評で忌み嫌われる解法でもある。

　多数解の関係を調べていくと、数の繋がりが見えてくる。1から9までの数字それぞれが、9つの場所で繋がっている。9本の糸を九つの結び目から解き放すのが数独の解法である。Chain　とか　Loop　とか呼ばれる解法によみ解く方法が、Pencil　Player　の熟練につながっていくものであろう。

激辛数独シリーズの難易度

ニコリ社出版の人気数独本「激辛シリーズ」の難易度（np　point)をデータベースより調査した結果を次に示そう。これまで、①から⑨まで九冊の本が出版されているが、どれも問題は105問である。総得点と一題あたりの np point は難易度の高い順に次のようになる。

　　第一位　　　激辛9　　　　8560　　　81.52
　　第二位　　　激辛7　　　　8460　　　80.10
　　第三位　　　激辛8　　　　8206　　　78.15
　　第四位　　　激辛6　　　　8102　　　77.16
　　第五位　　　激辛3　　　　7895　　　75.19
　　第六位　　　激辛5　　　　7826　　　74.53
　　第七位　　　激辛4　　　　7806　　　74.34
　　第八位　　　激辛1　　　　7597　　　72.35
　　第九位　　　激辛2　　　　7559　　　71.99

　これらは、難易度の高い本であるが、ちなみに数独本の定番の
　　「ニコリ数独名品100選」は、　　6510　　　65.1　　　である。


　Q14の解答　　(1,1)=6 30手目（55手の内）
レベル６ ( Lovely ) QQ
　　crux　①　(8,5)=5 31% 9手目　　QrB
②　(1,4)=9 10% 17手目　　QrR
np point=83

　この問題は、激辛9で比較すると、第43位に位置するが、激辛1では、13位になる。

時間は如何ほどかかるのか？

　まずスタンダード・ナンプレの　Q７から取り上げる。
　PCで計算する場合、どれくらいの時間がかかるのか？測ってみた。
　　入力を始めてから、最後の出た答えをデータベースに格納するまでの時間(total time)は、スタンダード・ナンプレ（ Q7, Q14, Q21, Q28)で次のようになった。

　Q7 　　　　1分24秒　（input　54秒、　PC　20秒）
　Q14 　1分20秒　（input　54秒、　PC　18秒）
　Q21　　　　2分34秒　（input　53秒、　PC　92秒）
　Q28　　　　1分21秒　（input　52秒、　PC　17秒）

　Q7　　解答　　(5,8)=8 12手目（55手の内）
　　　　　レベル6　（Lovely）
　　　　　crux　5手目　(7,3)=6 Q 28%
np point=73

解説　この問題は、取っ掛かりが少なく（number of entrance=4 ) また早くも五手目で急所(crux）にさしかかる。しかし、陰の二国同盟( hidden pair alliance of block Qb)で、全計算時間の28%　を費やするがそれを乗り切るとあとはすいすいと解ける。解答マスは、12手目で通過するがもちろんこれはcrux　通過後の適切位置にある。
　np point =73 は、激辛1 (72.35)の平均と激辛4（74.34）の平均の中間あたりの難易度といえる。



　
　　　　

超難問ナンプレ＆数理パズルに挑戦

　超難問ナンプレ＆頭脳全開数理パズル2011年7・8月号（Gakken,580円）を入手した。手持ちのソフトを使って、これらの難問にチャレンジしよう。
　ソフトはノーマルナンプレに対して最新鋭の「数林Ver.1.2　2011」を使う。このソフトの詳細については実問題を解きながら随時説明することにしよう。ソフトの開発にあたっては、最初から　①ワン・クリックで自動的に最終解が得られること、②途中経過つまり手順が説明できること。　③使用した探索法が人間が解く時をシュミレートできること、に留意した。
　今回のソフトの新しい特徴は、世界初（？）難易度を数値化したナンプレ・ポイント（NP　point）が求めることができること。代表的なナンプレ本のデータベースを備えていること。などなどである。
　これは備忘録ではあるが、一般公開をして、もし興味のある方がいればコメントをいただきたい。これまで公表したことがないので、ひとりよがりの処は是非とも糺したい。コメントがあれば、それにそった方向に話を進めていってもよい。
　7月30日まで、表題本の色々な問題を順に解いていくつもりだが、あまり期待はしないでほしい。なにせ備忘録なのだから、予告なしに公開をやめることもあることをあらかじめ断わっておく。

ホームレスがナンプレに挑戦！

　和歌山ソフトウエアコンテストでは、富士ゼロックス社の企業賞を獲得した。その日から数独への興味は極端に減衰した。
　あれから４年が経過している。数独（ナンプレ）はますます盛んになり、時々電車の中や公園のベンチで熱心に解いている人も見かける。日本橋の電気街のホームレスは拾ってきた本を堆く積み上げてある。週間朝日や文芸春秋といった本も見受けられる。先日通ったときには、数独を解いているのには魂げた。場所は違っても私と同じ趣味傾向ではないか。
　本屋さんの数独コーナーにもたくさんの数独本や数独雑誌が並ぶようになった。おばあさんがナンプレファンを買っていったとおもったら、今度はおじいさんがやってきた。「ボケ防止にやってますねん。」といっていたがそんなことはない。立派な趣味である。
　これだけポピュラーな娯楽に発展させた鍛冶真起氏の功績はおおきい。