Este reto se basa en el siguiente enigma: se le da una npor ncuadrícula con ncélulas marcadas. Su trabajo consiste en dividir la cuadrícula en npartes donde cada parte consta de exactamente nceldas, cada una de las cuales contiene exactamente una celda marcada.

Ejemplo

Aquí hay un rompecabezas a la izquierda y su solución (única) a la derecha:

Desafío

Se le dará un conjunto de ncoordenadas indexadas a cero en cualquier formato razonable.

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

Y su trabajo es escribir un programa que devuelva cualquier parición válida (nuevamente, en cualquier formato razonable).

[
  [(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)]
]

Si el rompecabezas no tiene solución, el programa debe indicarlo arrojando un error o devolviendo una solución vacía.

Ejemplos de entrada / salida

[(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)],
                         ]

Puntuación

Este es el código de golf , por lo que gana el código más corto.

code-golf combinatorics grid set-partitions Peter Kagey
fuente

Esto se inspiró en esta pregunta de Math Stack Exchange .

Peter Kagey

@Arnauld, parece que para los rompecabezas de Shikaku, "el objetivo es dividir la cuadrícula en piezas rectangulares y cuadradas". En este caso, no existe tal restricción.

Peter Kagey

Perdón por la confusion. Creo que podría haber un desafío Shikaku en algún lugar de la caja de arena, o tal vez estaba planeando hacer uno yo mismo en algún momento, no lo recuerdo con certeza. De cualquier manera, pensé que era lo mismo a primera vista.

Arnauld

¿Por qué el resultado es una matriz 2D de coordenadas? No entiendo lo que se expresa allí ... ¿No puede ser una matriz 2D del índice de la matriz? Por ejemplo, la fila 3, la columna 2 contiene una partición con coordenadas en el índice 4?

Olivier Grégoire

¿Podemos suponer que cada área se puede dibujar comenzando desde las coordenadas de referencia, como sugiere el ejemplo? Me acabo de dar cuenta de que inconscientemente he dado esto por sentado.

Arnauld

JavaScript (ES7), 166 bytes

$false$

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

Pruébalo en línea!

¿Cómo?

$m$ $N\times N$ $N$

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

$m$ $N$ $m$ ++

$g$ $n$ $(X,Y)$ $j$ $i$

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

Probamos $a[n]$ $a[j]$

La parte principal de $g$ $m$

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
fuente

Particionar una cuadrícula cuadrada en partes de igual área