Enlace numérico

Un ejemplo sencillo de un rompecabezas Numberlink.

Solución al rompecabezas Numberlink

Numberlink es un tipo de rompecabezas de lógica que consiste en encontrar caminos para conectar números en una cuadrícula.

El jugador debe emparejar todos los números iguales de la cuadrícula con líneas continuas (o caminos). Las líneas no pueden bifurcarse ni cruzarse entre sí, y los números deben quedar al final de cada línea (es decir, no en el medio).

Se considera que un problema está bien diseñado solo si tiene una solución única ^{[ 1 ]} y todas las celdas de la cuadrícula están llenas, aunque algunos diseñadores de Numberlink no estipulan esto. ^{[ 2 ]}

Otra regla que se incluye en algunas versiones del rompecabezas es que un camino no puede tener giros en U, ya que estos permitirían acortarlo sin cambiar los demás caminos. ^{[ 2 ]}

En 1897, una forma ligeramente diferente del rompecabezas se imprimió en el Brooklyn Daily Eagle , en una columna de Sam Loyd . ^{[ 3 ]} Otra versión temprana impresa de Number Link se puede encontrar en el libro de Henry Ernest Dudeney Amusements in mathematics (1917) como un rompecabezas para automovilistas (rompecabezas n.° 252). ^{[ 4 ]} Este tipo de rompecabezas fue popularizado en Japón por Nikoli como Arukone (アルコネ, Alphabet Connection ) y Nanbarinku (ナンバーリンク, Number Link ). La única diferencia entre Arukone y Nanbarinku es que en Arukone las pistas son pares de letras (como en el rompecabezas de Dudeney), mientras que en Nanbarinku las pistas son pares de números.

Se han lanzado versiones de esto conocidas como Wire Storm, Flow Free y Alphabet Connection como aplicaciones para iOS , Android , Web y Windows Phone . ^{[ 5 ] [ 6 ] [ 7 ] [ 8 ] [ 9 ] [ 10 ] [ 11 ]}

Como problema computacional , encontrar una solución a un rompecabezas Numberlink dado es NP-completo , para las versiones en las que el problema es solo conectar todos los pares de números, ^{[ 12 ] [ 13 ]} para caminos sin giros en U que deben cubrir todos los cuadrados de la cuadrícula, ^{[ 14 ]} y para la versión "zig-zag" en la que todos los cuadrados deben ser cubiertos pero se permiten giros en U. ^{[ 2 ]}

Estos resultados de dificultad requieren que el número de pares de números crezca con el tamaño del rompecabezas. Para un número fijo de pares, incluso en cuadrículas arbitrariamente grandes, conectar todos los pares (sin necesariamente llenar la cuadrícula) se puede resolver en tiempo polinomial como una instancia del problema de caminos disjuntos en vértices en grafos no dirigidos. ^{[ 15 ]}

• Lista de tipos de rompecabezas Nikoli

• Versión en línea de Numberlink en HTML5