使用 C# 和位运算解决五连块问题
4.98/5 (27投票s)
本项目解决了令著名科幻作家阿瑟·克拉克着迷的五连块问题。
引言
这个问题可以看作是解决一个有十二块拼图的谜题。听起来很简单，不是吗？
有十二种形状各异的块，称为五连块（类似多米诺骨牌）。它们是由五个方块组成的拼图，通过边缘连接成不同的构型。每块拼图看起来都隐约像一个字母，因此它们以字母唯一标识。挑战是将这些拼图排列在 60 个方格的矩形网格中。可能的网格尺寸为 6x10、5x12、4x15 和 3x20。本项目通过使用 64 位无符号长整数来表示棋盘和每种方向的单个拼图来解决这一挑战。这种表示方法将确定拼图是否适合当前棋盘的问题简化为按位或运算和按位异或运算。该程序证明了使用位运算可以极大地简化和加速某些计算问题。
背景
我受到《Futility Closet》网站上关于五连块的文章的启发，开发了这个程序。我读到阿瑟·克拉克曾“计算过，通过盲目排列解决这个问题需要超过 200 亿年”。这似乎很高，我估计答案更像是每秒一步需要 7000 年（12! x 8 种方向 x 60 个棋盘位置）。尽管如此，用一个简单的暴力破解计算机程序来解决这个问题似乎并不难。我只需要一个二维字节数组，以及某种方法用一组 12 个较小的数组填充它，其中包含已占用和未占用的单元格。几次无效的测试，运行了一整夜都没有找到结果，这表明我需要重新考虑我的方法。我的答案是将问题空间映射到 64 位字的位运算。
运行程序
用户界面是一个简单的 Windows 窗体。您可以选择棋盘尺寸以及是否应打乱拼图的初始顺序。由于存在多种解决方案，尝试拼图的顺序会影响解决方案。我可以遍历所有可能的解决方案（6x10 网格有 2339 种，5x12 网格有 1010 种，4x15 网格有 368 种，3x20 网格有 2 种），但我需要找到一种展示 3719 种不同解决方案的好方法。
选择网格尺寸后，您可以单击“解决”按钮，看到使用初始拼图顺序找到的第一个解决方案，该顺序为 L、F、I、N、P、T、U、V、W、X、Y、Z。如果您勾选了
Randomize order of tiles
，那么您可能会看到不同的解决方案。
6x10 网格的解决方案
5x12 网格的解决方案
4x15 网格的解决方案
3x20 网格的一个解决方案
3x20 网格的另一个解决方案
使用代码
解决方案是一个标准的 Visual Studio 2017 Windows 窗体应用程序，用 C# 编写。该解决方案应在该版本或更高版本的 Visual Studio 中打开。
关注点
棋盘和拼图的二进制表示
我最初尝试使用二维字节数组来解决问题。但这很快就变得非常麻烦。最困难的问题是如何确定哪些潜在的移动应该被接受，哪些应该被拒绝。然后我意识到，我可以将棋盘和拼图映射到 64 位整数，并使用位运算，如 &（与）、|（或）、^（异或）、>>（右移）和 <<（左移）将拼图放置在不同的位置。这会将迭代 60 个棋盘位置和代表拼图的 5x5 数组减少为对 64 位字的两个机器级操作。
5x10 棋盘可以表示为一个网格。下面的示例显示了 T 拼图放置在棋盘上的情况。
如果我们用 60 个二进制数字表示这个棋盘，已占用的方格设置为 1，空方格设置为 0，我们就得到以下位串。最后四位在棋盘之外。为了方便起见，我们可以将它们设置为 1。
011100000000100000000010000000000000000000000000001111
这还告诉我们如何表示位置 1 处的 T 拼图的二进制数字。如果我们想将 T 拼图向右移动一个位置，只需使用右移操作，我们就可以在位置 2 得到 T 的二进制表示。因此，我们可以将 T 移动到棋盘上的任何位置。我们确实需要一些测试来确保我们忽略 T 溢出棋盘的位置。因此，在 5x12 棋盘上，T 拼图在每个位置的有效二进制表示（省略了明显条目）是
0 11100000000001000000000001
1 011100000000001000000000001
2 0011100000000001000000000001
and so on...
8 0000000011100000000001000000000001
9 0000000001110000000000100000000000
skip overflow
12 00000000000011100000000001000000000001
13 000000000000011100000000001000000000001
and so on...
20 0000000000000000000011100000000001000000000001
21 00000000000000000000011100000000001000000000001
skip overflow
24 00000000000000000000000011100000000001000000000001
25 000000000000000000000000011100000000001000000000001
and so on
32 0000000000000000000000000000000011100000000001000000000001
33 00000000000000000000000000000000011100000000001000000000001
skip overflow
在棋盘上放置了一些其他拼图后，棋盘可能看起来像这样。
如果我们把棋盘转换成二进制数，其中 1 表示已占用，0 表示未占用，我们就得到下面的二进制数。为了清晰起见，我将其分解为五个十二位的二进制数，然后将它们连接起来，
100000000000
110000000000
110100000000
111100000000
111110000000
100000000000110000000000110100000000111100000000111110000000
现在我们想看看 T 拼图可以放在哪里。取位置 0 处的 T 和棋盘作为二进制数字，并将 Or 和 Xor 运算符应用于这对数字。
Board: 100000000000110000000000110100000000111100000000111110000000
T tile: 11100000000001000000000001
Or: 111000000000110000000000110100000000111100000000111110000000
Xor: 011000000000100000000100100100000000111100000000111110000000
现在尝试将 T 拼图放在位置 1 处的相同两个操作。
Board: 100000000000110000000000110100000000111100000000111110000000
T tile: 011100000000001000000000001
Or: 111100000000111000000000101100000000111100000000111110000000
Xor: 111100000000111000000000101100000000111100000000111110000000
在位置 1 的情况下，我们可以看到拼图块与棋盘之间的 Or 和 Xor 操作的结果是相同的。这表明拼图的所有部分都填充了棋盘上的空方格，并且没有与已占用方格发生冲突，即位置 1 是 T 拼图的有效位置。Or 操作的结果成为下一个拼图的棋盘。
通过使用位运算，我们将测试拼图是否可以放置在棋盘上以及放置在哪里，简化为三个基本机器操作——Shift（移位）、Or（或）和 Xor（异或）。请注意，1 位移位操作的数量对应于拼图左上角方块的棋盘位置。
表示拼图
拼图可以旋转，所以我们实际上需要每种拼图的四种不同的位图。如果我们允许翻转，那么就需要八种。事实证明，四种就足够了，但有一个例外，对于 3x20 的解决方案，如下所述。以下枚举和对象用于表示每种拼图。
public enum Rotation
{
zero,
ninety,
one80,
two70,
undefined
}
public class Tile
{
public int Number { get; set; }
public string Letter { get; set; }
public int Placed { get; set; }
public Rotation Rotation { get; set; }
public int Shift { get; set; }
public byte[,] Slots;
public ulong?[] BitMap = new ulong?[4]; // indexed by Rotation
public int[] TileWidth = new int[4]; // indexed by Rotation, used to check for Board overflow
public Tile(int number)
{
this.Placed = -1;
this.Rotation = Rotation.undefined;
this.Number = number;
}
}
ulong?[] BitMap 属性保存拼图的二进制表示，而 byte[,] Slots 属性保存二维表示。为了方便起见，我们填充 Slots，然后为每个 Rotation（旋转）创建一个 Bitmap。以下代码用于初始化 T 拼图。
_Tiles[9].Slots = new byte[3, 3] { { 1, 1, 1 }, { 0, 1, 0 }, { 0, 1, 0 } };
_Tiles[9].Letter = "T";
以下代码用于旋转 Slots 数组、去除空行、填充 Bitmap 并设置 Tilewidth。
slots = Rotate(_Tiles[i].Slots, Rotation.one80);
_Tiles[i].TileWidth[(int)Rotation.one80] = slots.GetUpperBound(1) + 1;
_Tiles[i].BitMap[(int)Rotation.one80] = slots.ToBitMap(_Width, _Height);
public byte[,] Rotate(byte[,] slots, Rotation r)
{
byte[,] rotSlots = null;
int rowMax = slots.GetUpperBound(0);
int colMax = slots.GetUpperBound(1);
switch (r) {
case Rotation.zero:
rotSlots = slots;
break;
case Rotation.ninety:
rotSlots = new byte[colMax + 1, rowMax + 1];
for (int col = 0; col <= colMax; col++) {
for (int row = 0; row <= rowMax; row++) {
rotSlots[col, rowMax - row] = slots[row, col];
}
}
break;
case Rotation.one80:
rotSlots = new byte[rowMax + 1, colMax + 1];
for (int col = 0; col <= colMax; col++) {
for (int row = 0; row <= rowMax; row++) {
rotSlots[rowMax - row, colMax - col] = slots[row, col];
}
}
break;
case Rotation.two70:
rotSlots = new byte[colMax + 1, rowMax + 1];
for (int col = 0; col <= colMax; col++) {
for (int row = 0; row <= rowMax; row++) {
rotSlots[colMax - col, row] = slots[row, col];
}
}
break;
}
return StripEmptyRowsAndColumns(rotSlots);
}
public static ulong? ToBitMap(this byte[,] byteMap, int width, int height)
{
ulong? result = 0;
int bitPos = 63;
int rows = byteMap.GetUpperBound(0) + 1;
if (rows > height) {
return null;
}
for (int row = 0; row <= byteMap.GetUpperBound(0); row++) {
for (int col = 0; col <= byteMap.GetUpperBound(1); col++) {
if (byteMap[row, col] == 1) {
result = SetBit(result, bitPos);
}
bitPos--;
}
bitPos = 63 - width * (row + 1);
}
return result;
}
private static ulong? SetBit(ulong? value, int index)
{
if (index < 0 || index >= 64) {
throw new ArgumentOutOfRangeException();
}
ulong? one = 1;
return value | (one << index);
}
放置拼图
谜题由以下递归方法解决。
public StatusFlag TilePlaced(ulong board, int level)
{
// Increment to next level of recursion
level++;
if (level > _Tiles.Count) {
return StatusFlag.Failed;
}
// Reset tiles placed at higher levels of recursion
for (int tileX = 0; tileX < _Tiles.Count; tileX++) {
if (_Tiles[tileX].Placed >= level) {
_Tiles[tileX].Placed = -1;
}
}
// Iterate through tiles
for (int x = 0; x < _Tiles.Count; x++) {
// Choose shuffled tile ordinal
int tileX = _Order[x];
// Skip placed tiles
if (_Tiles[tileX].Placed != -1 && _Tiles[tileX].Placed < level) {
continue;
}
_Tiles[tileX].Placed = -1;
// Iterarate through rotation
for (Rotation rotation = Rotation.zero; rotation <= Rotation.two70; rotation++) {
// Get pice as ulong
ulong? nullablePiece = _Tiles[tileX].BitMap[(int)rotation];
if (nullablePiece != null) {
ulong basePiece = nullablePiece.Value;
ulong piece = basePiece;
int tileWidth = _Tiles[tileX].TileWidth[(int)rotation];
// Iterate through all possible board positions by shifting
for (int shift = 0; shift < _Width * _Height; shift++) {
// Break when last bit is going to be shifted away
if ((piece >> 4) % 2 == 1) {
break;
}
// Move the piece by shiftind
piece = basePiece >> shift;
// Skip if shift position invalid (i.e overflows board)
if (SkipShift(shift, tileWidth)) {
continue;
}
// OR the piece and board
ulong b = board | piece;
// Test if result matches XOR of piece and board
if (b == (board ^ piece)) {
// Optimization - ensure Tile placement leaves no holes that can't be filled
if (b.NoHoles(_Width, _Height)) {
// Place tile
_Tiles[tileX].Placed = level;
_Tiles[tileX].Shift = shift;
_Tiles[tileX].Rotation = rotation;
_Counter++;
// Test for completion
if (level >= _Tiles.Count && b == _CompletedBoard) {
ReDrawAllCells(picBoard, level);
ReportSolved();
return StatusFlag.Finished;
}
// Recurse with new board
StatusFlag statusFlag = TilePlaced(b, level);
if (statusFlag != StatusFlag.Failed) {
return statusFlag;
}
else {
// Failed after recursion - continue iterations
_Tiles[tileX].Placed = -1;
continue;
}
}
}
}
}
}
}
return StatusFlag.Failed;
}
优化
虽然可以通过尝试所有可能的组合来解决谜题，但最好尝试人类解决谜题的方式。也就是说，从一个角落开始，尝试将拼图组合在一起，而不留下无法填充的空白。NoHoles 扩展方法可以做到这一点。它基本上确保非空行只能以一系列二进制 1 开始。实际上，程序尝试从右到左填充棋盘。
显示注意事项
由 Tile 对象表示的十二块拼图列表提供了在窗体上显示棋盘和拼图所需的信息。找到解决方案后，程序按最终放置的从左到右的顺序显示拼图，每个拼图显示之间有一个小时间间隔。
使用 Bit Array 类而不是 64 位字
使用实际的二进制表示来表示棋盘和拼图的一种替代方法是使用 .Net 框架的 BitArray 类。我开始创建一个版本来使用这个类。当我发现 BitArray 类没有本机移位方法时，我就停止了。