各種探索問題

ペントミノ

□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□
□■□□□□□■□□□□■■■□□□■■■□□□■□□□□□■■□□□
■■■□□□□■□□□□□■□□□□□□■□■□■■□□□□■■□■□
□■□□■■□■□□□■□■□□□□□□■□■□□■□□■□□■□■□
□□□□■□□■□□■■□□□■□■□□□□■■□■□□■■□□□■□
□□□■■□□■□■■□□□□■■■□□□□■□□□□■■□□□■■□
□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□
>
５個の正方形を並べてできる１２個の図形を５＊１２または６＊１０の箱に入れる
問題で、パズルとしても売られているありふれた問題です。
コンピュータで解く場合、私の考えた速度アッフ゜のこつは
置いた時、となりのコマまたは箱とのあいだのスペースが最小の置き方を優先する
連続するスペースの数は、いつも５の倍数でなければならない
の２つの条件のなかで試行錯誤するものです。
とりあえず、コーディングして実行し、答えらしいものがでるレベルのものは、
Pent5.javaのとおり
この段階の問題点は以下のとおり。
・答えがｘ軸、ｙ軸に対象のものも重複して解答にしている。
・コマの回転変換でも重複したものがあり解答が重複する。
・速度アッフ゜のためには変化の少ないものを先に置いた方がよい。
これらの問題を解決するために、kpos の初期値をタイトルの下の図形の順に変えた。
２番目の図形は本来４種の変化があるが、ｘ軸、ｙ軸に対象な解答を一つに集約する
目的で２種類とrnoで定義した。
箱の形は６＊１０と５＊１２があるが、Pent6N pent5Nとした。
ペントミノプログラムダウンロード

古典的速度アップの効果

現代ではコンピュータの速度が飛躍的に進歩し、速度の速いプログラムを作る考えは
あまりなくなった。ここでゆう速度の速いプログラムとは何か、それが問題だ？。
定義を決められないまま、古典的速度アップをここで述べる。
①モーストインナループ
　　プログラムの速度の決め手は最も内側のループの時間を最小にすれば、９０％以上
　　最適値に近ずくとゆう古典的格言です。
②アセンブラでプログラムする。
　　古き時代の先輩から酒の席で聞いた話で,今や実践する人はいない。
　　しかし、C言語にはこの時代を受け継ぐ思想が残っているので少しだけ、述べる。
　　・C言語では変数を定義しても初期化（自動的に０をつめる）されない。
　　　不要な初期化は無駄なステップなので、プログラマに必要なものだけ初期化する
　　　自由を与えるものである。
　　・C言語では配列のインデックスのオーバーをチェックしない。
　　いまやこのような配慮が有効と思う技術者はいない。
モーストインナループは今でも気にするプロの技術者は多い。
このプログラムで効果を確かめて見よう。
Pent6N のplace　がこの場合　モーストインナループ　である。
その中で　rotSet　は次に可能な置き場所をリストしながら

本プログラムのモーストインナループ改善

回転と反転を含めた全ての形はあらかじめ、コンストラクタで作られkomaに配列として
格納されている。
pは形の座標を示す配列である。この配列の０から置くことが可能かしらべる。
Pent5.javaの段階では形の中心の点が配列の０に入っている。
もし配列の０に中心から一番遠い点の座標があれば、最初の判定でこの位置に格納できない
ことを判定できる確率は増加する。
すなわち、kposの初期値の順を入れ替えれば解決する。
Pent6NN.javaでこの時間測定の結果　１〜２割の時間短縮になることがわかった。

困った問題

ペントミノの解答の数は、インターネットで検索すると2339であると書いてある。
なぜかこのプログラムでは(Pent6を除く) ４６７８通りの答えがあるとでている。
この問題は対称形を見落としていた、ある答を１８０度回転させたものを、別の
者として２重カウントしていた。Pent6NN.java　に修正反映した。

ペントミノ正解の数

正解の各パターンは　ans6NN.txt　にある。

盤の形式	正解の数
３＊２０	２
４＊１５	３６８
５＊１２	１０１０
６＊１０	２３３９

石の並べ替えクイズのコンピュータ解

<マーフィレポート０４４より引用＞

【Java（０2）】
この世で知らないことがあることを知らなければ全知である。この世でできないこ
とがあることを知らなければ全能である。FM-７で唯一の言語はF-BASICである。
F-BASICで書ける世界が全世界でありしたがってTさんは全知全能である。
　Tさんは卒論を思い出す。
「ｎ個の白石とｎ個の黒石が連続して並んでいる。隣り合った２つの石をｎ回水平に
移動して白石と黒石を交互に並べ替える。ただし、途中の両端の石の最大距離は２ｎ
＋２以内であること」
　ｎ＝３　の場合の例を示す。
　　　　　　１２３４５６７８９A　　移動　　　　　距離
初期状態　　○○○●●●　　　　　　　　　　　　６（２ｎ）
１回目移動　　　○●●●○○　　　１２を７８へ　６（２ｎ）
２回目移動　　　○●●　　○●○　６７を９Aへ　８（２ｎ＋２）
３回目移動　　　　　●○●○●○　３４を６７へ　６（２ｎ）

　卒論時のTさんは半年かかりでｎ＝１４までといた。
　F-BASICを取得したTさんは１ヶ月でといた。全知全能の私的幻想を抱いた。

【Javaもろもろ（０３）】
前回の石並べの問題、ｎ=4の場合を示す。
初期状態　　○○○○●●●●
１回目移動　○　　○●●●●○○
２回目移動　○●●○　　●●○○
３回目移動　○●●○●○●　　○
４回目移動　　　●○●○●○●○

＜吉川さんのアイデア＞

Ｎ＝８　は　Ｎ＝４＋４　すなわち　Ｎ＝４の操作を２回行う
Ｎ＝９　は　Ｎ＝４＋５　すなわち　Ｎ＝４とＮ＝５の操作を行う
Ｎ＝１０　は　Ｎ＝４＋６　であり　以下同様に無限大まで可能。

N = 8
○○○○○○○○●●●●●●●●××
○××○○○○○●●●●●●●●○○
○●●○○○○○●●●●××●●○○
call N=4
○●●○××●○●○●○●○●●○○
○●●○●○●○●○●○●○●××○
××●○●○●○●○●○●○●○●○
正確にはこのようにＮ＝４を入れ子にすることで最適解となる。
この手順の下半分はＮ＝４の解そのものではないが、このように
変形すれば、無限大に入れ子にできる。
したがって、Ｎを（４ｘ＋ｙ）の形にして無限大まで解ける。
ここでｙは４、５、６、７とする。
吉川さんの案はすばらしい、これに気がつかなかったので、
Ｎ＝３から１４まで解けるプログラムを作成した。
以下にそれを説明する。
Ｎ＝５から１４の回答

コンピュータで解くための枝刈のルールは以下の通り。
証明は知らない、試行錯誤できめた。
①　最初の移動元はＮ＝３は位置０からＮ＝４移行は位置２から
②　移動元の２個の石のどちらかは、答えの状態にないこと。
③　最後のＮ回の移動は移動先の答えの状態と一致すること。
④　その他の移動はどちらかの石が移動先の答えの状態にないこと。
⑤　移動先が左半分の場合は移動元は右半分であること。
以上を仮定すると、Ｎ＝１４までは１分以内に解ける。
プログラムは以下の通り。

４つの部屋

A B C D の４個の部屋があり、１から６６までの数をどれかの部屋へいれます。
同じ部屋に入った２つの数の和と一致する数はその部屋の入れることはできないとして
どのように４個の部屋に配分すればよいか、
６７の数ではこの条件に合う配分はないことを証明できるか。

４つの部屋プログラムダウンロード

世の中に頭の良い人は多いが、スーパープログラマを自認し、誰よりも優れたプログラム
を書けると思っている人も多い。
この問題では２時間以上の計算時間をかけても解けたので自分が最高と思っていた。
私の解法では、１秒で解ける。
自分の力の限界を感じ自殺者が続出すると困るので解法の公開を控えていた。
この問題の解き方は、どんな手法がプログラムの高速化に貢献するかを示す良い例
と思えるので、以下最初の発想から、完成までを再現したプログラムにしたがって
説明する。
プログラム改良の詳細

基本的には、Stat　の構造体を持ち回り、１手進める毎に新たなオブジェクトに
コピーして、戻って別の手を試行するのは、基本中の基本である。
構造体に多くの情報をもつと、この場合、６６階層この領域を持つことになるので
スタック領域の不足が懸念されるので、最小限の情報とした。
このプログラムでは、８時間以上かかる。（改良したのでテストはしてない）

２．高速化１の工夫

コメントで示した部分は、まだ部屋が決まっていない数字はその時点ですでにどの部屋
にも入れられない状況なら、この時点で失敗が確実なので戻して別の割り当てをするため
チェックを加えるものである。
一見むだなステップ（時間もかかりそう）のように見えるが効果が上回り、これで２時間
程度で解けるようになる。改良したのでテストはしてない）

３　究極の改善

重要な改善は、部屋の割り当ての順序を小さいほうから行うのではなく、自由度
の無い部屋から、すなわちすでに割り当てた部屋との関係で２つの番号の和の
制限から入れられる部屋が限定される数を優先して部屋を割り当てるもので、
我が師匠の吉川氏のアイデアを採用したものである。
これは画期的な結果を生み、１０秒以下で答えがでる。
探索問題は木構造をたどって成功する経路を探す問題であり、上位の枝分かれが少ない
と末端の枝の数は圧倒的に少なくなるので、この工夫で２時間が一気に１０秒に短縮され
るのである。
本当に正しい結果がでるのか疑いをもつひとがいると思うので以下に回答の出力をつける
C:\javaw\monop>java Mono66
start Mono66 initPos=0
Mono66 type_ID=0 time=0s
Mono66 type_ID=00101 ans_No=1 time=6s
rm=0: 1 2 4 8 11 16 22 25 31 37 40 43 50 57 60 63
rm=1: 3 5 6 7 19 21 23 36 38 51 52 53 64 65 66
rm=2: 9 10 12 13 14 15 17 18 20 54 55 56 58 59 61 62
rm=3: 24 26 27 28 29 30 32 33 34 35 39 41 42 44 45 46 47 48 49
Mono time=6s No of ans=1 No of node=22909

C:\javaw\monop>

４．６７の数ではこの条件に合う配分はないことを証明できるか。

基本的には　N=67　で計算すればよいが、全てのルートを検索するので時間がかかる。
６７の数では条件に合う配分はないことの証明

桂馬とびで盤面オールクリア

盤のコーナからはじめ桂馬に飛んで盤のすべての位置を通ること、ただし同じ場所を
２度通ってはいけない。(桂馬とび将棋の桂馬ではなくチェスの桂馬で８方に飛ぶ)
４＊４の盤は不可、５＊５以上どこまで可能か。

この問題は普通に書けば、６＊６　程度の盤までは解けるが、盤が大きくなると急速に
探索ノード数が増大し時間的にとけなくなる。 keima.java
時間短縮には、前の問題と同様に自由度の少ないところを先に実行するようにすると
大きい盤でもすぐに解ける。　keima9.java 桂馬とびで盤面オールクリアダウンロード

ナイトの世界旅行

上記の問題に似ているが、最後に出発点に戻る条件が追加される。
盤は８＊８から可能でそれ以上はすべて可能かどうか未確認。(Night.java)

問題発生

ナイトの世界旅行の場合は　９＊９　１１＊１１　など奇数の場合解答がでない。
２２＊２２は偶数なのに解答がでない。

ナンバープレースを解くアップレット

９＊９のマスに１から９の数を配置し、どの行、どの列にも１から９の数があり、
更に、そのマスを９個の３＊３のブロックに分けた場合どのブロックにも１から９
の数があるように数を配置する問題です。
最初に問題として２３個程度の数の配置をあらかじめ定めて、出題されるので、
残ったマスを上記の条件を満たすように配置するのがクイズです。
原則は正解は一意になるように出題されます。
この問題の解き方は、このページで何時も主張する、自由度の少ない場所から
トライするプログラムで充分です。
ナンバープレースを解くアップレット

ナンバープレースの問題を作るプログラムは簡単ではない。
何もないところから配置しユニークになる配置を求めるのであるが、数限りなく存在し
すべてを作成すると天文学的な数となり、どんな問題を作るか決める必要がある。
ここでは、コンピュータの解として価値のありそうなものとして、ユニークにするに
必要な場所の数に着目し、普通の問題２４から２３、２２と減らして、いくつが最小
であるかを見つける。
１９までは見つけることができた。
実際にはあまり価値はないが、１７が最小であるとの説もあるが、実際に問題を
見つけることはできなかった。
１９の問題を見つけたプログラムのロジックは、「鉱脈を探せ」と名づけたい。
２０の問題の近く（２個の位置と値を変えた状態）に２０よび１９の問題は
存在し、別の場所ではなかなか見つからない事実から近くを探すことにし、
成功した。
同じ方針で１８を探しているが今のところ見つからない。

横山実習室へ戻る