c# - ヒルクライムを使用した 8 パズルは常に無限ループに陥る

Question

山登りでランダムな 8 パズルを解くアルゴリズムを書こうとしています。最初の選択、最良の選択、およびランダムな再起動を使用して作成しましたが、常に無限ループに陥ります。それを防ぐ方法はありますか? また、ランダムなパズルを生成するときに、アルゴリズムを使用して、生成されたすべてのパズルが解けるようにしました。したがって、可解性の問題はありません。これは、ほぼ 100% のパズルで 8 つのパズルを解決するランダム リスタート タイプの関数です。

public static bool HillClimbingRandomRestart(int[,] _state)
{
    int[,] _current = _state;
    int hMax = Problem.GetHeuristic(_state);
    int Counter = 0;
    int _h = hMax;
    int[,] _best = _current;
    int[,] _next = _current;
    while (Counter < 100000)
    {
        Counter++;
        if (isGoal(_current))
            return true;
        foreach (Move suit in Enum.GetValues(typeof(Move)))
        {
            _next = Problem.MoveEmptyTile(_current, suit);
            if (_next == null)
                continue;
            _h = Problem.GetHeuristic(_next);
            if (_h < hMax)
            {
                hMax = _h;
                _best = _next;
            }
        }
        if (_current == _best)
        {
            Random rnd = new Random();
            int[,] _nextRandom = Problem.MoveEmptyTile(_current, (Move)rnd.Next(4));
            while(_nextRandom==null)
                _nextRandom = Problem.MoveEmptyTile(_current, (Move)rnd.Next(4));
            _current = _nextRandom;
        }
        else
            _current = _best;
        hMax = Problem.GetHeuristic(_current);
    }
    return false;
}