c# - 8-Puzzle 使用爬山总是陷入无限循环

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;
}