良い方向を追い、一巡して確かめる

良くなった方向は、すぐもう一度試す

(4,7,2,8) → 63
X1を+1歩  → (6,7,2,8)  → 71  採用
同じ方向  → (8,7,2,8)  → 76  採用
同じ方向  → (10,7,2,8) → 72  不採用・戻る

ある方向で改善したら、別のカードに移る前に、まず同じ方向をもう一度試します。改善が続くかぎり繰り返します。せっかく見つけた良い傾向を、一歩だけで手放さないためです。

「戻る」とは、候補を現在地にしないこと

上の例の最後で、Scoreは76から72に下がりました。このとき「戻る」といっても、消しゴムで何かを消す必要はありません。悪化した候補(10,7,2,8)は記録票に履歴として残し、現在地カードを(8,7,2,8)のまま動かさない。それだけです。

盤面の候補欄と現在地欄を分けておけば、前の値を記憶しておく必要はなくなります。探索を支えるのは記憶力ではなく、手順を再現できる記録です。

行き詰まりは「一巡」で判定する

一巡 = いま使っている方向カード全部を、
       同じ現在地・同じ歩幅で一度ずつ試すこと

一つの方向で失敗しただけでは、行き詰まりとは言えません。手持ちの方向カードをすべて一度ずつ試し、どれも改善しなかったときに、初めて「この歩幅では行き詰まった」と判定します。歩幅を小さくするのは、そのあとです。

ただし、一巡の途中で改善が出たら、その候補が新しい現在地です。残りのカードを消化する必要はなく、一巡はそこで打ち切って、新しい現在地から仕切り直します。

方向カードの順番は固定しておく

軸方向なら、たとえば+X1, -X1, +X2, -X2, …のように、カードを並べる順番を決めておきます。順番が固定されていれば、まだ試していない方向がひと目で分かり、同じ方向を重複して試す事故も防げます。

例外は、改善した方向です。そのカードだけは列から抜き出し、改善が止まるまで連続で使います。止まったら、また列の先頭から一巡を始めます。