El Sofista

Sudoku. Diferencia entre el método deductivo y el conjetural.

Preguntaron en Snark por la diferencia entre el método normal de resolución de problemas de sudoku y el método de las conjeturas.

Como creo que éste es un tema que podría interesarle a muchos, copio una versión pulida de mi respuesta para llevar el debate a un círculo más amplio.

Hay dos grandes métodos de resolución de sudokus, uno es el de deducción directa y el otro es por vía indirecta, también llamado por reducción al absurdo, por conjeturas, o por ensayo y error.

Ambos métodos son lógicos y se basan en métodos formales de razonamiento. Se diferencian por cómo ponen a prueba la verdad del enunciado que afirma el número a colocar en la grilla.

En el primer método, la deducción directa, ese enunciado —por ejemplo, En X1Y1 va 5— es la conclusión deducida de una conjunción de premisas o enunciados que describen los estados o las relaciones de los números puestos en la grilla del sudoku. Como se trata de una deducción y partimos de premisas verdaderas, las inferencias son necesarias y se mantiene el valor de verdad a lo largo de todo el razonamiento. Ahora bien, también es posible que —a causa de un error en la descripción de la grilla actual— una o más de las premisas que forman parte del razonamiento sean falsas. Sin embargo, como una conclusión verdadera puede inferirse lógicamente de premisas falsas, el hecho de partir de premisas falsas no significa que necesariamente habrá de llegarse a una contradicción en algún momento posterior del juego, aunque sea muy probable. De cualquier manera, en la deducción directa se tiene siempre la certeza de operar con enunciados verdaderos.

En el segundo método, el de las conjeturas, se parte de un enunciado cuya verdad se supone —por ejemplo, En X1Y1 podría ir 5— y el objetivo del razonamiento es poner a prueba el valor de verdad de ese enunciado. Se demuestra que el enunciado es falso cuando luego de una o más inferencias se arriba a una contradicción o imposibilidad de colocar un número en la grilla —por eso el procedimiento se llama el método del absurdo—, lo que obliga a regresar al punto de partida. En cambio, cuando la conjetura resulta verdadera el juego continúa desarrollándose sin necesidad de volver al punto de partida.

En resumen: en la deducción directa se tiene una verdad conocida, mientras que en el método de las conjeturas la verdad está aún por probarse.

Ahora bien, ¿por qué se dice que es mejor utilizar el método de deducción directa? No sólo porque es más elegante —aunque es difícil definir en qué consiste esa elegancia— sino porque es más económico, por cuanto la deducción directa es el camino con menos pasos para resolver un problema de sudoku. Claro, el criterio de economía vale cuando se trata de humanos, pero no tanto cuando hablamos de computadoras (por lo general éstas tardan muy poco en resolver problemas de sudoku, usando uno u otro método, o una combinación de ambos).

Pero con esto último no quiero decir que el método de las conjeturas no sirva para nada. También es un método necesario, porque no todos los problemas de sudoku pueden resolverse por medio de la deducción directa; por ejemplo, los problemas con más de una solución sólo se puede solucionar con el método de las conjeturas.

Nota: Para evitar confusiones terminológicas conviene distinguir entre métodos de razonamiento y técnicas de resolución. Los primeros son las formas de razonamiento estudiados por la Lógica y, por lo tanto, aplicables a todos los campos posibles; en cambio, las técnicas son aplicaciones de aquellas formas de razonamiento a un campo en particular, como los problemas de sudoku. Reconozco que yo también contribuí a esta confusión: por ejemplo, al método de la exclusión por par alineado no debería haberlo llamado así, sino técnica o procedimiento. Se hace camino al andar.

escrito por el sofista @ sábado, abril 15, 2006