Заполните 2D сетку с одного путем

Question

Как я могу заполнить квадрат 2D массив с числами, так что (случайный) путем последовательных чисел в порядке возрастания создается от 1 до (edge length)2?

Я пытаюсь написать генератор Hidato (aka Hidoku) в JavaScript. Это не обязательно лучший язык, чтобы написать его, но это то, что я использую в настоящее время. Игровая панель изначально только частично заполнена. Единственными гарантированными номерами являются первые и последние числа на пути. Идея игры состоит в том, чтобы создать единый путь чисел через сетку (по вертикали, по горизонтали или по диагонали), так что существует последовательная возрастающая цепочка чисел. Цепь может перекрываться из-за учета диагоналей.

Я застрял на части поколения доски. Действительная сетка должна иметь (один, не ветвящийся) путь последовательных чисел от 1 до (grid size)2. Я посмотрел и посмотрел, но не нашел ничего, что могло бы помочь. Есть ли алгоритм трассировки пути, который может заполнить 2D-массив одним путем, состоящим из последовательных чисел?

Мой первоначальный наивный подход состоял в том, чтобы заполнить 2D-массив значениями и значениями подкачки, пока сетка не станет действительной загадкой Хидато. Это потребовалось бы навсегда для вычисления и было бы очень неэффективным, поэтому я отказался от этой идеи.

Моя следующая мысль заключалась в том, чтобы использовать трассировщик пути возврата, чтобы заполнить сетку последовательными значениями, однако я не уверен, как реализовать такой трассировщик. Генерирование пути достаточно просто (выберите случайную смежную ячейку и перейдите к ней до тех пор, пока не будет заполнен 2D-массив), но моя проблема здесь заключается в «обратном следе» алгоритма или каком-то другом способе всегда обеспечивать случайную путь последовательных чисел по всей сетке. Я думал о лабиринте, но это не касается одиночных путей без разветвления или тупиков.

Как я могу исходить отсюда? Должен ли я рассматривать другие варианты, кроме трассировщика пути или другого аналогичного алгоритма?

Похожие вопросы:

• 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); 
    } 
}