我如何用数字填充方形二维数组，以便创建从1到(edge length) 2 的(随机)连续数字升序路径?
我试图写一个Hidato(又名Hidoku)在JavaScript生成器。它不一定是最好的语言，但这是我目前使用的。游戏棋盘最初只被部分填满。唯一保证显示的数字是路径中的第一个和最后一个数字。这个游戏的理念是在网格中创造一条数字路径(垂直、水平或对角线)，这样就会有一个连续上升的数字链。由于考虑了对角线，链可以重叠。
我卡在板生成部分。一个有效的网格必须有从1到(grid size) 2 的连续数字的(单一，非分支)路径。我找了又找，但没有找到任何有用的东西。是否有一个路径跟踪算法，可以填补一个二维数组与一个单一的路径组成的连续数字?
我最初的方法是用值填充2D数组并交换值，直到网格成为一个有效的Hidato谜题。这要花很长时间来计算，而且效率很低，所以我放弃了这个想法。
我的下一个想法是使用回溯路径跟踪器来填充连续值的网格，但是我不确定如何实现这样的跟踪器。生成路径很容易(选择一个随机的相邻单元，然后移动到它，直到2D数组满了)，但我在这里的问题是算法的"回溯性"，或者其他方法总是确保在整个网格中有一个连续数字的随机路径。我想过一个迷宫追踪器，但它不能处理没有分叉或死角的单一路径。
我该如何从这里出发?除了路径跟踪器或其他类似算法之外，我是否应该考虑其他选择?
相关问题:
- 通过矩形数组路由"路径"
- 在网格中找到随机哈密顿路径的算法?
事实证明，Angluin和Valiant(1977)提出的Hamilton路径的局部搜索算法在这方面做得很好，尽管对于非随机图没有证据。这是一个正方形样本
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);
}
}