Las clases fueron desarrolladas usando PHP 5, específicamente la versión 5.2, en un sistema operativo GNU/Linux Ubuntu 9.10 de 32 bits. También se hicieron pruebas en un Debian 5.0 y en un Ubuntu 10.04, ambos de 64 bits. Se debe tener habilitada la extensión GMP, que en Ubuntu se instala con: $ sudo apt-get install php5-gmp
La estructura general del problema se modela primero mediante una clase abstracta (State.php) que representa un estado genérico de cualquier juego. La implementación concreta de esa clase para este caso en particular modela la configuración de un tablero de juego de Peg Solitaire. Lo más natural para modelarlo sería usar una matriz que represente cada uno de los casilleros, pero se optó por representarlos como vectores de bit para mejorar la velocidad y el almacenamiento, dado que se puede generar una cantidad importante de estados durante la búsqueda. Dado que un tablero de 7x7 tiene más casilleros que los que se pueden representar con un entero de 32 bits, se optó por usar la extensión GMP (GNU Multiple Precision) para poder trabajar con números lo suficientemente grandes. Lo más interesante de la clase es que para cada estado se generan todas sus posibles alternativas por rotación/reflexión, para lo cual se impone como condición que el tablero sea simétrico en esos aspectos.
Existe otra clase abstracta que se usa para representar un problema, o en este caso, para establecer las reglas del juego. La clase PegSolitaireProblem implementa estas reglas, que en resumen son determinar si un estado es solución para problema, y dado un estado determinar los siguientes posibles estados partiendo desde él.
La última clase abstracta modela un algoritmo de búsqueda de estados, es decir, dados un problema y un estado inicial, determina cuándo se ha alcanzado una solución. La clase tiene métodos útiles para determinar cuando un estado ya ha sido visitado. También se considera la posibilidad de que estados similares ya hayan sido visitados, para poder acortar así el espacio de búsqueda. Finalmente, se implementa una versión del algoritmo de búsqueda Depth First Search, que es básicamente un algoritmo recursivo que para cada estado obtiene los siguientes estados y los recorre hasta encontrar una solución. Las mejoras que se han agregado al algoritmo son el poder cortar la recursión una vez que se alcanzó una solución y el hecho de detectar estados ya visitados para poder cortar ramas del árbol de recursión.
Para poder probar las clases se adjunta un archivo 'test.php' que se debe ejecutar desde la línea de comandos. Si se observa el mismo, se establece como estado inicial el tablero propuesto en el ejercicio, pero se pueden comentar/descomentar una serie de estados para partir desde otro estado inicial.
Para el tablero propuesto (que se denomina "Inglés") se tarda aproximadamente 30 segundos en alcanzar una solución en un Intel Core 2 Duo E8400 de 3.00 Ghz. Luego de encontrada la primera solución, se apela a la clase abstracta de búsquedas para que genere todas las posibles alternativas de solución mediante las rotaciones/reflexiones del tablero ya mencionadas.
Dado que la salida del script puede ser demasiado abundante (información de debug y luego se imprimen los caminos que llevan a la solución) se recomienda ejecutar el script y redirigir la salida hacia un archivo para poder analizarlo, es decir: $ php test.php > results
Lo que resta para cumplir los objetivos requeridos sería implementar la interacción con la base de datos, para lo cual probablemente se añada una clase que se encargue de almacenar una solución y la secuencia de estados (o movidas) que permiten alcanzarla.