用单个路径填充2D网格
我正在尝试用JavaScript 编写Hidato（aka
Hidoku）生成器。它不一定是最好的语言，但这就是我目前正在使用的语言。游戏板最初仅部分填充。显示的唯一保证数字是路径中的第一个和最后一个数字。游戏的想法是通过网格（垂直，水平或对角线）创建一条单一的数字路径，以便有一个连续的数字递增链。由于考虑了对角线，因此链条可能会重叠。
我被卡在了董事会生成部分。有效的网格必须具有从1到的连续数字（单个，非分支）路径(grid
size)``2。我看了看又看，但是没有发现可能有帮助的东西。是否有一种路径跟踪算法可以用由连续数字组成的单个路径填充2D数组？
我最初的天真方法是用值填充2D数组并交换值，直到网格成为有效的Hidato拼图为止。这将需要花费大量时间进行计算，并且效率非常低下，因此我放弃了这个想法。
我的下一个想法是使用回溯路径跟踪器将连续值填充到网格中，但是我不确定如何实现这种跟踪器。生成路径很容易（选择一个随机的相邻像元并移动到2D数组已满），但是我的问题是算法的“回溯度”，或其他确保始终存在随机性的方法整个网格中连续数字的路径。我想到了一个迷宫追踪器，但它不能处理没有叉形或死角的单个路径。
我怎样才能从这里开始？除了路径跟踪器或其他类似算法之外，我是否应该考虑其他选择？
回答：
事实证明，尽管没有针对非随机图的证据，但由于Angluin和Valiant（1977）而导致的汉密尔顿路径的局部搜索算法在此方面非常出色。这是一个样本广场
99 98 101 103 105 106 129 132 133 140 135 136 97 100 102 104 107 130 131 128 141 134 139 137
95 96 109 108 112 122 127 126 125 142 143 138
80 94 110 111 121 113 123 124 40 39 36 144
79 81 93 120 116 115 114 48 41 38 37 35
78 82 92 90 119 117 47 46 49 42 33 34
77 83 84 91 89 118 45 58 43 50 32 31
76 1 85 87 88 60 59 44 57 51 30 28
75 2 86 4 6 63 61 54 52 56 29 27
73 74 3 7 5 64 62 53 55 22 24 26
72 69 67 8 65 11 12 14 15 23 21 25
70 71 68 66 9 10 13 16 17 18 19 20
以及（有些草率编写的）Java代码。
import java.util.*;public class AV {
public static void main(String[] args) {
// construct an n-by-n grid
int n = 12;
Node[][] node = new Node[n][n];
List<Node> nodes = new ArrayList<Node>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
nodes.add((node[i][j] = new Node()));
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i >= 1) {
if (j >= 1) {
node[i - 1][j - 1].addEdge(node[i][j]);
}
node[i - 1][j].addEdge(node[i][j]);
if (j < n - 1) {
node[i - 1][j + 1].addEdge(node[i][j]);
}
}
if (j >= 1) {
node[i][j - 1].addEdge(node[i][j]);
}
}
}
findPath(nodes);
labelPath(nodes);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.printf("%4d", node[i][j].label);
}
System.out.println();
}
}
private static void findPath(List<Node> nodes) {
for (Node node : nodes) {
node.isOnPath = false;
}
Random random = new Random();
Node sink = nodes.get(random.nextInt(nodes.size()));
sink.isOnPath = true;
int isNotOnPathCount = nodes.size() - 1;
while (isNotOnPathCount > 0) {
sink.pathOut = sink.out.get(random.nextInt(sink.out.size()));
sink = sink.pathOut.head;
if (sink.isOnPath) {
// rotate
sink = sink.pathOut.head;
Arc reverse = null;
Node node = sink;
do {
Arc temp = node.pathOut;
node.pathOut = reverse;
reverse = temp.reverse;
node = temp.head;
} while (node != sink);
} else {
// extend
sink.isOnPath = true;
isNotOnPathCount--;
}
}
}
private static void labelPath(Collection<Node> nodes) {
for (Node node : nodes) {
node.isSource = true;
}
for (Node node : nodes) {
if (node.pathOut != null) {
node.pathOut.head.isSource = false;
}
}
Node source = null;
for (Node node : nodes) {
if (node.isSource) {
source = node;
break;
}
}
int count = 0;
while (true) {
source.label = ++count;
if (source.pathOut == null) {
break;
}
source = source.pathOut.head;
}
}
}
class Node {
public final List<Arc> out = new ArrayList<Arc>();
public boolean isOnPath;
public Arc pathOut;
public boolean isSource;
public int label;
public void addEdge(Node that) {
Arc arc = new Arc(this, that);
this.out.add(arc.reverse);
that.out.add(arc);
}
}
class Arc {
public final Node head;
public final Arc reverse;
private Arc(Node head, Arc reverse) {
this.head = head;
this.reverse = reverse;
}
public Arc(Node head, Node tail) {
this.head = head;
this.reverse = new Arc(tail, this);
}
}
以上是 用单个路径填充2D网格 的全部内容， 来源链接： utcz.com/qa/401600.html
