汉诺塔
4.83/5 (46投票s)
汉诺塔问题的解决方案。
引言
本文包含汉诺塔问题的递归解决方案。该应用程序使用 C# 编写，用户界面使用 Windows Forms 完成。
要求
- 使用 Windows Forms 对该谜题进行图形化表示。
- 用户应该能够选择使用 3、4、5、6 个盘片*来玩这个谜题。总是会有三根柱子**。
- 应用程序应该只允许有效的移动——由以下规则定义
- 一次只能移动一个盘片
- 你不能将一个较大的盘片放在一个较小的盘片上
- 应用程序必须有一个“演示”功能，应用程序将逐步向用户展示所选盘片数量的解决方案。
有关该谜题的更多信息，请参见：汉诺塔
* 盘片一词在整篇文章中用于描述谜题的可移动部分。
** 柱子一词用于描述包含盘片的桩子。
设计
我希望 UI 和后端之间有一个清晰的分离。我创建了 MoveCalculator 类，其唯一目的是处理解决方案。 GameState 类将处理游戏机制，而 GameForm 将在一些控件的帮助下驱动前端。
我希望 MoveCalculator 向 GameState 返回一些有用的东西，因此引入了 Move 类。 MoveCalculator 将返回一个移动列表，GameState 将执行它们。
UI 元素
GameForm 包含所有图形组件，并用作应用程序的驱动程序。我想使用 PictureBox 控件作为盘片和柱子的基本对象，但需要更多，因此我扩展了 PictureBox 控件。 Pole PictureBox 必须通过维护盘片的排序列表来跟踪其上的盘片。 Disk PictureBox 负责四处移动自己。我还添加了拖放功能，使游戏更有趣。
求解器算法
用于解决该谜题的算法是一个非常简单的递归函数。在该函数中，每个移动都会添加到列表中。该列表用于解决该谜题。
在游戏的开始状态，所有盘片都将在“起始柱子”上。在执行列表中的所有移动后，所有盘片都应该在“结束柱子”上。
代码
以下是来自应用程序的五个代码片段
MoveCalculator 类接收用户想要玩的盘片数量，并返回解决该谜题所需的移动列表。
代码片段 1：递归 Calculate 方法
public static class MoveCalculator
{
private static void Calculate(int n, int fromPole, int toPole)
{
if (n == -1)
{
return; // We are done
}
int intermediatePole = GetIntermediatePole(fromPole, toPole);
Calculate(n - 1, fromPole, intermediatePole);
moves.Add(new Move(fromPole, toPole));
Calculate(n - 1, intermediatePole, toPole);
}
...
} 代码片段 2：Move 包含 FromPole 和 ToPole。由于我们将始终移动 FromPole 顶部的盘片，因此我们只需要这两个柱子。
Move 还包含有关自身的信息，例如 AffectCount 和 IsValid。
public class Move
{
public Pole FromPole { get; set; }
public Pole ToPole { get; set; }
public bool AffectCount()
{
//If the poles don't change the move should not be counted
if (ToPole.Equals(FromPole))
{
return false;
}
return IsValid();
}
public bool IsValid()
{
//Allow a move where the pole dont change
if (ToPole.Equals(FromPole))
{
return true;
}
return ToPole.AllowDisk(FromPole.getTopDisk());
}
...
}
代码片段 3：UI 使用两个自定义 PictureBox 控件：Pole 和 Disk。
其中 Disk 可从一个 Pole 移动到下一个 Pole。而 Pole 包含一个 Disk 列表。
public class Disk : PictureBox
{
public int Number { get; set; }
public Disk(int Number) : base()
{ ... }
public void MoveToPole(Pole DestinationPole)
{ ... }
}
public class Pole : PictureBox
{
public SortedList<int, Disk> Disks { get; set; }
public int Number { get; set; }
public Pole(int number)
{
...
}
public bool IsEmpty()
{
return Disks.Count == 0;
}
public bool AllowDisk(Disk disk)
{
if (disk == null)
{
return false;
}
if (Disks.Count == 0)
{
return true;
}
return getTopDisk().Number > disk.Number;
}
public Disk getTopDisk()
{
if (Disks.Count > 0)
{
return Disks.First().Value;
}
return null;
}
public void RemoveDisk()
{
Disks.Remove(Disks.First().Key);
}
public void AddDisk(Disk disk)
{
if (AllowDisk(disk))
{
disk.MoveToPole(this);
Disks.Add(disk.Number, disk);
}
}
...
}
代码片段 4：为了保存有关游戏状态的信息，添加了 GameState 类。
GameState 应该启动游戏，执行移动并检查是否完成。
public static class GameState
{
public static List<Pole> Poles = new List<Pole>();
public static List<Bitmap> ImageList = new List<Bitmap>();
public static int MoveCount { get; set; }
public static int NumberOfDisks { get; set; }
// Start the game
static GameState()
{
LoadImagesFromFile();
RestartGame(3);
}
public static int Move(Move move)
{
if (move.AffectCount())
{
MoveCount++;
}
if (move.IsValid())
{
Disk disk = move.FromPole.getTopDisk();
Poles[move.FromPole.Number].RemoveDisk();
Poles[move.ToPole.Number].AddDisk(disk);
return MoveCount;
}
else //Invalid move
{
return -1;
}
}
public static bool IsSolved()
{
return (Poles[Properties.Settings.Default.EndPole].Disks.Count == NumberOfDisks);
}
}
代码片段 5：包含最多逻辑的两个类的单元测试：MoveCalculator & GameState
[TestClass()]
public class MoveCalculatorTest {
...
[TestMethod()]
public void GetMoveCountTest()
{
int actualMoveCount = MoveCalculator.GetMoveCount(3);
int expectedMoveCount = 7;
Assert.AreEqual(expectedMoveCount, actualMoveCount);
actualMoveCount = MoveCalculator.GetMoveCount(4);
expectedMoveCount = 15;
Assert.AreEqual(expectedMoveCount, actualMoveCount);
actualMoveCount = MoveCalculator.GetMoveCount(5);
expectedMoveCount = 31;
Assert.AreEqual(expectedMoveCount, actualMoveCount);
}
}
[TestClass()]
public class GameStateTest {
...
[TestMethod()]
public void IsSolvedTest()
{
GameState.RestartGame(numberOfDisks);
bool expectedBefore = false;
bool actualBefore = GameState.IsSolved();
solveGame();
bool expectedAfter = true;
bool actualAfter = GameState.IsSolved();
//Assert
Assert.AreEqual(expectedBefore, actualBefore);
Assert.AreEqual(expectedAfter, actualAfter);
}
}
注释
我想将每个盘片的位置等信息封装在 Disk 类本身中。
public void MoveToPole(Pole DestinationPole)
{
int numberOfRungsOnSelectedPole = DestinationPole.Disks.Count;
int x = (DestinationPole.Location.X + DestinationPole.Width) -
(DestinationPole.Width / 2) - (this.Size.Width / 2);
int y = DestinationPole.Location.Y + DestinationPole.Size.Height -
((numberOfRungsOnSelectedPole + 1) * this.Size.Height) -
toh.Properties.Resources._base.Size.Height;
this.Location = new Point(x, y);
} 我添加了 MoveToPole 方法，该方法基本上通过简单地设置其位置将盘片移动到柱子上。为了获得盘片移动到的正确点，我需要知道它要移动到哪个柱子以及它应该坐在柱子的哪个位置。由于每个 Pole 都包含有关其包含的盘片数量的信息，因此我只需接收 DestinationPole。该代码假定所有盘片的高度相同；与当前盘片相同。