Teilen Sie ein quadratisches Gitter in Teile gleicher Fläche

17

Diese Herausforderung ist auf dem folgenden Puzzle basiert: Sie sind ein gegeben ndurch nRaster mit nZellen markiert. Ihre Aufgabe ist es, das Raster in nTeile zu unterteilen, in denen jedes Teil aus genau nZellen besteht, von denen jede genau eine markierte Zelle enthält.

Beispiel

Hier ist ein Puzzle auf der linken Seite und seine (einzigartige) Lösung auf der rechten Seite:

Puzzle Lösung

Herausforderung

Sie erhalten einen Satz mit nNullindex versehener Koordinaten in einem angemessenen Format.

[(0,0), (0,3), (1,0), (1,1), (2,2)]

Und Ihre Aufgabe ist es, ein Programm zu schreiben, das alle gültigen Paritionen zurückgibt (wiederum in jedem vernünftigen Format).

[
  [(0,0), (0,1), (0,2), (1,2), (1,3)],
  [(0,3), (0,4), (1,4), (2,4), (3,4)],
  [(1,0), (2,0), (3,0), (4,0), (4,1)],
  [(1,1), (2,1), (3,1), (3,2), (4,2)],
  [(2,2), (2,3), (3,3), (4,3), (4,4)]
]

Wenn das Rätsel keine Lösung hat, sollte das Programm dies anzeigen, indem es einen Fehler auslöst oder eine leere Lösung zurückgibt.

Ein- / Ausgabebeispiele

[(0,0)]               => [[(0,0)]]

[(0,0), (1,1)]        => [
                          [(0,0), (1,0)], 
                          [(0,1), (1,1)]
                         ]

[(0,0), (0,1), (1,0)] => [] (no solution)

[(0,0), (0,1), (0,2)] => [
                          [(0,0), (1,0), (2,0)], 
                          [(0,1), (1,1), (2,1)],
                          [(0,2), (1,2), (2,2)],
                         ]

[(0,0), (0,2), (1,2)] => [
                          [(0,0), (1,0), (2,0)], 
                          [(0,1), (0,2), (1,1)],
                          [(1,2), (2,1), (2,2)],
                         ]

Wertung

Das ist , also gewinnt der kürzeste Code.

Peter Kagey
quelle
Dies wurde durch diese Math Stack Exchange-Frage inspiriert .
Peter Kagey
@Arnauld, bei Shikaku-Puzzles sieht es so aus, als ob "das Ziel darin besteht, das Gitter in rechteckige und quadratische Teile zu teilen". In diesem Fall gibt es keine solche Einschränkung.
Peter Kagey
Entschuldigung für die Verwirrung. Ich glaube, irgendwo in der Sandbox könnte es eine Shikaku-Herausforderung geben, oder ich hatte vor, irgendwann selbst eine zu bauen - ich kann mich nicht sicher erinnern. Auf jeden Fall dachte ich, es sei auf den ersten Blick dasselbe.
Arnauld
Warum ist das Ergebnis ein 2D-Array von Koordinaten? Ich verstehe nicht, was dort ausgedrückt wird ... Kann es nicht ein 2d-Array des Index des Arrays sein? Zum Beispiel Zeile 3, Spalte 2 enthält Partition mit Koordinaten bei Index 4?
Olivier Grégoire
Dürfen wir annehmen, dass jeder Bereich von den Referenzkoordinaten aus gezeichnet werden kann, wie im Beispiel vorgeschlagen? Mir ist gerade klar geworden, dass ich das unbewusst für selbstverständlich gehalten habe.
Arnauld

Antworten:

11

JavaScript (ES7), 166 Byte

feinlse

a=>(m=a.map(_=>[...a]),g=(n,X,Y,j=0,i)=>a[n]?a[j]?m.some((r,y)=>r.some((v,x)=>++v|(X-x)**2+(Y-y)**2-1?0:g(r[x]=n,x,y,j+1,i|x+[,y]==a[n])?1:r[x]=v)):i&&g(n+1):1)(0)&&m

Probieren Sie es online!

Wie?

mN×NN

m = a.map(_ => [...a])

mNm++

Gn(X,Y.)jich

g = (n, X, Y, j = 0, i) => a[n] ? a[j] ? ... : i && g(n + 1) : 1

ein[n]ein[j]

Gm

m.some((r, y) =>          // for each row r[] at position y in m[]:
  r.some((v, x) =>        //   for each cell of value v at position x in r[]:
    ++v |                 //     if this cell is already filled (i.e. v is numeric)
    (X - x) ** 2 +        //     or the squared Euclidean distance between
    (Y - y) ** 2 -        //     (X, Y) and (x, y)
    1 ?                   //     is not equal to 1:
      0                   //       this is an invalid target square: do nothing
    :                     //     else:
      g(                  //       do a recursive call to g:
        r[x] = n,         //         pass n unchanged and fill the cell with n
        x, y,             //         pass the coordinates of the current cell
        j + 1,            //         increment j
        i |               //         update i:
        x + [,y] == a[n]  //         set it if (x, y) = a[n]
      ) ?                 //       if the result of the call is truthy:
        1                 //         return 1
      :                   //       else:
        r[x] = v          //         reset the cell to NaN
  )                       //   end of inner map()
)                         // end of outer map()
Arnauld
quelle