c# - Knights Tour 递归 C# 我做这些事情的方式有问题

Question

class Knight
{
    public static readonly double LegalDistance = Math.Sqrt(5);
    public Stack<Field> Steps { get; set; }

    private static readonly List<Field> board = Board.GameBoard;
    private static List<Field> fields;       

    private static readonly Random random = new Random();
    private static readonly object synLock = new object(); 

    public Knight(Field initial)
    {
        Steps = new Stack<Field>();
        Steps.Push(initial);
    }

    public void Move()
    {
        Field destination = Choose();

        if (destination == null)
        {
            return;
        }

        Console.WriteLine("Moving from " + GetPosition().GetFieldName() + " to " + destination.GetFieldName());
        Steps.Push(destination);
    }

    public Field Back()
    {
        Field from = Steps.Pop();
        Console.WriteLine("Moving back from " + from.GetFieldName() + " to " + GetPosition().GetFieldName());

        return from;
    }

    public Field Choose()
    {
        List<Field> legalMoves = Behaviour();

        legalMoves.RemoveAll(field => Steps.Contains(field, new FieldValueComparer()));

        if (legalMoves.Count == 0)
        {
            return null;
        }

        Field theChoosenOne;

        int index;
        lock (synLock)
        {
            index = random.Next(0, legalMoves.Count);
        }

        theChoosenOne = legalMoves.ElementAt(index);


        return theChoosenOne;
    }

    private List<Field> Behaviour()
    {
        fields = new List<Field>();
        fields.AddRange(board);

        for (int i = fields.Count - 1; i >= 0; i--)
        {
            double actualDistance = fields[i].GetDistance(GetPosition());
            if (!actualDistance.Equals(LegalDistance))
            {
                fields.Remove(fields[i]);
            }
        }

        return fields;
    }
    public List<Field> GetSteps()
    {
        return Steps.ToList();
    }

    public Field GetPosition()
    {
        return Steps.Peek();
    }
}

这就是我做事的方式。问题是，我缺少一些关键功能，因为在给定步数较低时它会回溯到开始，在步数较高时会导致 StackOverFlow。

下面还有一些其他的函数可以让你明白我想做什么:计算距离:

public double GetDistance(Field other)
{
       return Math.Sqrt(Math.Pow(other.X - X, 2) + Math.Pow(other.Y - Y, 2));
}

寻找路径:

class PathFinder
    {
        public static void FindPath(Knight knight)
        {

            if (knight.Steps.Count != 20)
            {
                knight.Move();

                FindPath(knight);

                knight.Back();
            }
        }
    }

Answer 1

您的路径搜索本质上是随机游走。在大板上，无论如何这可能需要一段时间。

关于 StackOverflow:请注意，当无处可去时，您不会在 Move() 上推送任何内容。因此，在递归调用 FindPath() 时，仍然会有相同的 knight.Steps.Count、相同的位置、相同的 null 返回在 Choose()... 上，依此类推，直到堆栈空间不足。

明显的解决方法是将 bool 返回值添加到 Move() 以指示是否有 任何移动。除非使用随机移动背后有实际原因，否则建议使用更具确定性的搜索算法。