Por si alguien le interesa, en esta página hay una colección de códigos fuente en multitud de lenguajes (¡hasta en TeX!) que implementan este juego. A veces, incluso te dan la solución.
Yo juraria que lo tuve que hacer en lisp, pero no lo tiene en ese lenguaje, aunque si en prolog.