Un rompecabezas de emparejamiento de bordes es un tipo de rompecabezas de mosaico que implica el mosaico de un área con polígonos (típicamente regulares) cuyos bordes se distinguen con colores o patrones, de tal manera que los bordes de los mosaicos adyacentes coinciden.
Se sabe que los rompecabezas de combinación de bordes son NP-completos y pueden convertirse en y desde rompecabezas equivalentes y rompecabezas de empaque poliomino . [1]
Los primeros rompecabezas de combinación de bordes fueron patentados en los EE. UU. Por EL Thurston en 1892. [2] Los ejemplos actuales de rompecabezas comerciales de combinación de bordes incluyen el rompecabezas Eternity II , Tantrix , la gama de rompecabezas de combinación de bordes de Kadon Enterprises y Edge Match Aplicación para iPhone Puzzles.
Variaciones notables
Cuadrados MacMahon
MacMahon Squares es el nombre que se le da a un rompecabezas matemático recreativo sugerido por el matemático británico Percy MacMahon , quien publicó un tratado sobre la coloración de bordes de una variedad de formas en 1921. [4] Este rompecabezas en particular utiliza 24 fichas que constan de todas las permutaciones de 3 colores. para los bordes de un cuadrado. Las baldosas deben disponerse en un área rectangular de 6 × 4 de manera que todos los bordes coincidan y, además, solo se use un color para el borde exterior del rectángulo. [5]
Este rompecabezas se puede ampliar a fichas con permutaciones de 4 colores, dispuestas en 10 × 7. [6] En cualquier caso, los cuadrados son un subconjunto de los mosaicos de Wang , reduciendo mosaicos que son similares bajo rotación. Las soluciones se cuentan por miles. [7]
MacMahon Squares, junto con variaciones de la idea, se comercializó como Multimatch.
TetraVex
TetraVex es un juego de computadora que presenta al jugador una cuadrícula cuadrada y una colección de fichas, por defecto nueve fichas cuadradas para una cuadrícula de 3 × 3. Cada mosaico tiene cuatro números de un solo dígito, uno en cada borde. El objetivo del juego es colocar las fichas en la cuadrícula en la posición adecuada, completando este rompecabezas lo más rápido posible. Los mosaicos no se pueden girar y se pueden colocar dos uno al lado del otro solo si los números en los bordes adyacentes coinciden. [8] [9]
TetraVex se inspiró en "el problema de colocar mosaicos en el avión", como lo describe Donald Knuth en la página 382 del Volumen 1: Algoritmos fundamentales , el primer libro de su serie El arte de la programación informática . Fue nombrado por Scott Ferguson, el líder de desarrollo y arquitecto de la primera versión de Visual Basic, quien lo escribió para Windows Entertainment Pack 3 . [10]
TetraVex también está disponible como un juego de código abierto en la colección de juegos GNOME . [11]
Se puede contar el número posible de TetraVex. En un tablero hay pares horizontales y verticales que deben coincidir y números a lo largo de los bordes que se pueden elegir arbitrariamente. Por lo tanto hay opciones de 10 dígitos, es decir posibles tableros.
Decidir si un rompecabezas de TetraVex tiene una solución es, en general, NP-completo . [12] Su enfoque computacional involucra el algoritmo de Douglas-Rachford . [13] [14]
Hexágonos
Los serpentiles son las fichas hexagonales que se utilizan en varios juegos de estrategia abstractos como Psyche-Paths, Kaliko y Tantrix . Dentro de cada serpentina, los bordes están emparejados, restringiendo así el conjunto de mosaicos de tal manera que ningún color de borde aparece un número impar de veces dentro del hexágono.
Tres dimensiones
Matemáticamente, los rompecabezas de emparejar bordes son bidimensionales . Un rompecabezas de coincidencia de bordes en 3D es un rompecabezas que no es plano en el espacio euclidiano , por lo que implica colocar mosaicos en un área tridimensional como la superficie de un poliedro regular . Como antes, las piezas poligonales tienen bordes distinguidos para requerir que los bordes de las piezas adyacentes coincidan.
Los rompecabezas de combinación de bordes en 3D no están actualmente bajo la protección directa de una patente estadounidense, ya que la patente de 1892 de EL Thurston ha expirado. [2] Los ejemplos actuales de acertijos comerciales incluyen Dodek Duo , The Enigma, Mental Misery, [15] y la gama de acertijos tridimensionales de combinación de bordes de Kadon Enterprises. [dieciséis]
Incorporación de emparejamiento de bordes
El juego de mesa de Carcassonne emplea la combinación de bordes para restringir dónde se pueden colocar sus fichas cuadradas. El juego original tiene tres tipos de bordes: campos, carreteras y ciudades.
Ver también
Referencias
- ^ Erik D. Demaine , Martin L. Demaine . "Rompecabezas, emparejamiento de bordes y embalaje Polyomino: conexiones y complejidad" (PDF) . Consultado el 12 de agosto de 2007 .
- ^ a b "Página de rompecabezas de Rob: Coincidencia de bordes" . Archivado desde el original el 22 de octubre de 2007 . Consultado el 12 de agosto de 2007 .
- ^ Gardner, Martin (2009). Empaque de esferas, Lewis Caroll y Reversi . Prensa de la Universidad de Cambridge.
- ^ MacMahon, Percy Alexander (1921). Nuevos pasatiempos matemáticos . Gerstein - Universidad de Toronto. Prensa de la Universidad de Cambridge.
- ^ Steckles, Katie. Blackboard Bold: MacMahon Squares . Consultado el 10 de marzo de 2021.
- ^ Guy. Raíz cúbica de 31. Wang Tiles . Consultado el 12 de abril de 2021.
- ^ Wade Philpott (acreditado). Empresas Kadon. Multimatch . Consultado el 12 de abril de 2021.
- ^ Whittum, Christopher (2013). Dinamice la educación a través del código abierto . pág 32.
- ^ Gagné, Marcel (2006). Pasando a Ubuntu Linux .
- ^ "El nacimiento de Visual Basic" . Forestmoon.com . Consultado el 11 de mayo de 2010 .
- ^ "Licencia - README" . juegos de gnomos . gnome.org. 2011 . Consultado el 2 de octubre de 2012 .
- ^ "TetraVex es NP-completo" . Cartas de procesamiento de información, volumen 99, número 5, páginas 171–174. 15 de septiembre de 2006.
- ^ Bansal, Pulkit (2010). " Código para resolver Tetravex usando el algoritmo de Douglas-Rachford ". Consultado el 10 de marzo de 2021.
- ^ Linstrom, Scott B .; Sims, Brailey (2020). Encuesta: Sesenta años de Douglas Rachford. Prensa de la Universidad de Cambridge.
- ^ "Página de rompecabezas de Rob: Rompecabezas de patrones" . Consultado el 22 de junio de 2009 .
- ^ "Kadon Enterprises, más sobre Edgematching" . Consultado el 22 de junio de 2009 .
enlaces externos
- Colección de rompecabezas a juego de Erich
- Polígonos de coincidencia de color y bordes de Peter Esser [ enlace muerto ]
- Página de rompecabezas de Rob por Rob Stegmann
- Cuadrados a juego de bordes