骑士巡游棋盘格：编码挑战
4.99/5 (20投票s)
本文是CodeProject每周挑战“棋盘上的马”的解决方案。
引言
本文是CodeProject每周编码挑战的答案：棋盘上的马。[^] 该挑战是为马踏棋盘[^]编写一个（方形）国际象棋棋盘上的程序。
我的程序完全解决了挑战，但包含了一些额外功能
- 它不仅适用于8x8棋盘，还可以用于任何方形棋盘（其中n是行/列的数量，且n >= 5）。
- 仅仅输出一系列坐标对我们来说没有什么意义，除了坐标本身。因此，我的应用程序支持绘制马踏棋盘：可以是动画GIF，也可以是一张包含所有路径线的图像。
背景
我的解决方案使用了沃恩斯多夫规则。这是一种寻找马踏棋盘的启发式方法，其工作原理如下：我们将马移动到具有最少后续目的地格子的位置。如果这听起来很令人困惑，这里有一张图片可以让你更清楚地理解。
马的目的地和（来自两个格子的）后续目的地。棋盘：lichess.org[^]
绿色箭头是马可能的目的地。蓝色箭头（我只从两个目的地格子画了，但你应该能明白意思）显示了在按照相应绿色箭头移动后，合法的马步。c4-a3移动有3个后续目的地，c4-e5移动有7个。沃恩斯多夫规则说这里应该选择c4-a3，因为3 < 7。还要注意，对于目的地（“绿色箭头”）和后续目的地（“蓝色箭头”），已经访问过的格子应该被排除。
在上面的图片中，如果我们从a5画蓝色箭头，我们会得到3个目的地，就像从b3一样。选择哪个格子？沃恩斯多夫规则没有指定。我使用的是以下平局规则：我们选择离中心最远的格子。“这样，路径往往会靠近棋盘边缘，从而降低棋盘被分成两个或更多独立未覆盖部分的明显风险。”
这个平局规则是否将陷入困境的风险降至0%？不，它仍然可能发生，那时我的应用程序会告诉你。对于非方形棋盘，陷入困境的风险似乎非常高。经过多次尝试，我无法找到一个非方形棋盘+一个起始位置，它不会陷入困境。我猜沃恩斯多夫规则加上这个平局规则对非方形棋盘效果不太好，但对方形棋盘效果非常好，所以我的应用程序只接受方形棋盘。然而，我的大部分代码仍然支持不同的宽度和高度，因为我在代码接近完成时才观察到这一点。
同样非常重要的是要注意，在N x N棋盘上，如果N是奇数，你的马必须从一个深色格子开始才能完成马踏棋盘。（如果你不确定奇数棋盘上的“深色格子”是什么：角落属于深色格子）
马踏棋盘计算的实现
Coordinate 类
这个类只不过是一个辅助类，它有一个 `X` 和 `Y` 属性，以及一些相等方法。它的目的是存储其他类使用的坐标。关于这个类没有什么可说的。
public class Coordinate : IEquatable<Coordinate>
{
public int X
{
get;
private set;
}
public int Y
{
get;
private set;
}
public Coordinate(int x, int y)
{
X = x;
Y = y;
}
public override string ToString()
{
return string.Format("({0},{1})", X, Y);
}
public override bool Equals(object obj)
{
if (obj == null || !(obj is Coordinate))
{
return false;
}
return Equals(obj as Coordinate);
}
public bool Equals(Coordinate other)
{
return other != null && this.X == other.X && this.Y == other.Y;
}
public override int GetHashCode()
{
return new { X = X, Y = Y }.GetHashCode();
}
}
KnightBoard 类
KnightBoard 类是马踏棋盘计算发生的地方。让我们先回顾一下类中声明的字段和属性。
BitArray visited;
public int Width { get; private set; }
public int Height { get; private set; }
public Coordinate KnightPosition { get; private set; }
public List<Coordinate> Path { get; private set; }
int[][] directions = new int[][]
{
new int[] { 1, 2 },
new int[] { 2, 1 },
new int[] { -1, -2 },
new int[] { -2, -1 },
new int[] { 2, -1 },
new int[] { -2, 1 },
new int[] { 1, -2 },
new int[] { -1, 2 }
};
visited是一个System.Collections.BitArray，其内容指示哪些格子已经被访问过，哪些没有。Width和Height不言自明。KnightPosition保存马的“当前位置”。在构造函数中，它被设置为起始格子。当实际进行马踏棋盘计算时，它会经常被改变。Path是一个Coordinate对象列表，它保存马踏棋盘的路径。在调用MakeTour计算方法后，它将成为完整的马踏棋盘路径。如果你想知道为什么我们在有Path的情况下还需要visited，答案很简单：我们不应该使用Path来检查一个格子是否已被访问，因为List<T>.Contains比检查BitArray中的相应位要慢得多。这种差异在较大的棋盘上尤其明显。directions保存马相对于给定格子可以移动的所有可能格子。
构造函数接受三个参数：width、height（因为应用程序只接受相同的宽度和高度，所以它们是相同的）和 knightPos，它指示马的起始位置。
public KnightBoard(int width, int height, Coordinate knightPos)
{
visited = new BitArray(width * height);
Width = width;
Height = height;
visited[ArrayPositionFromCoordinate(knightPos)] = true;
Path = new List<Coordinate>();
Path.Add(knightPos);
KnightPosition = knightPos;
}
构造函数除了设置上面解释的字段和属性的值之外，没有做其他事情。
在构造函数之后，你会看到一个 ArrayPositionFromCoordinate 方法。我们的 BitArray visited 是一个一维数组，但棋盘是二维的。这个方法将二维坐标转换为一维坐标，以便 BitArray 可以使用它。
int ArrayPositionFromCoordinate(Coordinate pos)
{
if (pos.X >= Width || pos.Y >= Height || pos.X < 0 ||
pos.Y < 0) throw new ArgumentException();
return (pos.Y * Height) + pos.X;
}
如果你继续阅读代码，你会遇到 TourExists 方法。尽管实际上，KnightBoard 实例只会看到方形棋盘，但该方法仍然支持矩形棋盘。存在性的规则取自关于马踏棋盘的维基百科页面[^]
- 如果较小的维度至少为五，则存在马踏棋盘。它可能是开放的（闭合意味着马可以从最后一个路径格子移动到第一个；开放意味着它不能）。
- 如果不是至少五，则可能存在闭合马踏棋盘，除非满足以下一个或多个条件：
- 两个维度都是奇数。
- 较小的维度是1、2或4。
- 较小的维度是3 *并且* 较大的维度是4、6或8。
public bool TourExists()
{
int m = Math.Min(Width, Height);
int n = Math.Max(Width, Height);
if (m >= 5) return true; // a tour exists, and it's possibly an open one
// Otherwise, check that there is a closed tour.
if (m % 2 == 1 && n % 2 == 1)
return false;
if (m == 1 || m == 2 || m == 4)
return false;
if (m == 3 && (n == 4 || n == 6 || n == 8))
return false;
// if any of the three conditions is true, a closed tour is impossible.
return true;
}
TourExists 在应用程序开始时（在接受输入后）被调用，以告知用户马踏棋盘是否在理论上不可能。
KnightBoard 的下一个方法是 GetValidDestinations 方法。它使用 directions 数组生成目的地，并且只返回那些在棋盘边界内且马尚未访问过的格子。这是一个简单的 foreach 循环遍历所有方向，然后检查它是否在数组边界内，然后检查它是否尚未被访问。该方法接受一个“origin”参数，并且当目标等于“origin”时，它也不会返回目标。
List<Coordinate> GetValidDestinations(Coordinate origin)
{
List<Coordinate> result = new List<Coordinate>();
foreach (int[] dir in directions)
{
int newX = origin.X + dir[0];
int newY = origin.Y + dir[1];
if (newX < 0 || newY < 0 || newX >= Width || newY >= Height)
{
continue;
}
Coordinate newCo = new Coordinate(newX, newY);
if (visited[ArrayPositionFromCoordinate(newCo)] || newCo.Equals(origin))
{
continue;
}
result.Add(newCo);
}
return result;
}
在“背景”中，我提到了使用一个平局规则：在应用沃恩斯多夫规则后出现平局的情况下，我选择离中心最远的格子。中心通过 (Width - 1) / 2.0 和 (Height - 1) / 2.0（减一，因为数组是从零开始的）计算，然后我使用距离公式 \(\sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}\)，但因为我只是在比较距离，所以我不必进行平方根运算。这个计算由 FarthestFromCenter 方法执行。
Coordinate FarthestFromCenter(List<Coordinate> options)
{
double centerX = (Width - 1) / 2.0;
double centerY = (Height - 1) / 2.0;
Dictionary<Coordinate, double> coordinatesWithDistanceSquared =
options.ToDictionary(x => x, c => Math.Pow(centerX - c.X, 2) + Math.Pow(centerY - c.Y, 2));
return coordinatesWithDistanceSquared.Aggregate((l, r) => l.Value > r.Value ? l : r).Key;
}
现在我们有了所有辅助方法。是时候进行实际计算了：MakeTour 方法！这个方法运行一个循环，直到 Path.Count 小于棋盘上的格子数量（请注意，我们不需要减一，因为我们的初始位置也在 Path 中）。
while (Path.Count < Width * Height)
在循环内，我们首先初始化一个 Dictionary，其中包含目的地及其“权重”，即后续移动的数量。正如我在背景中说的，权重越低越好。然后我们创建一个 chosen 变量供稍后使用。它最初设置为 null。
Dictionary<Coordinate, int> weightedCoordinates = new Dictionary<Coordinate, int>();
Coordinate chosen = null;
是时候进行实际工作了。我们遍历所有有效目的地，并为每个目的地获取从该格子出发的有效目的地，然后计算其数量作为权重。
foreach (Coordinate co in GetValidDestinations(KnightPosition))
{
int optionsFromNewDestination = GetValidDestinations(co).Count;
weightedCoordinates.Add(co, optionsFromNewDestination);
}
如果 weightedCoordinates 的数量为零，则 GetValidDestinations 找不到任何有效项，这意味着马踏棋盘陷入了困境。MakeTour 返回一个 bool，因此在这种情况下我们返回 false。
if (weightedCoordinates.Count == 0)
{
return false;
}
然后我们只保留权重最低的格子，如果需要的话，对其应用平局规则。
int min = weightedCoordinates.Min(x => x.Value);
List<Coordinate> allMin = weightedCoordinates.Where
(x => x.Value == min).Select(x => x.Key).ToList();
在得到 allMin 之后，我们需要检查它是否只有一个元素。如果只有一个元素，我们就选择该元素。如果元素不止一个，我们就运行平局方法。
if (allMin.Count == 1)
{
chosen = allMin[0];
}
else
{
chosen = FarthestFromCenter(allMin);
}
一旦选定了格子，我们就将其添加到路径中，更新 visited 并替换 KnightPosition。
visited[ArrayPositionFromCoordinate(chosen)] = true;
KnightPosition = chosen;
当循环条件变为 false 时，我们返回 true，因为我们成功找到了一个马踏棋盘。
}
return true;
完整的函数如下所示：
public bool MakeTour()
{
while (Path.Count < Width * Height)
{
Dictionary<Coordinate, int> weightedCoordinates = new Dictionary<Coordinate, int>();
Coordinate chosen = null;
foreach (Coordinate co in GetValidDestinations(KnightPosition))
{
int optionsFromNewDestination = GetValidDestinations(co).Count;
weightedCoordinates.Add(co, optionsFromNewDestination);
}
if (weightedCoordinates.Count == 0)
{
return false;
}
int min = weightedCoordinates.Min(x => x.Value);
List<Coordinate> allMin =
weightedCoordinates.Where(x => x.Value == min).Select(x => x.Key).ToList();
if (allMin.Count == 1)
{
chosen = allMin[0];
}
else
{
chosen = FarthestFromCenter(allMin);
}
Path.Add(chosen);
visited[ArrayPositionFromCoordinate(chosen)] = true;
KnightPosition = chosen;
}
return true;
}
BoardDrawing.Draw: 马踏棋盘的图像表示
我们的下一个类是 static 类 BoardDrawing。它有两个方法：Draw，用于绘制路径的静态图像，以及 CreateGif，它使用 Draw 和 Magick.NET 创建路径的 GIF。但我稍后会详细介绍。
Draw 使用 .NET 的 System.Drawing。它创建图像的步骤如下：
- 该方法接受 6 个参数：
List<Coordinate> path：要绘制的路径int width：图像的widthint height：图像的heightint boardWidth：棋盘的width（列数）int boardHeight：棋盘的height（行数）string file：要保存到的文件路径
- 我们创建一个名为
boardBitmap的Bitmap实例，并从该bitmap获取一个名为g的Graphics对象。 - 我们使用
g.Clear将整个Bitmap设为白色而不是黑色。 - 我们计算棋盘网格的垂直和水平线数。边框不计入，因为它们稍后会单独绘制。线数就是棋盘宽度和高度减一。还计算了线之间的距离。这是
(width - 2) / boardWidth（或 height）。为什么减二？因为边框将是1像素宽，我不想将其计入距离。 - 边框使用
g.DrawRectangle绘制，网格使用g.DrawLine在循环中绘制。 - 我们构造一个
PointF数组，它将被馈送到g.DrawLines。这将是我们马踏棋盘的路径。我们使用一个for循环，在该循环内，我们计算每个路径坐标在图像上的 x 和 y 坐标。我们希望这个坐标显然是格子的中心。x 坐标的计算方法是取垂直线距离，乘以棋盘上的 x 坐标，再加上一半的垂直线距离。y 坐标同理，但使用水平线距离。然后我们就得到了路径中下一个格子的中心坐标。 - 在
for循环的第一次迭代中，我们在起始格子绘制一个较大的圆圈，以表示它是起始格子。 - 在循环外部，我们使用
g.DrawLines绘制PointF数组中的所有线。 - 我们将
Bitmap保存到文件。
这是代码
public static void Draw
(List<Coordinate> path, int width, int height, int boardWidth, int boardHeight, string file)
{
using (Bitmap boardBitmap = new Bitmap(width, height))
{
using (Graphics g = Graphics.FromImage(boardBitmap))
{
g.Clear(Color.White);
float lineWidth = 1f;
int verticalLineCount = boardWidth - 1;
float verticalLineDistance = (width - 2 * lineWidth) / boardWidth;
int horizontalLineCount = boardHeight - 1;
float horizontalLineDistance = (height - 2 * lineWidth) / boardHeight;
g.DrawRectangle(new Pen(Color.Black, 1), 0, 0,
width - lineWidth, height - lineWidth);
for (int i = 1; i <= verticalLineCount; i++)
{
g.DrawLine(new Pen(Color.Black, lineWidth),
new PointF(i * verticalLineDistance, 0),
new PointF(i * verticalLineDistance, height - lineWidth));
}
for (int i = 1; i <= horizontalLineCount; i++)
{
g.DrawLine(new Pen(Color.Black, lineWidth),
new PointF(0, i * horizontalLineDistance),
new PointF(width - lineWidth, i * horizontalLineDistance));
}
PointF[] linePoints = new PointF[path.Count];
for (int i = 0; i < linePoints.Length; i++)
{
float x = verticalLineDistance * path[i].X + verticalLineDistance / 2;
float y = horizontalLineDistance * path[i].Y + horizontalLineDistance / 2;
linePoints[i] = new PointF(x, y);
if (i == 0)
{
float ellipseWidth = verticalLineDistance / 3;
float ellipseHeight = horizontalLineDistance / 3;
g.FillEllipse(Brushes.Blue, x - (ellipseWidth / 2),
y - (ellipseHeight / 2), ellipseWidth, ellipseHeight);
}
}
if (linePoints.Length >= 2)
{
g.DrawLines(new Pen(Color.Blue, 2), linePoints);
}
}
boardBitmap.Save(file);
}
}
BoardDrawing.CreateGif: 路径的动画 GIF
要创建 GIF，我们使用 Magick.NET，这是 ImageMagick 的 .NET 库。它可在 NuGet 上找到[^]。首先，我们使用 Draw 为每个步骤创建一个图像，我们只需要传递 Coordinate 路径的一部分。我们将图像存储在临时的 *AppData* 文件夹中，并告诉 ImageMagick 使用哪些图像。请注意，如果图像太多，这将不起作用……我尝试了一个 50x50 的国际象棋棋盘，过了一段时间，Bitmap 构造函数抛出了一个 ArgumentException，尽管我的参数是有效的。我猜它只是内存不足。不过，对于较小的国际象棋棋盘，这效果很好。例如，25x25 的国际象棋棋盘上的 500x500 GIF 仍然有效。我没有进行过度的测试来确定限制，因为对于如此大的国际象棋棋盘，速度并不快。
Magick.NET GIF 生成的工作原理如下：您可以创建一个 MagickImageCollection，调用 .Add 添加一个文件，然后为所有图像指定“动画延迟”。完成后，我将最大颜色数设置为 256 以减小文件大小（反正它也不太丰富多彩），我还调用了 .Optimize。
GIF 生成后，临时文件的目录将被删除。
public static void CreateGif
(List<Coordinate> path, int width, int height, int boardWidth, int boardHeight, string file)
{
string tempDir = Path.Combine(Path.GetTempPath(),
"KnightsTour", "temp-" + Guid.NewGuid().ToString());
Directory.CreateDirectory(tempDir);
using (MagickImageCollection collection = new MagickImageCollection())
{
for (int i = 0; i < path.Count; i++)
{
string filename = Path.Combine(tempDir, i + ".gif");
Draw(path.Take(i + 1).ToList(), width, height, boardWidth, boardHeight, filename);
collection.Add(filename);
collection[i].AnimationDelay =
i != path.Count - 1 ? 50 : 300; // 3 seconds if last frame, otherwise 0.5
}
QuantizeSettings settings = new QuantizeSettings();
settings.Colors = 256;
collection.Quantize(settings);
collection.Optimize();
collection.Write(file);
}
Directory.Delete(tempDir, true);
}
Program.Main: 获取输入并运行代码
现在我们有了所有必需的类。是时候编写代码使应用程序在运行时执行某些操作了。它需要以下输入：
- 国际象棋棋盘的
Width和height - 起始格子
- 您是否想要输出 GIF、静态图像或无图像。如果您确实想要图像，它会询问
width和height。
没有输入验证；这并不是一个有趣的东西来编写，而且它也不是挑战的一部分。
这是 Main 中负责处理输入的代码：
Console.Write("Width and height of chess board: ");
int width, height;
width = height = int.Parse(Console.ReadLine());
Console.Write("Starting square (format: x,y ; zero-based): ");
string[] coordinateParts = Console.ReadLine().Split(new char[] { ',' }, 2);
Coordinate startingSquare = new Coordinate
(int.Parse(coordinateParts[0]), int.Parse(coordinateParts[1]));
Console.Write("Output image? (gif, final, none): ");
string outputImage = Console.ReadLine();
string outputImageFilePath = null;
int imageWidth = -1;
int imageHeight = -1;
if (outputImage == "gif" || outputImage == "final")
{
Console.Write("Output image file path? ");
outputImageFilePath = Console.ReadLine();
if (File.Exists(outputImageFilePath))
{
Console.WriteLine("WARNING! That file already exists,
so this application will overwrite it. Quit if you don't want to do this.");
}
Console.Write("Output image width? ");
imageWidth = int.Parse(Console.ReadLine());
Console.Write("Output image height? ");
imageHeight = int.Parse(Console.ReadLine());
}
然后，创建 KnightBoard 实例并尝试进行马踏棋盘计算。之后，它会打印坐标。
KnightBoard board = new KnightBoard(width, height, startingSquare);
if (!board.TourExists())
{
Console.WriteLine("There is no tour for this board.");
return;
}
if (!board.MakeTour())
{
Console.WriteLine(string.Join(" ", board.Path.Select(x => x.ToString())));
Console.WriteLine("I'm stuck :(");
return;
}
Console.WriteLine(string.Join(" ", board.Path.Select(x => x.ToString())));
如果您想要图像，它也会生成。
if (outputImage == "gif")
{
Console.WriteLine("Generating GIF...");
try
{
BoardDrawing.CreateGif(board.Path, imageWidth, imageHeight,
width, height, outputImageFilePath);
}
catch (ArgumentException)
{
Console.WriteLine("An ArgumentException occured.
It looks like this happens when the GIF generation takes too much memory. Sorry!");
}
Process.Start(outputImageFilePath);
}
else if (outputImage == "final")
{
Console.WriteLine("Generating image...");
BoardDrawing.Draw(board.Path, imageWidth, imageHeight, width, height, outputImageFilePath);
Process.Start(outputImageFilePath);
}
这是一次有趣的编码挑战 :D 感谢阅读！
历史
- 2017年3月11日：初始版本