Un rompecabezas de combinación de bordes es un tipo de rompecabezas de mosaicos que implica cubrir un área con polígonos (normalmente regulares) cuyos bordes se distinguen con colores o patrones, de tal forma que los bordes de los mosaicos adyacentes coincidan.
Se sabe que los rompecabezas de coincidencia de bordes son NP-completos y capaces de convertirse en y desde rompecabezas equivalentes y rompecabezas de empaquetamiento de poliominós . [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 de combinación de bordes comerciales incluyen el rompecabezas Eternity II , Tantrix , la gama de rompecabezas de combinación de bordes de Kadon Enterprises y la aplicación Edge Match Puzzles para iPhone.
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 los bordes de una variedad de formas en 1921. [4] Este rompecabezas en particular utiliza 24 fichas que consisten en todas las permutaciones de 3 colores para los bordes de un cuadrado. Las fichas deben estar dispuestas en un área rectangular de 6 × 4 de modo que todos los bordes coincidan y, además, solo se utiliza un color para el borde exterior del rectángulo. [5]
Este rompecabezas se puede extender a fichas con permutaciones de 4 colores, dispuestas en 10×7. [6] En cualquier caso, los cuadrados son un subconjunto de las fichas de Wang , lo que reduce las fichas 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 ordenador que presenta al jugador una cuadrícula cuadrada y una colección de fichas, por defecto nueve fichas cuadradas para una cuadrícula de 3x3. 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 en los bordes adyacentes coinciden. [8] [9]
TetraVex se inspiró en "el problema de teselar 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, 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 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, tableros posibles.
Decidir si un rompecabezas TetraVex tiene una solución es en general NP-completo . [12] Su enfoque computacional implica el algoritmo Douglas-Rachford. [13]
Las serpentiles son las fichas hexagonales que se utilizan en varios juegos de estrategia abstracta como Psyche-Paths, Kaliko y Tantrix . Dentro de cada serpentile, los bordes están emparejados, lo que restringe el conjunto de fichas de tal manera que ningún color de borde aparece un número impar de veces dentro del hexágono.
Matemáticamente, los rompecabezas de emparejamiento de aristas son bidimensionales . Un rompecabezas de emparejamiento de aristas en 3D es un rompecabezas que no es plano en el espacio euclidiano , por lo que implica cubrir con mosaicos un área tridimensional como la superficie de un poliedro regular . Como antes, las piezas poligonales tienen aristas diferenciadas para requerir que las aristas de las piezas adyacentes coincidan.
Los rompecabezas de combinación de bordes en 3D no están actualmente bajo protección directa de patentes en los EE. UU., ya que la patente de 1892 de EL Thurston ha expirado. [2] Entre los ejemplos actuales de rompecabezas comerciales se incluyen Dodek Duo, The Enigma, Mental Misery [14] y la gama de rompecabezas de combinación de bordes tridimensionales de Kadon Enterprises [15] .
El juego de mesa Carcassonne utiliza el sistema de emparejamiento de bordes para limitar dónde se pueden colocar las fichas cuadradas. El juego original tiene tres tipos de bordes: campos, caminos y ciudades.
