10

正方形の 2D 配列に数値を入力して、昇順で連続した数値の (ランダムな) パスが 1 から まで作成されるようにするにはどうすればよい(edge length)2ですか?

JavaScript でHidato (別名 Hidoku) ジェネレーターを作成しようとしています。それは必ずしもそれを書くのに最適な言語ではありませんが、それは私が現在使用しているものです. ゲームボードは、最初は部分的にしか埋められていません。表示される唯一の保証された番号は、パスの最初と最後の番号です。ゲームのアイデアは、数字の連続した昇順チェーンが存在するように、グリッド (垂直方向、水平方向、または斜め方向) を通る単一の数字パスを作成することです。対角線が考慮されるため、チェーンがオーバーラップする可能性があります。

ボード生成の部分で行き詰まっています。有効なグリッドには、 から までの連続した数値の (単一の分岐のない) パスが必要1です(grid size)2。私は見たり見たりしましたが、助けになるものは何も見つかりませんでした。連続した数字で構成される単一のパスで 2D 配列を埋めることができるパス トレース アルゴリズムはありますか?

私の最初の素朴なアプローチは、2D 配列に値を入力し、グリッドが有効なヒダト パズルになるまで値を交換することでした。これは計算に非常に時間がかかり、非常に非効率的であるため、そのアイデアを破棄しました。

次に考えたのは、バックトラッキング パス トレーサーを使用してグリッドに連続した値を入力することでしたが、そのようなトレーサーを実装する方法がわかりません。パスを生成するのは簡単です (ランダムな隣接セルを選択し、2D 配列がいっぱいになるまでそこに移動します)。グリッド全体の連続番号のパス。迷路トレーサーについて考えましたが、それは分岐や行き止まりのない単一のパスを処理しません。

ここからどうすれば進めますか？パス トレーサーや他の同様のアルゴリズム以外のオプションを検討する必要がありますか?

関連する質問:

4

1 に答える 1

9

非ランダム グラフの証明はありませんが、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);
    }
}
于 2013-04-09T14:12:22.160 に答える