その手のアルゴリズムはゲーム系プログラミングのサイトなんかにもにあったな……
ヘクス 移動 範囲 アルゴリズム あたりでｸﾞｸﾞﾙと吉

探索済みかつ遠回りして来たマスに辿り着いたらそのルートはそこでおしまい、
とすると余計な計算を省ける。