◆広島県 清川 育男 さんからの解答
プログラム（バックトラック）でのチェックでは今までの報告に間違いないです。
1→A、2→B、3→C を意味します。
●Ｎ＝２ ７手
1 - 3 1 - 2 3 - 1 3 - 1 3 - 2 1 - 2 1 - 2 3 - 1 3 - 2 1 - 3 1 - 3 1 - 2 3 - 2 3 - 2●Ｎ＝３ ２１手
1 - 2 3 - 2 3 - 1 2 - 1 2 - 1 3 - 2 1 - 2 1 - 2 1 - 3 1 - 3 2 - 1 2 - 3 1 - 3 1 - 2 3 - 1 3 - 1 3 - 2 3 - 2 1 - 3 1 - 2 3 - 2 1 - 2 3 - 2 3 - 1 2 - 1 2 - 1 3 - 2 1 - 2 1 - 2 1 - 3 1 - 3 2 - 1 2 - 3 1 - 3 1 - 2 3 - 2 3 - 1 2 - 1 3 - 2 3 - 2 1 - 2 1 - 2 3 - 2 1 - 2 1 - 3 2 - 3 2 - 3 1 - 2 3 - 2 3 - 2 3 - 1 3 - 1 2 - 3 2 - 1 3 - 1 3 - 2 1 - 2 1 - 3 2 - 3 1 - 2 1 - 2 3 - 2 3 - 2 3 - 2 1 - 2 1 - 3 2 - 3 2 - 3 1 - 2 3 - 2 3 - 2 3 - 1 3 - 1 2 - 3 2 - 1 3 - 1 3 - 2 1 - 3 1 - 3 1 - 2 1 - 2 3 - 1 3 - 2 1 - 2●Ｎ＝４ ６１手
1 - 3 1 - 2 3 - 2 3 - 1 2 - 1 3 - 2 1 - 3 1 - 2 3 - 2 3 - 1 2 - 1 2 - 3 1 - 3 2 - 1 2 - 1 3 - 1 3 - 1 3 - 2 1 - 2 1 - 3 2 - 3 1 - 2 1 - 2 3 - 2 3 - 2 1 - 3 1 - 3 2 - 1 2 - 3 1 - 3 2 - 1 2 - 1 3 - 1 3 - 2 1 - 2 1 - 3 1 - 3 2 - 1 2 - 3 1 - 3 1 - 2 3 - 1 3 - 1 3 - 2 3 - 2 1 - 3 1 - 3 2 - 1 2 - 1 3 - 2 3 - 1 2 - 1 3 - 2 3 - 2 1 - 2 1 - 3 2 - 3 1 - 2 1 - 2 3 - 2 3 - 2 1 - 3 1 - 2 3 - 2 3 - 1 2 - 1 3 - 2 1 - 3 1 - 2 3 - 2 3 - 1 2 - 1 2 - 3 1 - 3 2 - 1 2 - 1 3 - 1 3 - 1 3 - 2 1 - 2 1 - 3 2 - 3 1 - 2 1 - 2 3 - 2 3 - 2 1 - 3 1 - 3 2 - 1 2 - 3 1 - 3 2 - 1 2 - 1 3 - 1 3 - 2 1 - 2 1 - 3 1 - 3 2 - 1 2 - 3 1 - 3 1 - 2 3 - 1 3 - 1 3 - 2 3 - 2 1 - 3 1 - 3 2 - 1 2 - 1 3 - 2 3 - 1 2 - 1 3 - 2 3 - 2 1 - 3 1 - 3 1 - 2 1 - 2 3 - 1 3 - 2 1 - 2 1 - 3 1 - 2 3 - 2 3 - 1 2 - 1 3 - 2 1 - 3 1 - 2 3 - 2 3 - 1 2 - 1 2 - 3 1 - 3 2 - 1 2 - 1 3 - 1 3 - 1 3 - 2 1 - 2 1 - 3 2 - 3 1 - 2 1 - 2 3 - 2 3 - 2 1 - 3 1 - 3 2 - 1 2 - 3 1 - 3 2 - 1 2 - 1 3 - 1 3 - 2 1 - 2 1 - 3 1 - 3 2 - 1 2 - 3 1 - 3 1 - 2 3 - 2 3 - 2 3 - 1 3 - 1 2 - 3 2 - 1 3 - 1 3 - 2 3 - 2 1 - 3 1 - 2 3 - 2 1 - 3 1 - 3 2 - 1 2 - 1 3 - 2 3 - 2 1 - 2 1 - 2 1 - 3 1 - 2 3 - 2 3 - 1 2 - 1 3 - 2 1 - 3 1 - 2 3 - 2 3 - 1 2 - 1 2 - 3 1 - 3 2 - 1 2 - 1 3 - 1 3 - 1 3 - 2 1 - 3 1 - 3 1 - 2 1 - 2 3 - 1 3 - 2 1 - 2 1 - 3 1 - 3 2 - 1 2 - 3 1 - 3 2 - 1 2 - 1 3 - 1 3 - 2 1 - 2 1 - 3 1 - 3 2 - 1 2 - 3 1 - 3 1 - 2 3 - 1 3 - 1 3 - 2 3 - 2 1 - 3 1 - 3 2 - 1 2 - 1 3 - 2 3 - 1 2 - 1 3 - 2 3 - 2 1 - 2 1 - 3 2 - 3 1 - 2 1 - 2 3 - 2 3 - 2 1 - 3 1 - 2 3 - 2 3 - 1 2 - 1 3 - 2 1 - 3 1 - 2 3 - 2 3 - 1 2 - 1 2 - 3 1 - 3 2 - 1 2 - 1 3 - 1 3 - 1 3 - 2 1 - 3 1 - 3 1 - 2 1 - 2 3 - 1 3 - 2 1 - 2 1 - 3 1 - 3 2 - 1 2 - 3 1 - 3 2 - 1 2 - 1 3 - 1 3 - 2 1 - 2 1 - 3 1 - 3 2 - 1 2 - 3 1 - 3 1 - 2 3 - 1 3 - 1 3 - 2 3 - 2 1 - 3 1 - 3 2 - 1 2 - 1 3 - 2 3 - 1 2 - 1 3 - 2 3 - 2 1 - 3 1 - 3 1 - 2 1 - 2 3 - 1 3 - 2 1 - 2 1 - 3 1 - 2 3 - 2 3 - 1 2 - 1 3 - 2 1 - 3 1 - 2 3 - 2 3 - 1 2 - 1 2 - 3 1 - 3 2 - 1 2 - 1 3 - 1 3 - 1 3 - 2 1 - 3 1 - 3 1 - 2 1 - 2 3 - 1 3 - 2 1 - 2 1 - 3 1 - 3 2 - 1 2 - 3 1 - 3 2 - 1 2 - 1 3 - 1 3 - 2 1 - 2 1 - 3 1 - 3 2 - 1 2 - 3 1 - 3 1 - 2 3 - 2 3 - 2 3 - 1 3 - 1 2 - 3 2 - 1 3 - 1 3 - 2 3 - 2 1 - 3 1 - 2 3 - 2 1 - 3 1 - 3 2 - 1 2 - 1 3 - 2 3 - 2 1 - 2 1 - 2 3 - 1 3 - 2 1 - 2 1 - 3 2 - 3 1 - 2 3 - 1 3 - 2 1 - 2 1 - 3 2 - 3 2 - 1 3 - 1 2 - 3 2 - 3 1 - 3 1 - 3 1 - 2 3 - 1 3 - 1 3 - 2 3 - 2 1 - 3 1 - 2 3 - 2 3 - 1 3 - 1 2 - 3 2 - 1 3 - 1 2 - 3 2 - 3 1 - 3 1 - 2 3 - 2 3 - 1 3 - 1 2 - 3 2 - 1 3 - 1 3 - 2 1 - 2 1 - 2 1 - 3 1 - 3 2 - 1 2 - 3 1 - 3 1 - 2 1 - 2 3 - 1 3 - 2 1 - 2 3 - 1 3 - 1 2 - 3 2 - 3 1 - 2 1 - 2 3 - 2 3 - 2 3 - 1 3 - 2 1 - 2 1 - 3 2 - 3 1 - 2 3 - 1 3 - 2 1 - 2 1 - 3 2 - 3 2 - 1 3 - 1 2 - 3 2 - 3 1 - 3 1 - 3 1 - 2 3 - 1 3 - 1 3 - 2 3 - 2 1 - 3 1 - 2 3 - 2 3 - 1 3 - 1 2 - 3 2 - 1 3 - 1 2 - 3 2 - 3 1 - 3 1 - 2 3 - 2 3 - 1 3 - 1 2 - 3 2 - 1 3 - 1 3 - 2 1 - 3 1 - 3 1 - 2 1 - 2 3 - 1 3 - 1 2 - 3 2 - 3 1 - 2 1 - 3 2 - 3 1 - 2 1 - 2 3 - 1 3 - 1 3 - 2 3 - 2 1 - 3 1 - 2 3 - 2 3 - 1 3 - 2 1 - 2 1 - 3 2 - 3 1 - 2 3 - 1 3 - 2 1 - 2 1 - 3 2 - 3 2 - 1 3 - 1 2 - 3 2 - 3 1 - 3 1 - 3 1 - 2 3 - 1 3 - 1 3 - 2 3 - 2 1 - 3 1 - 2 3 - 2 3 - 1 3 - 1 2 - 3 2 - 1 3 - 1 2 - 3 2 - 3 1 - 3 1 - 2 3 - 2 3 - 1 3 - 1 2 - 3 2 - 1 3 - 1 3 - 2 1 - 3 1 - 3 1 - 2 1 - 2 3 - 1 3 - 1 2 - 3 2 - 3 1 - 2 1 - 3 2 - 3 1 - 2 1 - 2 3 - 2 3 - 1 2 - 1 3 - 2 3 - 2 1 - 2 1 - 2 3 - 1 3 - 2 1 - 2 1 - 3 2 - 3 1 - 2 3 - 1 3 - 2 1 - 2 1 - 3 2 - 3 2 - 1 3 - 1 2 - 3 2 - 3 1 - 3 1 - 3 1 - 2 3 - 2 3 - 1 2 - 1 3 - 2 3 - 2 1 - 2 1 - 2 3 - 1 3 - 1 2 - 3 2 - 1 3 - 1 2 - 3 2 - 3 1 - 3 1 - 2 3 - 2 3 - 1 3 - 1 2 - 3 2 - 1 3 - 1 3 - 2 1 - 2 1 - 2 1 - 3 1 - 3 2 - 1 2 - 3 1 - 3 1 - 2 1 - 2 3 - 1 3 - 2 1 - 2 3 - 1 3 - 1 2 - 3 2 - 3 1 - 2 1 - 2 3 - 2 3 - 2 3 - 1 3 - 2 1 - 2 1 - 3 2 - 3 1 - 2 3 - 1 3 - 2 1 - 2 1 - 3 2 - 3 2 - 1 3 - 1 2 - 3 2 - 3 1 - 3 1 - 3 1 - 2 3 - 2 3 - 1 2 - 1 3 - 2 3 - 2 1 - 2 1 - 2 3 - 1 3 - 1 2 - 3 2 - 1 3 - 1 2 - 3 2 - 3 1 - 3 1 - 2 3 - 2 3 - 1 3 - 1 2 - 3 2 - 1 3 - 1 3 - 2 1 - 3 1 - 3 1 - 2 1 - 2 3 - 1 3 - 1 2 - 3 2 - 3 1 - 2 1 - 3 2 - 3 1 - 2 1 - 2 3 - 1 3 - 1 3 - 2 3 - 2 1 - 3 1 - 2 3 - 2 3 - 1 3 - 2 1 - 2 1 - 3 2 - 3 1 - 2 3 - 1 3 - 2 1 - 2 1 - 3 2 - 3 2 - 1 3 - 1 2 - 3 2 - 3 1 - 3 1 - 3 1 - 2 3 - 2 3 - 1 2 - 1 3 - 2 3 - 2 1 - 2 1 - 2 3 - 1 3 - 1 2 - 3 2 - 1 3 - 1 2 - 3 2 - 3 1 - 3 1 - 2 3 - 2 3 - 1 3 - 1 2 - 3 2 - 1 3 - 1 3 - 2 1 - 3 1 - 3 1 - 2 1 - 2 3 - 1 3 - 1 2 - 3 2 - 3 1 - 2 1 - 3 2 - 3 1 - 2 1 - 2 3 - 2 3 - 1 2 - 1 3 - 2 3 - 2 1 - 2 1 - 2●Ｎ＝５
| 3n+1 2 |
１２２手を前提にしてのその後 |
５３手 計１７５手
1 - 2 1 - 2 1 - 3 1 - 3 2 - 1 2 - 3 1 - 3 1 - 2 1 - 2 3 - 1 3 - 2 1 - 2 3 - 1 3 - 1 2 - 1 2 - 1 2 - 3 2 - 3 1 - 2 1 - 3 2 - 3 1 - 2 1 - 2 3 - 2 3 - 1 2 - 1 2 - 3 2 - 3 1 - 2 1 - 3 2 - 3 1 - 2 1 - 2 3 - 1 3 - 1 3 - 2 3 - 2 1 - 3 1 - 3 2 - 1 2 - 1 3 - 2 3 - 1 2 - 1 3 - 2 3 - 2 1 - 2 1 - 3 2 - 3 1 - 2 1 - 2 3 - 2 3 - 2 1 - 2 1 - 2 1 - 3 1 - 3 2 - 1 2 - 3 1 - 3 1 - 2 1 - 2 3 - 1 3 - 2 1 - 2 3 - 1 3 - 1 2 - 1 2 - 1 2 - 3 2 - 3 1 - 2 1 - 3 2 - 3 1 - 2 1 - 2 3 - 2 3 - 1 2 - 1 2 - 3 2 - 3 1 - 2 1 - 3 2 - 3 1 - 2 1 - 2 3 - 1 3 - 1 3 - 2 3 - 2 1 - 3 1 - 3 2 - 1 2 - 1 3 - 2 3 - 1 2 - 1 3 - 2 3 - 2 1 - 3 1 - 3 1 - 2 1 - 2 3 - 1 3 - 2 1 - 2 1 - 2 1 - 2 1 - 3 1 - 3 2 - 1 2 - 3 1 - 3 1 - 2 1 - 2 3 - 1 3 - 2 1 - 2 3 - 1 3 - 1 2 - 1 2 - 1 2 - 3 2 - 3 1 - 2 1 - 3 2 - 3 1 - 2 1 - 2 3 - 2 3 - 1 2 - 1 2 - 3 2 - 3 1 - 2 1 - 3 2 - 3 1 - 2 1 - 2 3 - 2 3 - 2 3 - 1 3 - 1 2 - 3 2 - 1 3 - 1 3 - 2 3 - 2 1 - 3 1 - 2 3 - 2 1 - 3 1 - 3 2 - 1 2 - 1 3 - 2 3 - 2 1 - 2 1 - 2●Ｎ＝６
３６５手を前提にその後の１３４手を確認できるか、
３６５手＋８１手とその後の５３手。
ベーシック言語では時間的に無理です。
Ｃ言語等のコンパイル型言語なら十分に可能です。
最長手順の詰め将棋を解いていますから。
大分速くなりましたが、Ｎ＝５は無理のようです。
Ｎ＝２，３，４にセットしています。
変則ハノイの塔の解答プログラム (Basic)
◆愛知県 Y.M.Ojisan さんからのコメント
【清川育男さん解へのコメント】
（１）提示のＢＡＳＩＣプログラムをほぼそのままＣ＋＋で実行してみました。
（ファイル添付 ７ｋＢ）
ＰIII/500MHzでのCPU時間は下表となりました。
CPUクロック当たりの性能はBASICとC++コンパイルで驚くほどは違わないだろうと思いますがどうでしょうか？。
この解法の場合、１．３倍／１手順 程度のE問題であることが、プログラムの配列Tを平均すると分かります。
従って、N=５のCPU時間はN=4のCPU時間の１．３175-61倍程度と推定され、下表のように、宇宙的時間が必要でC＋＋コンパイルでも無理でしょう。
N=６の場合のあと１３４手の場合でも、推定５２５年で無理のようです。
| N | ２ | ３ | ４ | ５ |
| CPU時間 | ０．３ｍ秒 | ５ｍ秒 | １４０秒 | 推定１７００万年 |
（２）清川育男さんが見つけないし最小を確認された ７，２１，６１，１７５の系列の手順を解析すると、一定の手順に従っていることが分かります。
手順を下図に示します。
この手順によるとN＝６以上の解は清川予想より若干多めになります。
パソコン技で虱潰しに調べて見ると、
調べることができたN＝８までは最小解になっていることがわかりました。
| N | ２ | ３ | ４ | ５ | ６ | ７ | ８ | ９ | １０ |
| 清川手順 | ７ | ２１ | ６１ | １７５ | ５０４ | １４７２ | ４３４１ | １２８９９ | ３８４９６ |
|
最小 （パソコン技） |
７ | ２１ | ６１ | １７５ | ５０４ | １４７２ | ４３４１ | − | − |
（３）パソコン技の方法
プログラムリストは分かりにくいので添付しませんが、原理は簡単です。
一度調べたことを全て記憶し、ループやその他無駄な手を再探索しないようにすれば、メモリー容量が許す範囲ではかなり早く探索ができます。
N=8の場合ハードディスクを用いた仮想メモリ（SWAP）まで動員していますが、それでも記憶しない方法よりは圧倒的に早いです。
それはこの問題の場合、記憶して無駄を省くと、探索すべき数が手順数に対して E問題ではなく、
P1問題の程度になってしまうからです。
◆広島県 清川 育男 さんからの質問
【Y.M.Ojisan さんからのコメントに対する質問】
縦型生成手続きによるアルゴリズムでは、過去の検索結果が利用されないので、 横型生成手続き（メモリー容量は多く必要とするが）によるアルゴリズムの方が速く検索されると言うことでしょうね。
確かに手順前後で、Ｄ手目の局面で同一局面となる可能性が考えられます。
そうなれば、横型生成手続きによるアルゴリズムでは過去の検索結果が利用されるので、その後の検索は省略出来ます。
したがって、横型生成手続きによるアルゴリズムの方が同一局面かどうかの照合に時間を要するが、その後の検索を繰り返す縦型生成手続きによるアルゴリズムより有利であると理解してよいのでしょうか。
横型生成手続きによるアルゴリズムを採用してみます。
これはと言う検索のための戦略があれば、、、。
◆愛知県 Y.M.Ojisan さんからのコメント
（１）
残念ながら／縦型生成手続／横型生成手続き／の定義を知りませんので確たる回答ができませんが、雰囲気的にはＹＥＳです。
（２）
照合・検索の時間をもったいなく思う気持ちはとても良く分かります。
しかし、問題にもよりますが、大抵の場合その先の何十万手の操作・探索に比べると、照合・検索の時間はゴミです。
ですから、よほど無駄のある方法で無ければ、戦略というほど凝らなくても十分な結果が得られます。
たとえばメモリー容量を優先するなら、可能性を否定できない状態に１対１対応の何らかのインデックスをつけ、インデックス順に一列に並べて、２分法を適用すれば十分です。
（３）
とはいえ、いろいろ小細工を弄したくなるのが人の常です。
特にこの変形ハノイの探索プログラムは小細工のため、今となっては作った本人すら何だったっけ状態です。
従って、他の方に解説なしで開示しても解読が困難と思いますが、とりあえず、ソース(１３ｋＢ)だけ添付します。
次の土日に時間が有れば解説をつけようと思います。
（４）
なお、このプログラムの構造上の限界 NMAX=N=9で一晩かけて実行したところ答えに至り、清川手順の最小性がさらに確認されました。
ＨＤが壊れるのではないと不安でしたが。
◆愛知県 Y.M.Ojisan さんからの解答
変形ハノイの塔探索プログラム解説
【ちょっと一般論】
探索結果を記憶して虱潰しに探索するプログラムの一般的概念を図１に示す。
この場合の要点は
（１）仮想現実の状態に対して何らかの１対１対応の背番号つけること。
（２）その背番号を無駄なくかつ位置を探索しやすくメモリに割り付けること。
である。さらにできれば、
（３）仮想現実空間での操作（輪の移動）が、背番号集合の空間での計算で可能であること。
が探索速度向上の点から望ましい。
なお「情勢判断」とは最後まで探索する前に、明らかに探索しても無駄な探索枝をすてるような判断をすることである。
２／２０版のソフトではこれを用いていませんが、今回の新バージョンではあとで紹介する１つの方法を追加しています。
【背番号付けの方法】
変形ハノイの塔の場合の背番号のつけ方を図２に示す。
色を無視したときの各大きさの輪の位置は図２の表で大きさ番号１〜６に示される６タイプがあり、これを図示のように各塔上の存在の有無に対応させた各々３bitのビットパターンで対応させるものとする。
色は手順を正しく行っている限り、交互にならぶので、一番上の状態だけ指定すればよい。
各塔毎に（青・黄・空白）の３色があるが、全部が同色である場合はない。
即ち３×３×３−３＝２４通り有る。
さらに青と黄を交換しても手順数に影響はない。
よって実質１２とおりに番号付けを行えばよい。
このうち空白は輪の状態から規定可能なので、４bitは不要で、実際には図３に示すように４通りを区別すればよいが、操作する時の容易性から３bitとする。
この１bitの無駄は【メモリーの圧縮】で確実に取り戻せる。
その３bitは色そのものではなく、塔間の移動の可不可を示すようにつける。
すなわち塔の番号を０〜２とするときｍ番の塔とｎ番の塔間の移動の可不可を
３−ｍ−ｎ番の塔の位置につける。
このようにしてつけたビットパターンを図１の紫矢印で示すようにつないで２進法とみなして背番号とする。
N=8の場合は２７ビットの整数となる。
背番号の範囲は、仮想現実で存在しうる状態数に比較し、かなり多いものとなるが、各大きさの輪の状態が分離しているので、
操作＝計算を背番号集合上で実施するのに便利なのである。
【背番号集合上での操作】
輪の移動の選択枝はまず最初に、最も小さい輪の状態（３bit）と移動可不可の状態(3bit)で決まる。
そしてそれらは、図４に示すように小さな輪が２箇所にある場合（ｔｙpe1）と1箇所にある場合(type2)に分かれる。
(type1)の場合は移動はすべて最も小さい輪の移動だけの最大４通りがあるが、その結果影響を受けるのは、やはり最も小さい輪の状態（３bit）と移動可不可の状態(3bit)の合計６bitのみである。
一方(type2)の場合は最も小さい輪の移動の最大２通りに加え、次に高い位置にある輪の移動（最大２通り）が選択肢となる。
この場合影響を受けるのは関連の９bitのみである。
因みに次に高い輪の探索は、背番号を３bitずつずらしては小さい輪のある位置をマスク( 背番号bitshift bitAnd 101 等)して０か０でないか判定する。
６bitは６４ ９bitは５１２であり、大した量ではないので計算時間短縮のために、全てのケースについて移動後の状態を配列に記憶させ、ビット毎の排他論理輪で背番号に対して操作（ビット計算）ができるようにしてある。
ただし、移動の結果、ある塔が空白になった場合のケースに関しては、別途空白状態を検査し、空白の塔があれば、対応する移動可不可ビットパターンの３bitを修正する。
因みに空白かどうかの検査は ００１００１００１・・・という各塔対応のビットパターンと移動後の背番号とのbitAndをとれば一発で検査可能である。
【メモリーの圧縮概念】
図５にこの問題のメモリーの利用状態を示す。
仮想現実に対して背番号は過大に割り当てていることは先に述べたとおりである。
さらに、この問題では探索する範囲は、手順が進んでも以外に増えないため（P問題程度）、最小手順を発見するのまでに利用される個数は相対的に非常に少なく、背番号は大部分が使われることなく終了する。
背番号からメモリー位置を探索するオーバーヘッドを小さくするには
メモリーアドレス＝背番号×定数とするのが良いが膨大な無駄メモリーが必要になるのである。
そこで、一つのメモリーグループ（たとえば要素数３２個）を１つの背番号グループ（たとえば要素数４０９６）に割り当て、探索で出てきたもの順にメモリーに記録してゆくことにする。
即ち図の主メモリー部分である。
このようにすれば当然メモリーは減少します。
また、３２個ぐらいであれば、再度アクセスするときに端から順次全部照合していても時間はかかりません。
問題は３２個で納まるかと言うことです。
そこで３２個でおさまらない例外的な場合に備えて、全部まとめてた例外メモリを容易しておき、ここに全部入れてしまいます。
【メモリーの圧縮詳細】
図６にこのプログラムのメモリー割付の方法の詳細を示します。
２のべき乗値から１％ぐらい小さい素数Zを用いて背番号の集合をmod ZでZ個の類に分け、これに少数（３２個）のメモリーを対応させています。
メモリーの属性値（手順数）がどの背番号のものか照合するために各メモリーには
[背番号／Z]の値を２バイト整数で記録しておきます。
例外が出た場合は例外メモリの方に入れますが、再アクセス時の背番号照合のために、背番号をそのまま記憶する領域を別途設置してあります。
【探索方法】
最初の状態から初めて、１手で到達するもののリスト、２手で到達するもののリスト、。。。。と言う風に順次探索してリストを作って行きます。
つまり、メモリー空間上に手順数の等高線を低い方から書いて行く感じです。
図５参照。
そして最終状態の背番号に達したら、終了です。
これで最小手順数がきまります。
実際の手順は、最終状態から逆にたどって、初期状態にたどり着くことで再現することができます。
なお、等手順数(手数T)の背番号のリストは各背番号のメモリーに用意されたリンク（次）により、等手数線ヘッダR[T]から繋がっています。
図６参照。
【情勢判断の例】
２／２０のプログラムでは「情勢判断」は入れていませんでした。
それはこの問題の場合、前にも申しましたが探索範囲があまり広がらないので、効果が少ないと考えられるからです。
（注：手数に対しE（指数的増加）問題の場合は効果絶大）
しかし実際に下記の方法を加えてみると予想外の効果がありました。
即ち例外メモリが殆ど使われなくなったのです。
このため２／２０ソフトに比べ、さらにメモリーが圧縮可能となり、
N=9まで全部RAM（私のPCは１２８MB）上で計算できるので、圧倒的に早くなりました。
HDアクセスのため１晩（実際は２時間）かかっていたのが１０秒程度になってしまいました。
方法は下図に示すとおりです。
必ず通らなければならないパターン（ホモタイプ、ヘテロタイプ）に着目し、ヘテロタイプからゴールの方がホモタイプからゴールより近い（漸化的に証明可能だがここでは省略）ので、もし初期状態からの探索でヘテロに早く到着すれば、広がった探索範囲を一旦１点に絞りこみ探索時間を短縮できます。
清川手順はヘテロ通過ですからこの賭けは勝算があり、実際N=9までは成功しています。
【新プログラム】
情勢判断を追加し、メモリ関係パラメータを調整したソフト１７ｋBを添付します。
なお、公開用に不要な変数などを削除・整理し、変数名を長くかつ統一し、少し解読しやすくしたつもりです。
【計算結果】
下表参照。PIII／５００MHｚ／１２８MB仕様
【P.S.】
CPU時間的にはまだまだ計算できそうです。
CPU時間は６Nに比例すると予測されるからです。
問題はメモリですが、あと４分の１にはできるでしょう。
総合するとこの方法では、N=10までは確実だがN=11はメモリ限界でできなさそうです。
◆広島県 清川 育男 さんからのコメント
「変形ハノイの塔」N=5 Y.M.Ojisan さん の解答が正しいことを確認できました。
中間点のヘテロ通過のその中間点も１つの関門になりますが、そこまでの手数が判れば総手数が解る漸化式を見つけました。
N=10 の結果が知りたいです。
◆ 解答Part１へ
◆ 問題へもどる
◆ 今週の問題へ
数学の部屋へもどる