La comprobación de la corrección de un diario de Sudoku acababa de terminar, me di cuenta de un curioso patrón en una de las células de 3x3:
1 9 3
8 2 4
7 6 5
Tenga en cuenta que cada uno de los números es adyacente en los 8 puntos cardinales para el número que está inmediatamente por encima y por debajo de ella, así que se puede recorrer en orden, sin saltarse ninguna. Ciertamente, esto no es siempre el caso. Considere la posibilidad de:
1 2 3
5 6 4
7 8 9
Este tiene una brecha entre el 4 y el 5, así que no hay ruta de acceso completa aquí. Me hice una nota mental para comprobar que en la posterior rompecabezas para ver si sucedió de nuevo - parece bastante raro. Incluso con nueve de 3x3 casillas en cada puzzle, una vez por día durante más de un mes, aún tengo que encontrar otro. Además, el original es especialmente inusual como se crea un Ciclo Hamiltoniano, no sólo un Camino, como la 1 y la 9 también son adyacentes. Esto también no es siempre cierto. Considere la posibilidad de:
1 2 3
6 5 4
7 8 9
Esto tiene un Camino Hamiltoniano de 1-9, pero no un Ciclo porque los extremos no son adyacentes. Mi pregunta es, en una cuadrícula de 3x3, cómo muchos de los posibles (3x3)! permutaciones resultado en un Camino Hamiltoniano, y cómo muchos de ellos son también los Ciclos Hamiltonianos? Existe una formula para estos que puede ser generalizado para 4x4, 5x5, o de otros NxN cuadrículas? (3x3 es el mínimo, como con 2x2, la respuesta es trivialmente 100%, ya que todos los números son adyacentes el uno al otro.)
Los ciclos parecen más fáciles de precisar, al menos en 3x3. Hay básicamente dos formas, como lo que yo puedo decir, que no diagonal de cruce y uno con: (Disculpas por crudo de arte ASCII)
1 2 3 ┌────/ 1 2 3 ┌────┐
9 4 5 │ /─┐ 9 7 4 │ /\/
8 7 6 └────┘ 8 5 6 │/ /\
que se puede girar y se volcó en 8 configuraciones de cada uno, y, a continuación, para cada configuración, los números pueden ser un ciclo en una de las 9 posiciones, o invertido para otro 9. Así que usted consigue 2 x 8 x 9 x 2 = 288. Tengo más dificultad en encontrar todos los no-Cíclico de las rutas, o viniendo para arriba con una solución generalizada para grandes redes.
