El agujero
¿Cuántos posibles sudokus completos hay?
¿Cuántas formas posibles hay de rellenar un sudoku de forma que se cumplan las reglas usuales? Ésta no es una pregunta sencilla de contestar. En mayo de 2005, Bertram Felgenhauer y Frazer Jarvis calcularon la respuesta: hay 6670903752021072936960 formas de hacerlo (En su página hay un artículo sobre esto y en un foro de www.sudoku.com hay una discusión sobre el tema). Llegaron a este resultado calculando las posibilidades con un programa de ordenador, después de reducir cuidadosamente la búsqueda usando las simetrías del juego. Esto último era necesario porque sin más arma que la fuerza bruta las combinaciones de números a comprobar son mucho mayores de lo que puede abarcar un ordenador actual en un tiempo razonable: por ejemplo, si se prueban todas las formas de colocar los números del 1 al 9 en cada una de las cajas 3x3 que forman el cuadro 9x9, el número de posibilidades es (9!)^9, más de 10^50.
En cierta forma es una decepción que no se pueda llegar a este resultado de una forma más elegante, especialmente porque da la sensación contraria, probablemente equivocada. Es fácil calcular cuántas formas hay de rellenar, por ejemplo, las tres cajas superiores; pueden estudiarse las simetrías de las reglas y reducir mucho la cantidad de soluciones que hay que contar y luego pueden enumerarse mil casos menores, pero al final hay tantas casillas que dependen de otras que resulta imposible terminar el cálculo de alguna forma que no incluya a un ordenador. El hecho de que el número final de soluciones se factorice como 9! × 722 × 27 × 27,704,267,971 hace pensar que encontrarlo a mano es improbable, ya que el último factor es primo, y por tanto no puede encontrarse con argumentos del tipo "hay X formas de resolver esta parte, y esto debe hacerse n veces, luego el número de formas es X^n". Esto no dice nada sobre otras formas de razonamiento, claro; en particular nada dice que no pueda encontrarse un razonamiento como "hay tantas formas de resolverlo en este caso, más tantas otras en este otro caso, lo que da un total de..."
Pero, ¿por qué este interés por encontrarlo a mano, si ya lo ha hecho un ordenador? Bueno, hay varios motivos, que no sé si lo justifican demasiado bien: el primero de ellos es el deseo de saber si se puede o no, por curiosidad. Otro es que una solución "para humanos" conlleva una mejor comprensión del problema: es muy conocida la historia de la demostración del teorema de los cuatro colores y la polémica sobre si una demostración por ordenador es válida o no, o si nos ayuda en algo a entender el problema. (Otro ejemplo: la búsqueda de un plano proyectivo de orden 10).
Para mí, éste último motivo es muy importante. Sin embargo, no tiene sentido esforzarse en encontrar una demostración sencilla cuando parece que no la hay, y además ésta tal vez no aporte mucho más. Digamos que pueden ocurrir dos cosas:
- Hay algunas preguntas que se pueden contestar por medio del razonamiento.
- Hay algunas que no.
Volviendo al número de soluciones del sudoku, hay un curioso razonamiento que da un número muy aproximado al de las soluciones. Copio un mensaje de Kevin Kilfoil del foro mencionado al principio de este texto:
Lets try this from a whole different direction:
Step A: Pretend that the only 'rule' was the 'block' rule, and that the row and column rules did not exist. Then each block could be arranged 9! ways, or 9!^9 ways to populate the puzzle (1.0911*10^50 'solutions').
Step B1: If we then say 'let us add a rule about unique values in a row', then the top three blocks can be filled as follows: Block 1: 9! ways Block 2: 56 ways to select which values go in each 3-cell row, and 3! ways to arrange them (remember that we haven't invented a column rule yet). Block 3: with 1 and 2 filled, the values that go in each row is now defined, but each row can be arranged 3! ways. Therefore, we have 9! * 56 * 3!^6 ways to fill the top three blocks, and this value cubed to fill all nine blocks. (or 8.5227*10^35 solutions). Note that this represents a 'reduction ratio' (denoted as R) of 1.2802*10^14, by adding this one new rule.
Step B2: But we could have just as easily added a 'unique in columns' rule, and achieved the same results downward instead of across, with the same value of R.
Step C: (and here is where my solution is not rigorous) What if we assume that each of these rules would constrain the number of valid solutions by exactly the same ratio? Then there would be a combined reduction ratio of R^2. So the intitial value of 1.0911*10^50 solutions would reduce by a factor of R^2, or 1.639*10^28, leaving 6.6571*10^21 valid solutions.
Este argumento heurístico es muy interesante, y más cuando la diferencia entre este resultado y el real es de sólo un 0.2%.
Comparo este resultado con el número exacto. La pregunta que me queda en el fondo es: ¿cuáles de los resultados que pueden calcularse en seis horas con un ordenador son interesantes? ¿Cuáles de los razonamientos que dan resultados inexactos son interesantes? Supongo que estas preguntas son demasiado generales para tener respuesta, así que, siendo consistente con lo anterior, tal vez lo mejor es buscar otras que sí podamos contestar.
