Marble puzzle

Ejercicio de Entrenamiento Problema 1 de Hasni-Lodhi
Adaptacion M. Cebollada, M. Eschoyez, C. Barto
Octubre 2011
1. Enunciado
Hay que resolver un Rompecabezas de Bolitas o \Marble Puzzle" comose lo denomina, de tama~no 4, que
consiste en 4 bolitas rojas, 4 bolitas negras y un liston de madera con 9 perforaciones. Las bolitas de un color son
colocadas alternativamente con las del otrocolor en cada uno de los agujeros a partir de la izquieda, quedando
libre la perforacion de la extrema derecha.
El objetivo del juego consiste en poner las bolitas rojas de un lado y las negras delotro, dejando la perforacion
libre en el centro.
En general este rompecabezas de N bolitas consiste en N bolitas rojas, N bolitas negras y un liston con 2N+1
perforaciones.
Solo se permiten dostipos de movimientos, Ud puede deslizar una bolita a una perforacion adjacente libre o
puede saltar a una perforacion libre por encima de una bolita de distinto color. Ud no puede saltar 2 o masbolitas
de una vez. Escriba un programa que simule el proceso de solucion del Rompecabezas de Bolitas para tama~nos de
1  N  10.
Utilice un arreglo de caracteres de tama~no 2N+1, representando elliston de madera y utilice el caracter \X"
para representar las bolitas negras, el caracter \O" para representar las bolitas rojas y el caracter \E" para la
perforacion libre. En un arreglo almaceneseries de caracteres que representan la conguracion de las bolitas en el
liston. Abajo un ejemplo del Rompecabezas de Bolitas de tama~no N=2.
Movimientos Rompecabezas de Bolitas N=2 Ejemplo deSalida
Estado Inicial X O X O E
muevo bolita celda 3 a 4 X O X E O
salto bolita celda 1 a 3 X E X O O
muevo bolita celda 2 a 1 X X E O O
Paso 1 Resuelva
El rompecabezas en papel para N=3 y N=6,Use las tablas de abajo para observar los calculos necesarios. Des.=
deslizamiento, sal.=salto, desde= desde celda, a= a celda, Dir.=direccion Izq o Der.
Cuadro 1: Rompecabezas de Bolitas N=3
0 1 2...