骑士的目的地使用递归
Knight's destination using recursion
我一直在做一个项目,需要骑士(我们在开始时有它的坐标)前往目的地(也称为坐标)。
我尝试使用递归来编写,但我的代码似乎没有做任何事情,而且我找不到问题所在。这是我的代码:
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) 的边界内。
您的代码看起来一定可以工作。我刚刚使用了你的算法,稍微修改了一下,一切正常。我用了类让它看起来更一般,其实都一样
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; }
}
我一直在做一个项目,需要骑士(我们在开始时有它的坐标)前往目的地(也称为坐标)。 我尝试使用递归来编写,但我的代码似乎没有做任何事情,而且我找不到问题所在。这是我的代码:
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) 的边界内。
您的代码看起来一定可以工作。我刚刚使用了你的算法,稍微修改了一下,一切正常。我用了类让它看起来更一般,其实都一样
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; }
}