Juego a las 15

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 3 de septiembre de 2021; las comprobaciones requieren 2 ediciones .

El juego de 15 [1] [2] [3] , etiqueta [4] [5] , tomado [2] [5] [6]  es un popular juego de rompecabezas inventado en 1878 por Noah Chapman. El rompecabezas es un conjunto de 15 huesos cuadrados idénticos con números impresos en ellos, que se encuentran en una caja cuadrada. La longitud del lado de la caja es cuatro veces la longitud del lado del hueso, por lo que un campo cuadrado queda vacío en la caja. El objetivo del juego es colocar las fichas en orden ascendente moviéndolas dentro de la caja, preferiblemente con la menor cantidad de movimientos posible.

Historia

Autoría

Desde 1891 hasta su muerte , Samuel Loyd afirmó que fue él quien inventó el rompecabezas, y durante mucho tiempo se creyó que así era [7] [8] . Sin embargo, hay pruebas de que no participó en la creación de las fichas 14 y 15 [9] [10] [11] [8] . El pico de popularidad del rompecabezas en los Estados Unidos llegó en la primera mitad de 1880; sin embargo, no se encontró ninguna mención de Sam Loyd en relación con los "quince" hasta enero de 1891 [12] [10] . En particular, The New York Times publicó materiales sobre el rompecabezas dos veces, el 22 de marzo de 1880 y el 11 de junio de 1880, sin mencionar a Loyd ni una sola vez, a pesar de que Loyd vivía en Nueva York [13] .

El verdadero inventor del rompecabezas fue Noah Palmer Chapman, un administrador de correos de Canastota [14] [15] , quien allá por 1874 mostró a sus amigos un rompecabezas que constaba de dieciséis cuadrados numerados que había que poner en filas de cuatro para que la suma de los números en cada fila eran iguales a 34 [16] .

El hijo de Noah Chapman, Frank Chapman, trajo los rompecabezas completos a Syracuse, Nueva York, y se los dio a Anna y James Belden [17] . Ellos, a su vez, llevaron el rompecabezas a Watch Hill, Rhode Island donde se hicieron copias del rompecabezas [14] ; una de estas copias llegó a Hartford [14] a través de una ruta desconocida , donde los estudiantes de la Escuela Americana para Personas con Discapacidad Auditiva comenzaron a hacer copias preliminares del rompecabezas [14] . Para 1879, el rompecabezas ya se vendía no solo en Hartford, sino también en Boston . Luego, el carpintero Matthias J. Rice se enteró de las "etiquetas". En diciembre de 1879, Matthias Rice inició un nuevo negocio de rompecabezas en Boston llamado The  Gem Puzzle [18] [ 19] [20] .

A principios de 1880, un tal Charles Pevey, un dentista de Worcester , atrajo la atención del público al ofrecer una recompensa en efectivo por resolver el problema de armar un rompecabezas, lo que aumentó la popularidad del nuevo juego. En la primavera de ese año, el juego llegó a Europa .

El 21 de febrero de 1880, Noah Chapman intentó solicitar una patente para su invento bajo el nombre de "Block Solitaire Puzzle" ("Rompecabezas-solitario con bloques") [21] , pero la solicitud de patente fue rechazada; no se ha conservado ningún registro que explique por qué sucedió esto [22] . Aparentemente, esto se debió al hecho de que, según el inspector de patentes Burke, la nueva solicitud difería poco de la patente [23] "Cunning Blocks", "Puzzle-Blocks", otorgada a Ernest W. Kinsey (Ernest U. Kinsey ) más de un año antes de que Noah Chapman presentara su solicitud [24] [25] .

Distribución

En los EE.UU.

El 6 de enero de 1880, apareció un anuncio el Boston Evening Transcript de un rompecabezas llamado Boss Puzzle . El 12 de enero, Boston Transcript mencionó varias versiones de terceros, incluidas Gem Puzzle , Solitaire , Fifteen y Number Puzzle . El 19 de enero se anunció en el mismo periódico un rompecabezas llamado The New Puzzle ; Al día siguiente, Worcester Gazette publicó un anuncio de The Boss Puzzle . La popularidad del rompecabezas creció rápidamente y los empresarios ya comenzaron a fabricarlo y venderlo [26] .

Entre el 26 y el 30 de enero, el Boston Evening Transcript publicó un anuncio de Matthias Ries, molesto por la aparición de copias del rompecabezas. El anuncio decía [27] :

Cuidado con las falsificaciones. Asegúrese de obtener este y solo un rompecabezas cuidadosamente elaborado y cuidadosamente probado.
Texto original  (inglés) : 
El rompecabezas de las gemas de Rice. El Gran Original. Cuidado con las imitaciones. Asegúrese de pedir este, el único rompecabezas completamente confiable y hecho con precisión en el mercado, y no tome otro.

En febrero de 1880, comenzaron a aparecer artículos detallados sobre el rompecabezas en varios periódicos [28] . Varias revistas nacionales, incluidas The Youth's Companion , Illustrated Newspaper, Harper's Weekly , Scientific American , The Independent , anunciaron el rompecabezas durante varias semanas [29] . La noticia del rompecabezas se extendió a otras ciudades. A principios de marzo, muchos fabricantes lanzaron versiones del rompecabezas con diferentes nombres [19] .

El 12 de febrero, el Boston Herald publicó un poema sobre el rompecabezas, seguido de varias obras en verso en otros periódicos 30] . El 17 de febrero, el periódico Rochester Democrat and Chronicle publicó un artículo sobre el impacto del rompecabezas en la sociedad. El 20 de febrero, el New York Ontario County Journal publicó un artículo que dice lo siguiente [31] :

Probablemente N. P. Chapman, jefe de correos de Canastota, será el hombre más maldito del país durante las próximas semanas. Inventó el Juego a los 15 años.
Texto original  (inglés) : 
Probablemente NP Chapman, jefe de correos de Canastota, NY, será, durante las próximas semanas, el hombre más maldito del país. Inventó el 'Juego de 15'.

El 17 de marzo de 1880, el Boston Daily Advertiser publicó un artículo que describía el "comienzo de la locura" en Boston hace tres meses (diciembre de 1879) [28] .

Con base en anuncios y artículos de periódicos, los autores de The 15 Puzzle Slocum y Zonneveld concluyen que en la mayoría de las ciudades la "locura" duró uno o dos meses; sin embargo, en muchas ciudades el rompecabezas se hizo popular antes de su publicación en los periódicos locales y siguió siendo popular incluso cuando cesó la publicación [32] .

Fuera de los EE.UU.

En marzo de 1880, el rompecabezas comenzó a extenderse fuera de los Estados Unidos. Hasta finales de marzo llegó a Canadá y Francia. Durante abril, la "locura" llegó a Inglaterra, Alemania, Letonia, Austria, Estonia, Noruega, Suecia, Rusia, Finlandia, en mayo: Nueva Zelanda, Países Bajos, Italia, México, Dinamarca, Australia [33] .

En Rusia

El 25 de abril de 1880, el St. Petersburg Herold publicó un anuncio en alemán "Neues Spiel - Das Spiel der Funfzehn" [34] ("Juego nuevo - Juego a las 15").

Tareas

El rompecabezas de gemas

En The Gem Puzzle , creado y vendido por Matthias Ries en 1879, el jugador vaciaba fichas de una caja y las volvía a colocar al azar, después de lo cual intentaba restaurar la configuración ordenada [20] [10] :

Coloca los bloques en la caja al azar, luego muévelos hasta que se alineen en el orden correcto.
Texto original  (inglés) : 
Coloque los bloques en la caja de manera irregular, luego muévalos hasta que estén en orden regular.

En esta versión, el problema resultó irresoluble exactamente en la mitad de los casos.

Rompecabezas 14-15

En otra versión, todas las fichas, excepto la 14 y la 15, están inicialmente en su lugar; la tarea es intercambiar las fichas 14 y 15 mal colocadas. Esta tarea no tiene solución; sin embargo, en este caso, puede organizar las fichas con una celda vacía en la esquina superior izquierda o alinear las fichas en columnas [35] .

  • Arroz. 1. En la posición inicial en el rompecabezas 14-15, se intercambian las fichas 14 y 15

  • Arroz. 2. No se puede acceder a esta ubicación desde la ubicación inicial del rompecabezas 14-15 (Fig. 1)

  • Arroz. 3. Pero esta ubicación se puede lograr desde la ubicación inicial del rompecabezas 14-15 (Fig. 1)

  • Arroz. 4. Otra ubicación alcanzable para el rompecabezas 14-15 (Fig. 1)

Modificaciones modernas

Se han lanzado numerosas variantes del rompecabezas. En algunas realizaciones, en lugar de ordenar números, el objetivo es restaurar alguna imagen. Se pueden usar letras en lugar de números; la presencia de al menos dos letras idénticas puede hacer que resolver el rompecabezas no sea una tarea trivial.

  • El elefante duerme de pie. ¿Y usted?

  • En inglés ("Mide tu mente, amigo mío") [8]

  • En alemán ("Sin trabajo no hay recompensa")

Cuadrado Mágico

Una de las tareas es reorganizar las fichas de tal manera que la suma de los números en cada fila (horizontal, vertical o diagonal grande) sea igual al mismo número ; mientras que el valor numérico de una celda vacía se considera igual a cero [36] [37] . En este caso, la suma mágica es 30. Se necesitan al menos 35 movimientos para obtener el cuadrado mágico desde la ubicación inicial, y solo hay un cuadrado mágico que se puede alcanzar en 35 movimientos [38] .

Descripción matemática

Se puede demostrar que exactamente la mitad de todas las 20 922 789 888 000 (=16 ! ) posiciones iniciales posibles de las etiquetas no se pueden llevar a la forma ensamblada. Deje que una ficha con un número se ubique antes (si cuenta de izquierda a derecha y de arriba hacia abajo) que las fichas con números menores que ; entonces denotamos . En particular, si después de una ficha con un número no hay fichas con números menores que , entonces . También ingresamos un número  : el número de la fila de la celda vacía (contando desde 1). si la cantidad

(es decir, la suma del número de pares de huesos en los que el hueso con el número más alto viene antes que el hueso con el número más pequeño, y el número de la fila de una celda vacía) es impar , entonces no hay solución para el rompecabezas [39] [3] .

Si permitimos que la caja gire 90 grados, en la que las imágenes de los números estarán de costado, entonces es posible convertir combinaciones irresolubles en solubles (y viceversa). Por lo tanto, si en lugar de números en los nudillos, coloque puntos y no fije la posición del cuadro, entonces no habrá combinaciones irresolubles.

Solución óptima

Para etiquetas generalizadas (con más de 15 mosaicos), el problema de encontrar la solución más corta para una configuración dada es NP-completo [40] [41] .

4  ×  4

Cualquiera de las 10.461.394.944.000 configuraciones resolubles del “clásico” rompecabezas 4  ×  4 se puede convertir a la inicial en no más de 80 movimientos, si por movimiento entendemos el movimiento de una ficha [42] [43] [38] [44 ] , o no más que en 43 movimientos, si por movimiento entendemos el movimiento simultáneo de una fila continua de no más de tres fichas [45] . Solo 17 de todas las configuraciones resolubles no se pueden resolver en menos de 80 movimientos, es decir, requieren 80 movimientos de fichas individuales para resolver [43] [38] [46] ; solo 16 configuraciones resolubles requieren 43 movimientos de filas continuas de mosaicos [45] .

5  ×  5

En 1995, se demostró que cualquier configuración de un rompecabezas de 5  ×  5 se puede resolver en no más de 219 movimientos individuales [47] , es decir, se obtuvo un límite superior de 219 movimientos para la longitud de la solución óptima arbitraria. configuración. En 1996, se encontró una configuración que no se puede resolver en menos de 112 movimientos de mosaico [48] . En 2000, el límite superior se mejoró a 210 movimientos [49] ; en 2011,  se obtuvo un límite inferior de 152 movimientos y un límite superior de 208 movimientos para el " número de Dios " del rompecabezas 5  × 5 [44] .

Resultados actuales

La tabla resume los datos para una serie de generalizaciones de "etiquetas". Cuando no se conoce el resultado exacto, los límites inferior y superior más conocidos se dan en la forma lb - ub .

El tamaño Configuración de destino Número
de configuraciones a resolver		 Movimientos "largos"
[ K 1] 		" Número de Dios " Número
de "antípodas" [K 2]
2  ×  2 caja vacía en la esquina 12 No 6 [49] [50] 1 [49]
2  ×  3 caja vacía en la esquina 360 No 21 [49] [50] 1 [49]
2  ×  4 caja vacía en la esquina 20 160 No 36 [49] [50] 1 [49]
2  ×  5 caja vacía en la esquina 1 814 400 No 55 [51] [50] 2 [51]
2  ×  6 caja vacía en la esquina 239 500 800 No 80 [52] [50] 2 [52]
2  ×  7 caja vacía en la esquina 43 589 145 600 No 108 [53] [50]
2  ×  8 caja vacía en la esquina 10 461 394 944 000 No 140 [53] [50]
3  ×  3 caja vacía en la esquina 181 440 No 31 [49] [44] [50] 2 [49] [54]
Sí 24 [44]
3  ×  4 caja vacía en la esquina 239 500 800 No 53 [49] [50] 18 [49]
3  ×  5 caja vacía en la esquina 653 837 184 000 No 84 [50]
3  ×  5 celda vacía en el centro 653 837 184 000 No 84 [55]
4  ×  4 caja vacía en la esquina 10 461 394 944 000 No 80 [43] [38] [44] [50] 17 [43] [38] [46]
Sí 43 [45] 16 [45]
5  ×  5 caja vacía en la esquina 7.7556⋅10 24 No 152 [44]  - 208 [44]

El uso de etiquetas en informática

Los "quince" de varios tamaños se han utilizado regularmente en la investigación de IA desde la década de 1960 ; en particular, prueban y comparan algoritmos de búsqueda de espacio de estado con diferentes funciones heurísticas [56] [57] [58] [59] y otras optimizaciones que afectan la cantidad de configuraciones de rompecabezas (vértices de gráficos) visitadas en el proceso de búsqueda. En los estudios, de una forma u otra, se realizan rompecabezas de tamaños 3  ×  3 [60] [61] , 4  ×  4 [62] [63] [43] , 5  ×  5 [48] [64] [65] , 6  × Se utilizaron  6 [66] , 2  ×  7 [55] , 3  ×  5 [55] .

Se pueden enumerar las principales razones para elegir etiquetas como "banco de pruebas" para los algoritmos de búsqueda [67] [40] [68] :

  1. el espacio de estado de las etiquetas clásicas es accesible para el análisis, pero aún lo suficientemente grande como para ser de interés y para usar y comparar varias heurísticas [69] ;
  2. no se conoce ningún algoritmo que encuentre la solución más corta para etiquetas n  ×  n generalizadas en un tiempo razonable [40] ;
  3. la tarea misma de encontrar la solución más corta para las etiquetas es fácil de entender y manipular programáticamente [56] [40] ; el rompecabezas se puede describir con un conjunto pequeño y bien definido de reglas simples [70] [40] ;
  4. el modelado de rompecabezas no requiere la transferencia de sutilezas semánticas inherentes a áreas temáticas más complejas [71] ;
  5. los problemas con etiquetas son representantes exitosos de la clase de problemas en los que se requiere encontrar el camino más corto entre dos vértices dados de un gráfico finito no dirigido [40] ;
  6. el tamaño del gráfico de búsqueda depende exponencialmente del tamaño del rompecabezas n , aunque cualquier estado puede describirse utilizando la memoria O ( n 2 ) [40] ;
  7. la misma función heurística se puede aplicar a todos los estados, ya que todos los estados se describen de la misma manera; en aplicaciones reales, diferentes estados pueden tener diferentes descripciones, lo que requiere la introducción de varias heurísticas [72] ;
  8. el uso de juegos y acertijos en la investigación no plantea problemas financieros o éticos [71] .

Búsqueda heurística

El algoritmo A* , IDA* [73] , la búsqueda primero en amplitud se puede utilizar como un algoritmo de búsqueda .

El rompecabezas de 3  × 3  se resuelve fácilmente con cualquier algoritmo de búsqueda. Las configuraciones arbitrarias de etiquetas 4  ×  4 se resuelven utilizando algoritmos de búsqueda modernos en unos pocos milisegundos [57] . La solución óptima del rompecabezas 5  ×  5 requiere más recursos incluso con el uso de computadoras y algoritmos modernos [57] [64] ; el proceso de búsqueda puede tardar varias semanas y generar billones de nodos [65] [66] . La solución óptima de configuraciones arbitrarias del  rompecabezas 6  × 6 aún está más allá de las posibilidades [66] y, por lo tanto, los estudios solo intentan predecir el rendimiento relativo del algoritmo IDA* con diferentes funciones heurísticas [66] .

Una de las heurísticas más simples para las etiquetas se puede expresar de la siguiente manera [74] [75] [76] :

El número de movimientos necesarios para resolver no es menor que el número de fichas que están fuera de lugar.

La corrección de la declaración, es decir, la admisibilidad de la función heurística "el número de fichas que no están en su lugar", se deriva del hecho de que solo se puede colocar una ficha en un movimiento. Esta heurística no utiliza toda la información disponible: por ejemplo, no tiene en cuenta las distancias que deben moverse las fichas individuales.

Una heurística más inteligente asigna a cada ubicación de mosaico la suma de las distancias desde la posición actual de cada mosaico hasta su posición de destino [77] . En la literatura, esta heurística se encuentra bajo el nombre de "distancia de Manhattan" (distancia de Manhattan) [76] [78] . La validez de la función se deriva del hecho de que solo se mueve una pieza por movimiento, y la distancia entre esta pieza y su posición final cambia en 1. Sin embargo, esta heurística tampoco utiliza toda la información disponible, debido al hecho de que en una posición dos fichas no pueden estar al mismo tiempo. Hay versiones más informadas de la "distancia de Manhattan" como el conflicto lineal [58] .

 Se han desarrollado heurísticas basadas en bases de datos de patrones [63] [64] [59] para encontrar rápidamente la solución óptima a un rompecabezas de 4  ×  4, así como para poder encontrar la solución óptima a un rompecabezas de 5  × 5 en un tiempo razonable. tiempo Tales heurísticas son, en esencia, tablas precalculadas y almacenadas en RAM, en las que se codifican las soluciones óptimas para las subtareas; cada una de las subtareas se reduce a mover un determinado grupo de fichas a las posiciones de destino [63] . Estas heurísticas también se pueden aplicar al Cubo de Rubik y otros rompecabezas [64] .

Véase también

Comentarios

  1. ↑ La columna indica si el movimiento de varias fichas al mismo tiempo, formando una fila vertical u horizontal continua, cuenta como un movimiento.
  2. ↑ "Antípodas": configuraciones de rompecabezas que requieren la mayor cantidad de movimientos para resolver

Notas

  1. ↑ Ocio matemático, 1972 , p. 401.
  2. ↑ 1 2 Tareas y experimentos entretenidos, 1972 , p. 365.
  3. ↑ 1 2 Jugando "15" . componente matemático . Estudios Matemáticos .
  4. ↑ Inteligencia artificial: estrategias y métodos para resolver problemas complejos, 2003 , p. 43, 114, 163, 166, 168, 181-182.
  5. ↑ 1 2 Nombre "Quince" . TwistyPuzzles.RU.
  6. ↑ Vladímir Belov. Rompecabezas desde una distancia cercana. parte 2 Computerra (18 de enero de 2000). Archivado desde el original el 28 de noviembre de 2015.
  7. ↑ Cyclopedia of Puzzles , pág. 235
  8. ↑ 1 2 3 Jaap Scherphuis. Rompecabezas 14-15 / Rompecabezas jefe . La página del rompecabezas de Jaap .
  9. ↑ El rompecabezas de los 15, 2006 .
  10. ↑ 1 2 3 Reseña de The 15 Puzzle de Aaron Archer , p. una.
  11. ↑ Rompecabezas por placer, 1994 , p. 10-12.
  12. ↑ El rompecabezas de los 15, 2006 , p. 76.
  13. ↑ Rompecabezas por placer, 1994 , p. once.
  14. ↑ 1 2 3 4 El rompecabezas de los 15, 2006 , pág. 109.
  15. ↑ Reseña de The 15 Puzzle de Aaron Archer , p. 13
  16. ↑ El rompecabezas de los 15, 2006 , p. 98-99.
  17. ↑ El rompecabezas de los 15, 2006 , p. 103-104, 109.
  18. ↑ El rompecabezas de los 15, 2006 , p. 11, 109.
  19. ↑ 1 2 Reseña de The 15 Puzzle de Aaron Archer , p. 2.
  20. ↑ 1 2 Jerry Slocum: el engaño más exitoso de Sam Loyd Archivado el 23 de diciembre de 2015 en Wayback Machine (PDF; 672 kB) . Vortrag auf: Seventh Gathering for Gardner, marzo de 2006, Convención de la Asociación de coleccionistas de juegos y rompecabezas. Publicado en: E. Pegg, A. H. Schoen & T. Rodgers: Homage to a Pied Puzzler. AK Peters, Wellesley/Massachusetts, 2009, S. 3-21. (aquí: S. 4)
  21. ↑ El rompecabezas de los 15, 2006 , p. 100-101.
  22. ↑ El rompecabezas de los 15, 2006 , p. 101.
  23. ↑ UE Kinsey. Bloques de rompecabezas. no. 207124. Patentado ago. 20, 1878 .
  24. ↑ El rompecabezas de los 15, 2006 , p. 102.
  25. ↑ Reseña de The 15 Puzzle de Aaron Archer , p. 3.
  26. ↑ El rompecabezas de los 15, 2006 , p. 14-15.
  27. ↑ El rompecabezas de los 15, 2006 , p. 15-16.
  28. ↑ 1 2 El rompecabezas de los 15, 2006 , p. 12
  29. ↑ El rompecabezas de los 15, 2006 , p. veinte.
  30. ↑ El rompecabezas de los 15, 2006 , p. 21
  31. ↑ El rompecabezas de los 15, 2006 , p. 24, 98.
  32. ↑ El rompecabezas de los 15, 2006 , p. 59.
  33. ↑ El rompecabezas de los 15, 2006 , p. 60
  34. ↑ El rompecabezas de los 15, 2006 , p. 63.
  35. ↑ Tareas y experimentos entretenidos, 1972 , p. 370.
  36. ↑ Tareas y experimentos entretenidos, 1972 , p. 371.
  37. ↑ Sam Loyd; Martin Gardner: Rompecabezas matemáticos de Sam Loyd . Dover Pubs., Nueva York 1959, págs. 19 y 20. Google libros
  38. ↑ 1 2 3 4 5 Herbert Kociemba. Solucionador óptimo de quince rompecabezas . Archivado desde el original el 2 de octubre de 2015.
  39. ↑ Slocum J., Weisstein EW 15 Puzzle  (inglés) en el sitio web de Wolfram MathWorld .
  40. ↑ 1 2 3 4 5 6 7 Ratner D., Warmuth MK Encontrar una solución más corta para la extensión N × N del 15-PUZZLE es intratable // Conferencia Nacional sobre Inteligencia Artificial, 1986.
  41. ↑ Ratner D., Warmuth M. El rompecabezas (n 2 −1) y los problemas de reubicación relacionados  // Journal of Symbolic Computation. - 1990. - T. 10 , N º 2 . — págs. 111–137 . - doi : 10.1016/S0747-7171(08)80001-6 .
  42. ↑ A. Brüngger, A. Marzetta, K. Fukuda y J. Nievergelt, El banco de búsqueda paralelo ZRAM y sus aplicaciones , Annals of Operations Research 90 (1999), págs. 45-63.
  43. ↑ 1 2 3 4 5 Richard E. Korf, Peter Schultze. Búsqueda en amplitud paralela a gran escala . — 2005.
  44. ↑ 1 2 3 4 5 6 7 Secuencia OEIS A087725 : el mayor número de movimientos necesarios para generalizar el  rompecabezas n  × n 15
  45. ↑ 1 2 3 4 Bruce Norskog. El Quince Puzzle se puede resolver en 43 "movimientos" . Foro Dominio del Cubo (8 de diciembre de 2010).
  46. ↑ 1 2 Secuencia OEIS A089484 : número de configuraciones de etiquetas cuya solución óptima contiene n movimientos
  47. ↑ Ralph Udo Gasser. Aprovechamiento de los recursos computacionales para una búsqueda exhaustiva eficiente . — 1995.
  48. ↑ 1 2 Richard E. Korf, Larry A. Taylor. Encontrar soluciones óptimas al rompecabezas de los veinticuatro . — 1996.
  49. ↑ 1 2 3 4 5 6 7 8 9 10 11 Filip RW Karlemo y Patric RJ Östergård Sobre rompecabezas de bloques deslizantes , Journal of Combinatorial Mathematics and Combinatorial Computing 34 (2000), 97-107
  50. ↑ 1 2 3 4 5 6 7 8 9 10 11 Secuencia OEIS A151944 : el mayor número de movimientos necesarios para generalizar un  rompecabezas de 15 rompecabezas de m  × n
  51. ↑ 1 2 Secuencia A090036 en OEIS
  52. ↑ 1 2 Secuencia A090167 en OEIS
  53. ↑ 1 2 Secuencia A151943 en OEIS
  54. ↑ Secuencia OEIS A089473 _
  55. ↑ 1 2 3 Richard E. Korf. Búsqueda de frontera en amplitud con detección de duplicados retrasada . — 2004.
  56. ↑ 1 2 Inteligencia artificial: estrategias y métodos para resolver problemas complejos, 2003 , p. 114.
  57. ↑ 1 2 3 Inteligencia artificial: un enfoque moderno, 2006 , p. 118.
  58. ↑ 1 2 Generación de heurísticas admisibles mediante la crítica de soluciones a modelos relajados, 1985 .
  59. ↑ 1 2 F. Yang, J. Culberson, R. Holte, U. Zahavi y A. Felner A General Theory of Additive State Space Abstractions Archivado el 8 de diciembre de 2015 en Wayback Machine , Volumen 32 (2008), páginas 631-662
  60. ↑ Alejandro Reinfeld. Solución completa del rompecabezas de ocho y el beneficio de la ordenación de nodos en IDA* . — 1993.
  61. ↑ Daniel R. Kunkle. Resolviendo el Rompecabezas del 8 en un Número Mínimo de Movimientos: Una Aplicación del Algoritmo A* . — 2001.
  62. ↑ Richard E. Korf. Profundización iterativa primero en profundidad: una búsqueda de árbol admisible óptima . — 1985.
  63. ↑ 1 2 3 Joseph C. Culberson, Jonathan Schaeffer. Bases de datos de patrones . — 1998.
  64. ↑ 1 2 3 4 Richard E. Korf. Avances recientes en el diseño y análisis de funciones heurísticas admisibles . — 2000.
  65. ↑ 1 2 Richard E. Korf, Ariel Felner. Heurística de la base de datos de patrones disjuntos . — 2002.
  66. ↑ 1 2 3 4 Ariel Felner, Richard E. Korf, Sarit Hanan. Heurística de la base de datos de patrones aditivos . — 2004.
  67. ↑ Inteligencia artificial: estrategias y métodos para resolver problemas complejos, 2003 , p. 43, 114, 163.
  68. ↑ Generación de heurísticas admisibles mediante la crítica de soluciones para modelos relajados, 1985 , p. 3.
  69. ↑ Inteligencia artificial: estrategias y métodos para resolver problemas complejos, 2003 , p. 114, 163.
  70. ↑ Inteligencia artificial: estrategias y métodos para resolver problemas complejos, 2003 , p. 43, 163.
  71. ↑ 1 2 Inteligencia artificial: estrategias y métodos para resolver problemas complejos, 2003 , p. 43.
  72. ↑ Inteligencia artificial: estrategias y métodos para resolver problemas complejos, 2003 , p. 163.
  73. ↑ Borowski BS Optimal 8/15-Puzzle Solver . // Galería de proyectos de Brian. Consultado el 29 de julio de 2013. Archivado desde el original el 17 de agosto de 2013.
  74. ↑ Inteligencia artificial: estrategias y métodos para resolver problemas complejos, 2003 , p. 156.
  75. ↑ Programación entretenida: Tutorial, 2005 , p. 171.
  76. ↑ 1 2 Generación de heurísticas admisibles mediante la crítica de soluciones a modelos relajados, 1985 , p. 4-5.
  77. ↑ Inteligencia artificial: estrategias y métodos para resolver problemas complejos, 2003 , p. 157.
  78. ↑ Programación entretenida: Tutorial, 2005 , p. 173.

Literatura

Libros
  • Gardner M. Ocio matemático / Per. De inglés. Yu. A. Danilova . ed. Ya. A. Smorodinsky . — M .: Mir , 1972.
  • Perelman Ya. I. Tareas y experimentos entretenidos. - M .: Literatura infantil , 1972.
  • Jerry Slocum y Dic Sonneveld. El rompecabezas del 15. - 2006. - ISBN 1-890980-15-3 .
  • Szczepan Jelenski Tras los pasos de Pitágoras: Matemáticas entretenidas = Śladami Pitagorasa / Traducido del polaco por G. F. Boyarskaya, B. V. Boyarsky y A. A. Yakushev. -M.:Detgiz, 1961. - S. 231-233.
  • Clarke BR Rompecabezas por placer . - Prensa de la Universidad de Cambridge, 1994. - ISBN 0-521-46634-2 .
  • Luger, George F. Inteligencia artificial : estructuras y estrategias para la resolución de problemas complejos. - 4ª edición. - Editorial Williams, 2003. - 864 p. — ISBN 5-8459-0437-4 . — ISBN 978-5-845-90437-9 .
  • Stuart Russel, Peter Norvig . Inteligencia artificial: un enfoque moderno = Inteligencia artificial: un enfoque moderno. - 2ª ed. - M. : Editorial "Williams", 2006. - 1408 p. — ISBN 5-8459-0887-6 .
  • Mozgovoy M. V. Programación entretenida: Tutorial . - San Petersburgo. : Pedro , 2005. - 208 p. - ISBN 5-94723-853-5 .
Artículos

Enlaces

 Problemas NP-completos
Problema
de maximización del apilamiento (packing)
teoría de grafos
teoría de conjuntos
Problemas algorítmicos
Juegos de lógica
y rompecabezas.