https://www.ap-siken.com/kakomon/30_haru/pm03.html

「現在のマスの移動順序を取り消して、マスを通過していない状態に戻す」というⅱ-3の記述がある意味が分かりません（解答欄キの部分です）。

巡回問題というと難しそうですが、チェスのナイトの駒を使ったパズルですね。
スタートからナイトが移動できるルールで駒を動かし、全てのマスを1回ずつ通りなさいという問題です。

このアルゴリズムは、比較的人間の思考法に近い形でできているように思います。
次のような感じで進みます。（若干簡略化しています。ご容赦ください）
(1)ナイトのルールで次に移動する空きマス（まだ通ってないマス）を探す
(2)移動する
(3)移動後、今のマスに今何番目の移動か書き込む
(4)次の移動できるマスを探す（以降(2)から繰り返し）

ここで、まだ何も書き込んでいない空きマスがあり、かつ(4)での次の移動先がない場合、今いる場所に駒を進めたこと自体が間違っている、ということになりますね？
この場合、(2)(3)をなかったことにして一マス分移動を巻き戻し、(2)ではない別の移動先からやり直す必要があります。

(ⅱ-3)「現在のマスの移動順序を取り消して、マスを通過していない状態に戻す」は、上記でいう(3)の「このマス使いましたよ」チェックを取り消す処理です。
その後の、
(ⅱ-4)「再帰関数 search の呼出し元へ戻る」が、(2)に来たことを忘れて(1)に戻ることを指します。