El reto

Considere el siguiente diagrama del Fifteen Puzzle en su estado resuelto:

_____________________
|    |    |    |    |
| 1  | 2  | 3  | 4  |
|____|____|____|____|
|    |    |    |    |
| 5  | 6  | 7  | 8  |
|____|____|____|____|
|    |    |    |    |
| 9  | 10 | 11 | 12 |
|____|____|____|____|
|    |    |    |    |
| 13 | 14 | 15 |    |
|____|____|____|____|

En cada movimiento, un rompecabezas emocionado tiene la oportunidad de mover una pieza adyacente al espacio en blanco al espacio en blanco. Por ejemplo, después del 1movimiento, tenemos 2escenarios posibles (dejemos 0un espacio en blanco):

1   2   3   4          1   2   3   4
5   6   7   8          5   6   7   8
9   10  11  12   and   9   10  11  0
13  14  0   15         13  14  15  12

Después de los 2movimientos, el rompecabezas tiene 5diferentes resultados ( tenga en cuenta que los dos casos anteriores están excluidos, ya que no se pueden alcanzar en 2 movimientos). Una de estas situaciones es el estado resuelto original, y se puede alcanzar de dos maneras diferentes.

Su tarea en este desafío es producir el número de resultados diferentes a los que puede conducir un cierto número de movimientos. Como entrada, tome un númeroN >= 0 y genere el número de situaciones únicas que pueden aparecer después de los Nmovimientos.

Reglas

• Este es el código de golf. ¡El código más corto gana!
• Lagunas estándar no están permitidas.
• Su código debería poder calcular el caso N = 10dentro de unos minutos. Probablemente no probaré esta regla a menos que exista un abuso obvio del tiempo en una respuesta.

Casos de prueba

(Resultados generados a partir de las sumas de OEIS A089484 (Como describió Geobits en el chat ), automatizado por el script de Martin Büttner . ¡Gracias por toda la ayuda!)

0 moves: 1
1 moves: 2
2 moves: 5
3 moves: 12
4 moves: 29
5 moves: 66
6 moves: 136
7 moves: 278
8 moves: 582
9 moves: 1224
10 moves: 2530
11 moves: 5162
12 moves: 10338
13 moves: 20706
14 moves: 41159
15 moves: 81548
16 moves: 160159
17 moves: 313392
18 moves: 607501
19 moves: 1173136
20 moves: 2244884
21 moves: 4271406
22 moves: 8047295
23 moves: 15055186
24 moves: 27873613
25 moves: 51197332
26 moves: 93009236
27 moves: 167435388
28 moves: 297909255
29 moves: 524507316
30 moves: 911835416
31 moves: 1566529356

Pyth, 36 bytes

lu{smmXd,0@dk)fq1.a.DR4,Txd0UdGQ]U16

Demostración . Prueba de arnés.

lu{smmXd,0@dk)fq1.a.DR4,Txd0UdGQ]U16

                 .a.DR4,Txd0            Find the Euclidean distance between the
                                        present location of 0 and a given location.
              fq1           Ud          Filter over all locations on that distance
                                        equaling 1.
     mXd,0@dk)                          Map each such location to the grid with 0
                                        and the value at that location swapped.
  {sm                         G         Map all unique grids possible after n-1
                                        steps to all unique grids after n steps.
 u                             Q]U16    Repeat <input> times, starting with the
                                        initial grid.
l                                       Print the length of the resulting set.

CJam, 54 52 51 50 49 47 45 bytes

G,ari{{:S0#S{4md2$4md@-@@-mh1=},f{Se\}}%:|}*,

Pruébelo en línea en el intérprete de CJam (debería tomar menos de 10 segundos).

Cómo funciona

G,a       e# Push R := [[0 1 ... 15]].
ri{       e# Do int(input()) times:
  {:S     e#   For each S in R:
    0#    e#     Push the index of 0 in S (I).
    S{    e#     Filter S; for each J in in S:
      4md e#       Push J/4 and J%4.
      2$  e#       Copy I.
      4md e#       Push I/4 and I%4.
      @-  e#       Compute (I%4)-(J%4).
      @@- e#       Compute (J%4)-(I%4).
      mh  e#       2-norm distance: a b -> sqrt(aa + bb)
      1=  e#       Check if the distance is 1.
    },    e#     Keep all values of J with distance 1 from I.
    f{    e#     For each J:
      S   e#       Push S. 
      e\  e#       Swap S at indexes I and J.
    }     e#     This pushes an array of all valid modifications of S.
  }%      e#   Collect the results for all S in R in an array.
  :|      e#   Reduce the outmost array using set union (removes duplicates).
}*        e#

Retina , 289 276 bytes

^
,abcd%efgh%ijkl%mnox,
(`(,[^,]*)x([^,%])([^,y]*),
$0$1$2x$3y,
(,[^,]*)([^,%])x([^,y]*),
$0$1x$2$3y,
(,[^,]*)x([^,]{4})([^,])([^,y]*),
$0$1$3$2x$4y,
(,[^,]*)([^,])([^,]{4})x([^,y]*),
$0$1x$3$2$4y,
,.{19},(?=.*1)|,[^,]{20},(?=[^1]*$)|y|1$

+)`([^,]{19})(.*),\1,
$1$2
[^a]

a
1

Toma entrada e imprime salida en unario.

Puede poner cada línea en un solo archivo o ejecutar el código tal como está con la -sbandera. P.ej:

> echo -n 111|retina -s fifteen_puzzle
111111111111

El núcleo del método es que hacemos un seguimiento de todas las posiciones posibles (sin repetición) que pueden ocurrir después de exactamente los kpasos. Comenzamos el formulario k = 0y repetimos los pasos de sustitución (usando el (` and )` modifiers) hasta llegar al número de entrada de pasos.

Durante este cálculo, nuestra cadena siempre tiene la forma de

(,[puzzle_state]y?,)+1*

dónde puzzle_state está abcd%efgh%ijkl%mnoxcon alguna permutación de las letras. xrepresenta el lugar vacío, el resto de las letras son los azulejos.%son delimitadores de fila.

y marca que el estado se genera en el paso actual (k ), por lo que no debe usarse para generar otros estados en este paso.

1Marque el número de pasos restantes.

La mecánica básica del código Retina es que cada coincidencia de una línea impar se cambia a la siguiente (par).

El código con explicación adicional:

initialize string
^
,abcd%efgh%ijkl%mnox,

while string changes
(`

for every old (y-less) state concatenate a new state with moving the empty tile to r/l/d/u if possible
right
(,[^,]*)x([^,%])([^,y]*),
$0$1$2x$3y,
left
(,[^,]*)([^,%])x([^,y]*),
$0$1x$2$3y,
down
(,[^,]*)x([^,]{4})([^,])([^,y]*),
$0$1$3$2x$4y,
up
(,[^,]*)([^,])([^,]{4})x([^,y]*),
$0$1x$3$2$4y,

if we should have made this step (there are 1's left) remove old states
,.{19},(?=.*1)

if we should not have made this step (no more 1's left) remove new states
,[^,]{20},(?=[^1]*$)

remove y markers
y

remove one 1 (decrease remaining step count)
1$


remove duplicates until string changes (with + modifier)
+`([^,]{19})(.*),\1,
$1$2    

end while
)`

remove non-a's, 1 a stays from each state
[^a]

change a's to 1's
a
1

10 bytes guardados gracias a @MartinButtner.

Python, 310 253 243 229 bytes

Última versión con mejora sugerida por @randomra:

s=set()
s.add(tuple(range(16)))
def e(a,b):s.add(t[:a]+(t[b],)+t[a+1:b]+(t[a],)+t[b+1:])
for k in range(input()):
 p,s=s,set()
 for t in p:j=t.index(0);j%4and e(j-1,j);j%4>2or e(j,j+1);j<4or e(j-4,j);j>11or e(j,j+4)
print len(s)

Mi propia versión, que era más larga (243 bytes), pero más fácil de leer:

s=set()
s.add(tuple(range(16)))
def e(a,b):s.add(t[:a]+(t[b],)+t[a+1:b]+(t[a],)+t[b+1:])
for k in range(input()):
 p,s=s,set()
 for t in p:
  j=t.index(0)
  if j%4:e(j-1,j)
  if j%4<3:e(j,j+1)
  if j>3:e(j-4,j)
  if j<12:e(j,j+4)
print len(s)

Búsqueda simple de amplitud, codificando los estados como tuplas y almacenándolos en un conjunto para mantenerlos únicos.

Toma alrededor de 0.03 segundos en mi computadora portátil para N = 10. El tiempo de ejecución aumenta sustancialmente para números más grandes, por ejemplo, aproximadamente 12 segundos para N = 20.

Perl, 148

#!perl -p
$s{"abcd.efgh.ijkl.mno#"}=1;for(1..$_){$x=$_,map{$r{$_}=1if
s/($x)/$3$2$1/}keys%s for
qw!\w)(# #)(\w \w)(.{4})(# #)(.{4})(\w!;%s=%r;%r=()}$_=keys%s

Ejemplo:

$ time perl 15.pl <<<20
2244884
real    0m39.660s
user    0m38.822s
sys 0m0.336s