algorithm - 通过矩形数组路由 "paths"

Question

我正在尝试创建自己的益智游戏实现。

为了创建我的游戏板，我需要遍历数组中的每个方 block 一次且仅一次。
遍历需要链接到相邻的邻居(水平、垂直或对角线)。

我正在使用以下形式的数组结构:

board[n,m] = byte
Each bit of the byte represents a direction 0..7 and exactly 2 bits are always set
Directions are numbered clockwise
0 1 2 
7 . 3
6 5 4 
Board[0,0] must have some combination of bits 3,4,5 set

我目前构建随机路径的方法是:

 Start at a random position
 While (Squares remain)
    if no directions from this square are valid, step backwards
    Pick random direction from those remaining in bitfield for this square       
    Erase the direction to this square from those not picked
    Move to the next square

此算法在某些中等大小的网格上花费的时间太长，因为较早的选择将区域排除在考虑之外。

我想要的是一个函数，它为每个可能的路径取一个索引，并返回为该路径填充的数组。这将让我提供一个“种子”值以返回到这个特定的板。

欢迎提出其他建议..

Answer 1

本质上，您想要构造一个 Hamiltonian path : 访问图的每个节点恰好一次的路径。

一般来说，即使您只想测试一个图是否包含哈密顿路径，这也已经是 NP 完全的了。在这种情况下，很明显该图至少包含一条哈密顿路径，并且该图具有良好的规则结构——但枚举所有哈密顿路径似乎仍然是一个难题。

Wikipedia entry哈密​​顿路径问题上有一个随机算法，用于查找声称“在大多数图上都很快”的哈密顿路径。它与您的算法的不同之处在于它围绕路径的整个分支进行交换，而不是仅通过一个节点进行回溯。这种更“激进”的策略可能会更快——试试看。

您可以让您的用户输入随机数生成器的种子以重建特定路径。您仍然不会枚举所有可能的路径，但我想这对于您的应用程序可能不是必需的。