Un juego de enlace numérico

El juego: Considere una array de cuadrados n × n. Algunos de los cuadrados están vacíos, algunos son sólidos y algunos cuadrados no sólidos están marcados con números enteros 1, 2, 3, … Cada número entero ocupa exactamente dos cuadrados diferentes en el tablero. La tarea del jugador es conectar las dos apariciones de cada número entero en el tablero mediante un camino simple usando solo movimientos horizontales y verticales. No se permite que dos caminos diferentes se crucen entre sí. Ningún camino puede incluir ningún cuadrado sólido (está prohibido que aparezcan cuadrados sólidos en cualquier camino). Finalmente, todos los cuadrados no sólidos deben ser llenados por las rutas.

El algoritmo: para preparar un rompecabezas aleatorio válido con un tamaño de tablero dado n × n, primero generamos caminos aleatorios simples que no se cruzan entre sí en el tablero. Si quedan algunos cuadrados aislados fuera de todos los caminos generados, márquelos como sólidos (prohibidos). Luego proporcionamos los puntos finales de los caminos y la lista de cuadrados sólidos como rompecabezas.
Por lo tanto, primero generamos una solución y luego resolvemos el rompecabezas a partir de la solución. Los caminos y los cuadrados sólidos dividen el tablero n × n. Usamos una estructura de datos de búsqueda de unión para generar esta partición. La estructura de datos trata con los subconjuntos del conjunto de n^2 cuadrados en el tablero.

Pseudocódigo:

1. Ubique los cuadrados (i, j) y (k, l) al azar en el tablero de modo que:
   (a) (i, j) y (k, l) sean vecinos entre sí, y
   (b) ninguno (i, j) ni (k, l) pertenece a ningún camino generado hasta el momento. Si no se encuentra ese par de cuadrados en todo el tablero, devuelve FALLO /* Aquí, (i, j) y (k, l) son los primeros dos cuadrados en el nuevo camino que se construirá. */
2. Haz una unión de los dos árboles de búsqueda de unión que contienen (i, j) y (k, l).
3. Repita siempre que la ruta actual se pueda extender:
   Renombrar (i, j) = (k, l).
   Ubique un cuadrado vecino aleatorio (k, l) de (i, j) tal que:
   (a) (k, l) no pertenezca a ningún camino generado hasta el momento (incluido el actual)
   (b) el único vecino (k , l) tiene en la ruta de corriente parcialmente construida es (i, j).
4. Si no se puede encontrar tal vecino (k, l), la ruta no se puede extender más, así que rompa el ciclo
5. De lo contrario, haga la unión de los dos árboles de búsqueda de unión a los que pertenecen (i, j) y (k, l).
6. Establezca las banderas de punto final de los dos cuadrados que están al principio y al final de la nueva ruta.
7. Volver ÉXITO

Código de Ejecución Completo del Artículo .

Este artículo es una contribución de Vaibhav Aggarwal. Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo electrónico a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.