javascript - 用单一路径填充二维网格

Question

如何用数字填充方形二维数组，以便创建从 1 到 (edge length) 的(随机)升序连续数字路径 ² ?

我正在尝试写一个 Hidato (又名 Hidoku)JavaScript 生成器。它不一定是编写它的最佳语言，但这就是我目前使用的语言。游戏板最初只被部分填满。唯一保证显示的数字是路径中的第一个和最后一个数字。游戏的想法是通过网格(垂直、水平或对 Angular 线)创建一条数字路径，以便有一个连续的上升数字链。由于考虑了对 Angular 线，链可能会重叠。

我卡在了电路板生成部分。一个有效的网格必须有一个(单一的，非分支的)连续数字路径，从 1 开始。至 (grid size) 2 。我看了又看，但没有发现任何可能有帮助的东西。有没有一种路径追踪算法可以用连续数字组成的单个路径填充二维数组？

我最初的天真方法是用值填充二维数组并交换值，直到网格成为有效的 Hidato 拼图。这需要永远计算，而且效率非常低，所以我放弃了这个想法。

我的下一个想法是使用回溯路径跟踪器来用连续值填充网格，但是我不确定如何实现这样的跟踪器。生成一条路径很容易(选择一个随机的相邻单元格并移动到它直到二维数组已满)，但我这里的问题是算法的“回溯性”，或者其他一些始终确保随机的方法整个网格中连续数字的路径。我想到了一个迷宫追踪器，但它不处理没有 fork 或死胡同的单一路径。

我怎样才能从这里开始？除了路径跟踪器或其他类似算法之外，我是否应该考虑其他选项？

相关问题:

• Routing “paths” through a rectangular array
• Algorithm to find a random Hamiltonian path in a grid?

Answer 1

事实证明，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);
    }
}