Vervollständigen Sie den gitterfüllenden Mäander

18

Ein gitterfüllender Mäander ist ein geschlossener Pfad, der jede Zelle eines quadratischen Gitters mindestens einmal besucht, niemals eine Kante zwischen benachbarten Zellen mehr als einmal kreuzt und sich niemals selbst kreuzt. Beispielsweise:N×N

Einmal gefüllt, kann jede Zelle des Gitters durch eine der folgenden 8 Kacheln dargestellt werden:

Auf diese Weise nummeriert, können die Kacheln des obigen Mäanders durch diese Matrix dargestellt werden:

5 6 5 6
4 8 3 2
5 7 6 2
4 3 4 3

Ihre Aufgabe ist es, einen gitterfüllenden Mäander mit einem unvollständigen Kachelsatz fertigzustellen. Zum Beispiel der unvollständige Mäander:

... die mit 0s für fehlende Kacheln dargestellt werden können:

5 0 0 0 6
0 0 7 0 0
0 0 0 0 3
2 4 0 0 0
0 0 3 0 0

... könnte so ergänzt werden:

... dh:

5 6 5 1 6
4 8 7 6 2
5 7 7 7 3
2 4 8 8 6
4 1 3 4 3

Spezifikationen

  • Die Eingabe hat immer mindestens und höchstens (nicht leere) Kacheln, wobei .1N22N7
  • Sie können einen beliebigen Satz von Werten verwenden, um die Kacheln darzustellen, sofern dies in Ihrer Antwort angegeben ist.
  • Ihre Eingabe und Ausgabe kann in jedem Format und in jeder Reihenfolge erfolgen, sofern dies in Ihrer Antwort angegeben ist.
  • Für alle Eingaben ist mindestens eine gültige Lösung vorhanden (dh Sie müssen keine ungültigen Eingaben verarbeiten).
  • Es gelten die Standard-E / A-Regeln .
  • Standardlücken sind verboten.
  • Erklärungen, auch für "praktische" Sprachen, sind erwünscht.

Testfälle

Eingabe ( Θ ):

0 6
0 0

Ausgabe ( Θ ):

5 6
4 3

Eingabe ( Θ ):

5 6 5 6
4 0 3 2
5 7 6 2
4 3 4 3

Ausgabe ( Θ ):

5 6 5 6
4 8 3 2
5 7 6 2
4 3 4 3

Eingabe ( Θ ):

5 0 0 0 6
0 0 7 0 0
0 0 0 0 3
2 4 0 0 0
0 0 3 0 0

Ausgabe ( Θ ):

5 6 5 1 6
4 8 7 6 2
5 7 7 7 3
2 4 8 8 6
4 1 3 4 3
Jordan
quelle
Sandboxed
Jordan
1
@ Arnauld Du hast recht; es ist nicht gültig. Ein Mäander ist ein einzelner geschlossener Pfad.
Jordan
1
@ Arnauld Danke, ich habe diese Änderung vorgenommen. Ich wusste nicht, dass MathJax auf dieser Seite aktiviert ist!
Jordan

Antworten:

11

JavaScript (ES7),  236 ... 193  185 Bytes

Ausgaben durch Ändern der Eingabematrix.

m=>(g=(d,x,y,v,r=m[y],h=_=>++r[x]<9?g(d,x,y,v)||h():r[x]=0)=>r&&1/(n=r[x])?x|y|!v?n?g(d='21100--13203-32-21030321'[n*28+d*3+7&31],x+--d%2,y+--d%2,v+=n<7||.5):h():!m[v**.5|0]:0)(0,0,0,0)

Probieren Sie es online!

(Enthält Nachbearbeitungscode, um das Ergebnis sowohl als Matrix als auch als flache Liste zu drucken, die mit dem vom OP bereitgestellten Visualisierungstool kompatibel ist. )

Ergebnisse

Wie?

Variablen

gd(x,y)v

g

  • r

    r = m[y]
  • h18gg0

    h = _ => ++r[x] < 9 ? g(d, x, y, v) || h() : r[x] = 0

Erstkontrollen

n

r && 1 / (n = r[x]) ? ... ok ... : ... failed ...

(0,0)v>0

x | y | !v ? ... no ... : ... yes ...

Nehmen wir vorerst an, dass wir nicht zum Ausgangspunkt zurückkehren.

Auf der Suche nach einem Weg

n0h

n0

ndd

d = '21100--13203-32-21030321'[n * 28 + d * 3 + 7 & 31]

Die letzten 8 Einträge sind ungültig und weggelassen. Die anderen 4 ungültigen Einträge sind explizit mit Bindestrichen gekennzeichnet.

Nachfolgend finden Sie als Referenz die dekodierte Tabelle, den Kompass und das Kachelset, die in der Challenge enthalten sind:

   | 1 2 3 4 5 6 7 8
---+-----------------
 0 | 0 - - 1 3 - 3 1          1
 1 | - 1 - - 2 0 2 0        0 + 2
 2 | 2 - 1 - - 3 1 3          3
 3 | - 3 0 2 - - 0 2

g1/2v781

g(d, x + --d % 2, y + --d % 2, v += n < 7 || .5)

dxy

Pfad validieren

(0,0)v>0

781/2v

v=N2v>N2v<N2kk=v

Daher der JS-Code:

!m[v ** .5 | 0]

Formatierte Quelle

m => (
  g = (
    d,
    x, y,
    v,
    r = m[y],
    h = _ => ++r[x] < 9 ? g(d, x, y, v) || h() : r[x] = 0
  ) =>
    r && 1 / (n = r[x]) ?
      x | y | !v ?
        n ?
          g(
            d = '21100--13203-32-21030321'[n * 28 + d * 3 + 7 & 31],
            x + --d % 2,
            y + --d % 2,
            v += n < 7 || .5
          )
        :
          h()
      :
        !m[v ** .5 | 0]
    :
      0
)(0, 0, 0, 0)
Arnauld
quelle
Gute Arbeit. Ich würde gerne eine Erklärung des Codes lesen.
Jordan
@Arnauld erzwingen Sie es brachial oder verwenden Sie einen anderen Algorithmus?
Jonah
1
@Jonah Ich schreibe gerade eine Erklärung. Grundsätzlich ist es ein Brute-Force-Ansatz, aber der Algorithmus geht zurück, sobald eine Inkonsistenz festgestellt wird, anstatt jedes einzelne mögliche Board auszuprobieren.
Arnauld