Algoritmo
Código Gray
Veamos como se puede solucionar Los Aros
Chinos utilizando el Código Gray
Hago una distinción según la
posición inicial que tenga el puzzle, Clásica o Extrema.
Posición
Inicial Extrema
Posición
Inicial Clásica
Posición
Inicial Extrema
Supongamos que empezamos con Los Aros Chinos
en el estado de la figura, que denomino Posición Inicial Extrema.
 |
Figura 14. Posición
Inicial Extrema |
El Código Gray nos permite solucionar
el puzzle, indicándonos la manipulación en cada momento
Veamos el sistema:
Supongamos que empezamos con Los Aros Chinos
en el estado de la figura, que denomino Posición Inicial Extrema.
EDCBA
10000
En la tabla del Código Gray es la última.
Sólo tenemos que realizar la manipulación
oportuna para cambiar al estado anterior en la tabla.
La primera manipulación es el aro
A, meterlo (1).
EDCBA
10001
Después manipulamos el aro B, meterlo
(1)
EDCBA
10011
Después manipulamos el aro A, sacarlo
(0)
EDCBA
10010
Repetimos el proceso hasta alcanzar La Posición
Final, La primera en la tabla, con todos los aros libres.
EDCBA
00000
Para pasar de un estado al anterior en la
tabla, sólo cambia un bit o columna, es consecuencia de la propiedad
Cíclica. Es el aro que tenemos que manipular.
Para introducir todos los aros realizamos
el proceso contrario, a este proceso contrario a la SOLUCION, lo
denomino NOICULOS.
Podemos realizar una nueva tabla, para realizar
estos procesos, añadiendo una columna que indique el aro X a manipular.
Figura 15.
Para realizar la tabla conviene intercalar
filas, de tal modo que la información con el aro a manipular este
entre dos filas de los estados del puzzle.
Esta tabla permite fácilmente realizar
el proceso SOLUCION y NOICULOS.
Aro Manipulable
|
EDCBA |
Aro X |
00000 |
|
|
A |
00001 |
|
|
B |
00011 |
|
|
A |
00010 |
|
|
C |
00110 |
|
|
A |
00111 |
|
|
B |
00101 |
|
|
A |
00100 |
|
|
D |
01100 |
|
|
A |
01101 |
|
|
B |
01111 |
|
|
A |
01110 |
|
|
C |
01010 |
|
|
A |
01011 |
|
|
B |
01001 |
|
|
A |
01000 |
|
|
E |
11000 |
|
|
A |
11001 |
|
|
B |
11011 |
|
|
A |
11010 |
|
|
C |
11110 |
|
|
A |
11111 |
|
|
B |
11101 |
|
|
A |
11100 |
|
|
D |
10100 |
|
|
A |
10101 |
|
|
B |
10111 |
|
|
A |
10110 |
|
|
C |
10010 |
|
|
A |
10011 |
|
|
B |
10001 |
|
|
A |
10000 |
|
Figura 15. Tabla de Manipulaciones
Número de Manipulaciones Necesarias
Para solucionar Los Aros Chinos desde La
Posición Inicial Extrema necesitamos realizar 31 manipulaciones.
En general para una versión de N aros
necesitamos 2N -1.
Posición
Inicial Clásica
Supongamos que empezamos con Los Aros Chinos
en el estado de la figura 16, que denomino Posición Inicial Clásica.
 |
Figura 16. Posición
Inicial Clásica |
La Posición Inicial Clásica, tiene
todos los aros dentro.
EDCBA
11111
Se soluciona de igual modo la según
la tabla del Código Gray.
Es una posición intermedia en la tabla
del Código Gray.
Comenzamos en la fila correspondiente al
estado del puzzle.
Vamos cambiando al estado anterior, hasta
obtener la Posición Final
¿ Cuál es la posición
inicial más complicada ?
La más alejada de la solución
es la última, La Posición Inicial Extrema, sólo el
aro E dentro.
Curioso, ya veremos si es la más complicada
Número de Manipulaciones Necesarias
Para solucionar Los Aros Chinos desde La
Posición Inicial Clásica necesitamos realizar 21 manipulaciones.
Basta mirar en la tabla el valor decimal asociado a la posición
inicial.
En general para una versión de N aros,
podemos utilizar una fórmula diseñada por Gros.
Para N par, 1/3 *(2N+1 -2)
Para N impar, 1/3 *(2N+1 -1)
|