El juego del gato tiene muchas virtudes: por una parte es un juego entre dos personas que es elemental y que pronto se aprende cómo ganar o cómo no perder. Su complejidad no es ni remotamente como la de otros juegos de suma-cero e información perfecta, pero es un juego muy interesante para enseñar mucho en computación.
En este reto no estamos buscando que se escriba un programa que juegue al gato, sino que haga algo más trivial, dé todas las posiciones posibles de los juegos de gato legales. Por ejemplo, la siguiente figura muestra una posición del gato que no se puede alcanzar jugando (aunque se juegue mal) y por tanto no se considera una posición “legal”, para decirle de algún modo.

La pregunta es entonces: ¿Cuántas posiciones legales tiene el juego del gato? De acuerdo con este sitio, hay 9 formas diferentes de empezar un juego, y entonces, el rival tendrá 8 maneras diferentes de responder. Entonces de nuevo el primer jugador tendrá 7 casilleros donde poner su tirada y así sucesivamente, es decir: 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 9! = 362880. Pero este número parece demasiado grande. Supongamos que un juego termina en el sexto movimiento. Claramente habrán quedado casillas sin llenar, pero ya no se necesitan llenar. Si las llenamos entonces puede ser que cuente como más de un juego.
Se puede hacer un análisis más cuidadoso, por ejemplo: cuántos son los juegos que acaban …