填写2D网格单一路径 [英] Fill 2D grid with single path
问题描述
如何我可以填写一个正方形二维数组与号码，这样连续编号升序排列一个（随机）路径是从1创建（边长） 2 ？
我想写一个 Hidato （又名Hidoku）发生在JavaScript中。它不一定把它写在最好的语言，但我使用的是什么目前唯一的。游戏板最初仅部分填充。示出的只保证数字是在路径中的第一个和最后一个号码。游戏的想法是通过网格来创建数字的单个路径（垂直，水平或对角），以便有一个数字连续升链。链可重叠由于对角线被考虑在内。
I'm trying to write a Hidato (aka Hidoku) generator in JavaScript. It's not necessarily the best language to write it in, but that's what I'm using currently. The game board is initially only partially filled. The only guaranteed numbers shown are the first and last numbers in the path. The idea of the game is to create a single path of numbers through the grid (vertically, horizontally or diagonally) so that there is a consecutive ascending chain of numbers. The chain can overlap due to the diagonals being taken into account.
我卡上的电路板产生的一部分。有效的电网必须具有（网格大小） 1 去的路径> 2 。我看着看着却一无所获，可能已经帮助。是否有一个路径追踪算法，可以填补一个二维数组由连续的数字的单一路径？
I'm stuck on the board generation part. A valid grid must have a (single, non-branching) path of consecutive numbers going from 1 to (grid size)2. I've looked and looked but found nothing that might've helped. Is there an path tracing algorithm that can fill a 2D array with a single path made up of consecutive numbers?
我最初的，幼稚的做法是，以填补一个二维数组与价值和交换价值，直到电网是一个有效的Hidato谜。这将采取永远计算和效率会很低，所以我放弃了这个想法。
My initial, naive approach was to fill a 2D array with values and swap values until the grid was a valid Hidato puzzle. This would take forever to compute and would be very inefficient, so I scrapped that idea.
我的下一个想法是使用回溯路径示踪剂，填补了网格连续的值，但是我不能确定如何实现这样的示踪剂。产生路径够容易（随机选择一个相邻小区，并移动到它，直到2D阵列满），但在这里我的问题是回溯性的算法，或者一些其它的方式来始终确保有一个随机连续号码整个网格的路径。我想到了一个迷宫示踪剂但不处理，没有分叉或死角单一路径。
My next thought was to use a backtracking path tracer to fill in the grid with consecutive values, however I'm unsure how to implement such a tracer. Generating a path is easy enough (choose a random adjacent cell and move to it until the 2D array is full), but my issue here is the "backtracking-ness" of the algorithm, or some other way to always ensure there is a random path of consecutive numbers throughout the grid. I thought about a maze tracer but that doesn't deal with single paths with no forking or dead ends.
我如何从这里出发？我应该考虑其他的选择不是一个路径示踪或其他类似的算法？
How can I proceed from here? Should I be considering other options than a path tracer or other similar algorithm?
相关问题：
- Routing "paths" through a rectangular array
- Algorithm to find a random Hamiltonian path in a grid?
推荐答案
原来，汉密尔顿路径因Angluin和勇士（1977）的局部搜索算法是pretty的擅长此道，尽管没有证据用于非随机图形。下面是一个示例方
It turns out that the local search algorithm for Hamilton path due to Angluin and Valiant (1977) is pretty good at this, even though there's no proof for non-random graphs. Here's a sample square
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 code，使得它。
and the (somewhat hastily written) Java code that made it.
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网格单一路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
