骑士的目的地使用递归

Question

我一直在做一个项目，需要骑士（我们在开始时有它的坐标）前往目的地（也称为坐标）。我尝试使用递归来编写，但我的代码似乎没有做任何事情，而且我找不到问题所在。这是我的代码：

static bool Kelias(int dabX, int dabY, string[] Lenta, int dX, int dY, int indeksas)
{
    if (dabX == dX && dabY == dY)
        return true;
    if (!Lenta[dabY][dabX].Equals('0'))
    {
        return false;
    }
    if (indeksas > 0)
    {
        StringBuilder naujas = new StringBuilder(Lenta[dabY]);

        naujas[dabX] = (char)indeksas;

        Lenta[dabY] = naujas.ToString();
    }

    // aukstyn desinen
    if (GaliJudeti(dabX + 2, dabY + 1)
            && Kelias(dabX + 2, dabY + 1, Lenta, dX, dY, indeksas + 1))
    {
        return true;
    }
    // aukstyn desinen
    if (GaliJudeti(dabX + 1, dabY + 2)
            && Kelias(dabX + 1, dabY + 2, Lenta, dX, dY, indeksas + 1))
    {
        return true;
    }
    // aukstyn kairen
    if (GaliJudeti(dabX - 1, dabY + 2)
            && Kelias(dabX - 1, dabY + 2, Lenta, dX, dY, indeksas + 1))
    {
        return true;
    }
    // aukstyn kairen
    if (GaliJudeti(dabX - 2, dabY + 1)
            && Kelias(dabX - 2, dabY + 1, Lenta, dX, dY, indeksas + 1))
    {
        return true;
    }

    // zemyn kairen
    if (GaliJudeti(dabX - 2, dabY - 1)
            && Kelias(dabX - 2, dabY - 1, Lenta, dX, dY, indeksas + 1))
    {
        return true;
    }

    // zemyn kairen
    if (GaliJudeti(dabX - 1, dabY - 2)
            && Kelias(dabX - 1, dabY - 2, Lenta, dX, dY, indeksas + 1))
    {
        return true;
    }

    // zemyn desinen
    if (GaliJudeti(dabX + 1, dabY - 2)
            && Kelias(dabX + 1, dabY - 2, Lenta, dX, dY, indeksas + 1))
    {
        return true;
    }

    // zemyn desinen
    if (GaliJudeti(dabX + 2, dabY - 1)
            && Kelias(dabX + 2, dabY - 1, Lenta, dX, dY, indeksas + 1))
    {
        return true;
    }

    indeksas--;
    return false;
}

static bool GaliJudeti(int x, int y)
{
    if (x >= 0 && y >= 0 && x < 8 && y < 8)
    {
        return true;
    }
    return false;
}

关于变量和我正在尝试做的事情的一些解释：

dabX, dabY - 是骑士的当前坐标

Lenta - 是我的板（它是一个字符串，因为我正在从 txt 文件中读取起始数据）。

dX, dY - 是目标目的地

indeksas - 跟踪到达目的地需要走多少步

现在第一个 if 检查我们是否到达目的地。第二个检查我们行进的坐标是否也没有被阻塞（因为我的板是由零组成的，因为它在一个字符串中，我们检查符号是否等于它，因为如果它不等于路径被阻塞）。然后我们转向骑士可能的动作，这是该方法的主要部分。

还有另一个名为 GaliJudeti 的函数，它会检查我们是否在棋盘 (8x8) 的边界内。

Answer 1

您的代码看起来一定可以工作。我刚刚使用了你的算法，稍微修改了一下，一切正常。我用了类让它看起来更一般，其实都一样

static bool MoveFirstSolution(Knight knight, Board board, Point destination, int counter, Trace trace)
{
    board.Set(knight.X, knight.Y, counter);
    if (knight.IsInPoint(destination))
    {       
        //trace is an object to store found path         
        trace.Counter = counter;
        trace.Board = board;                   
        return true;
    }
    counter++;
    Point[] moves = knight.AllPossibleMoves();
    foreach (Point point in moves)
    {
        if (board.Contains(point) && board.IsFree(point))
        {
            knight.MoveTo(point);
            if (MoveFirstSolution(knight, board.GetCopy(), destination, counter, trace))
            {
                return true;
            }
        }
    }
    return false;
}

但是，这个函数会找到第一个解并停止。如果您想要最佳解决方案，即使找到答案也需要继续搜索。这是执行它的函数：

static void Move(Knight knight, Board board, Point destination, int counter, Trace trace)
{
    board.Set(knight.X, knight.Y, counter);
    if (knight.IsInPoint(destination))
    {
        if (!trace.IsShorterThen(counter))
        {
            trace.Counter = counter;
            trace.Board = board;
            Console.WriteLine("Better trace");
            Console.WriteLine("Counter: " + trace.Counter);
            Console.WriteLine(trace.Board);
        }
        return;
    }
    counter++;
    Point[] moves = knight.AllPossibleMoves();
    foreach(Point point in moves)
    {
        if (board.Contains(point) && board.IsFree(point))
        {
            knight.MoveTo(point);
            Move(knight, board.GetCopy(), destination, counter, trace);
        }
    }
}

每次找到更好的跟踪时都会覆盖跟踪。但是对于 8 * 8 的板来说，执行起来确实需要很长时间。

对于您的代码，我建议尝试 Console.WriteLine() 以确保一切正常。也许，您 Lenta 没有像您预期的那样被覆盖，这会导致无限递归。尝试跟踪函数的每个操作，以找到问题的根源。

这是我的主要功能：

static void Main(string[] args)
{
    Knight knight = new Knight(0, 0);
    Board board = new Board(8, 8);
    Point destination = new Point(0, 4);
    Trace bestTrace = new Trace();
    MoveFirstSolution(knight, board, destination, 1, bestTrace);

    Console.WriteLine("Best trace: " + bestTrace.Counter);
    Console.WriteLine(bestTrace.Board);
    Console.ReadLine();
}

和其余必需的类，因此您可以尝试将其作为工作示例。

class Trace
{
    public Trace()
    {
        this.Board = null;
        this.Counter = -1;
    }
    public Trace(Board board, int counter)
    {
        this.Board = board;
        this.Counter = counter;
    }
    public bool IsShorterThen(int counter)
    {
        return this.Counter > 0 && this.Counter <= counter;
    }
    public Board Board { get; set; }
    public int Counter { get; set; }
}
class Board
{
    private int[][] _board;
    public Board(int N, int M)
    {
        this._board = new int[N][];
        for (int i = 0; i < N; i++)
        {
            this._board[i] = new int[M];
            for (int j = 0; j < M; j++)
            {
                this._board[i][j] = 0;
            }
        }
    }
    public int N
    {
        get
        {
            return this._board.Length;
        }
    }
    public int M
    {
        get
        {
            return this._board.Length > 0 ? this._board[0].Length : 0;
        }
    }
    public Board GetEmptyCopy()
    {
        return new Board(this.N, this.M);
    }
    public Board GetCopy()
    {
        Board b = new Board(this.N, this.M);
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < M; j++)
            {
                b.Set(i, j, this.Get(i, j));
            }
        }
        return b;
    }
    public bool Contains(int i, int j)
    {
        return (i >= 0) && (i < this.N) && (j >= 0) && (j < this.M);
    }
    public bool Contains(Point point)
    {
        return this.Contains(point.X, point.Y);
    }
    public bool IsFree(int i, int j)
    {
        return this._board[i][j] == 0;
    }
    public bool IsFree(Point point)
    {
        return this.IsFree(point.X, point.Y);
    }
    public void Set(int i, int j, int val)
    {
        this._board[i][j] = val;
    }
    public int Get(int i, int j)
    {
        return this._board[i][j];
    }
    public override string ToString()
    {
        string str = "";
        for (int i = 0; i < this.N; i++)
        {
            for (int j = 0; j < this.M; j++)
            {
                str += String.Format("{0, 3}", this._board[i][j]);
            }
            str += "\r\n";
        }
        return str;
    }
}
class Knight
{        
    public Knight(int x, int y)
    {
        this.X = x;
        this.Y = y;
    }
    public int X { get; private set; }
    public int Y { get; private set; }
    public Point[] AllPossibleMoves()
    {
        Point[] moves = new Point[8];
        moves[0] = new Point(this.X + 1, this.Y + 2);
        moves[1] = new Point(this.X + 1, this.Y - 2);
        moves[2] = new Point(this.X + 2, this.Y + 1);
        moves[3] = new Point(this.X + 2, this.Y - 1);
        moves[4] = new Point(this.X - 1, this.Y + 2);
        moves[5] = new Point(this.X - 1, this.Y - 2);
        moves[6] = new Point(this.X - 2, this.Y + 1);
        moves[7] = new Point(this.X - 2, this.Y - 1);
        return moves;
    }
    public bool IsInPoint(int x, int y)
    {
        return this.X == x && this.Y == y;
    }
    public bool IsInPoint(Point point)
    {
        return this.IsInPoint(point.X, point.Y);
    }
    public void MoveTo(int x, int y)
    {
        this.X = x;
        this.Y = y;
    }
    public void MoveTo(Point point)
    {
        this.MoveTo(point.X, point.Y);
    }
}
class Point
{
    public Point(int x, int y)
    {
        this.X = x;
        this.Y = y;
    }
    public int X { get; private set; }
    public int Y { get; private set; }
}

骑士的目的地使用递归

Knight's destination using recursion

c#

recursion

backtracking

chess