Un rompecabezas de coincidencia de bordes es un tipo de rompecabezas de mosaico que implica colocar en mosaico un área con polígonos (normalmente regulares) cuyos bordes se distinguen con colores o patrones, de tal manera que los bordes de los mosaicos adyacentes coincidan.
Se sabe que los rompecabezas de combinación de bordes son NP-completos y pueden convertirse desde y hacia rompecabezas equivalentes y rompecabezas de embalaje de poliominó . [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 el Edge Match. Aplicación de rompecabezas para iPhone.
MacMahon Squares es el nombre dado a un rompecabezas matemático recreativo sugerido por el matemático británico Percy MacMahon , quien publicó un tratado sobre la coloración de los 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. Los mosaicos 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 Wang , lo que reduce los 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 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 ficha 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. Las fichas no se pueden girar y se pueden colocar dos una al lado de la otra solo si los números de los bordes adyacentes coinciden. [8] [9]
TetraVex se inspiró en "el problema de colocar mosaicos en el plano", 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, 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 juego de código abierto en la colección de juegos de 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 TetraVex tiene solución es, en general, NP-completo . [12] Su enfoque computacional implica el algoritmo de Douglas-Rachford. [13]
Los serpentiles son fichas hexagonales que se utilizan en varios juegos de estrategia abstracta 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 aparezca un número impar de veces dentro del hexágono.
Matemáticamente, los acertijos de combinación de bordes son bidimensionales . Un rompecabezas de combinación de bordes en 3D es un rompecabezas que no es plano en el espacio euclidiano , por lo que implica colocar en mosaico un área tridimensional como la superficie de un poliedro regular . Como antes, las piezas poligonales tienen bordes diferenciados para requerir que los bordes de las piezas adyacentes coincidan.
Los rompecabezas 3D de combinación de bordes no están actualmente bajo protección directa de patente en los EE. UU., ya que la patente de 1892 de EL Thurston ha expirado. [2] Los ejemplos actuales de rompecabezas comerciales incluyen Dodek Duo, The Enigma, Mental Misery, [14] y la gama de rompecabezas tridimensionales de combinación de bordes de Kadon Enterprises. [15]
El juego de mesa Carcassonne emplea la combinación de bordes para limitar dónde se pueden colocar las fichas cuadradas. El juego original tiene tres tipos de bordes: campos, caminos y ciudades.
