SUDOKU

Historia

Este rompecabezas numérico, ahora llamado Sudoku, era ya conocido en la antigüedad aunque fue ignorado hasta hace algunos años. El Sudoku, en su versión actual, apareció en la prensa norteamericana a finales de los años setenta, más concretamente en 1979. En la revista “Math Puzzles and Logic Problems”, el editor del Puzzle Magazine publicó una rejilla de nueve cuadrados mágicos que llamó “Number Place” (el lugar de los números).

Ésta pasó casi inadvertida hasta catorce años más tarde, cuando el periódico japonés Monthly Nikolist en publicó en abril de 1984 este juego en el mensual de crucigramas “Monthly Nikolist”. La traducción japonesa era demasiado larga de escribir, por eso el juego volvió a ser bautizado utilizando la contracción de las palabras “Sūji wa dokushin ni kagiru” (数字は独身に限る), lo que significa aproximadamente “los números deben estar solos” (独身 significa literalmente “célibe, soltero”) o “una sola cifra debe ser inscrita”. Es por ello que finalmente el juego se ha hecho famoso con el nombre de Sūdoku (数独; sū = número, doku = solo).

Dos años después, los japoneses introducen una variante que consiste en dos innovaciones que lleva el juego a una mayor popularidad en el país del sol naciente: el número de las cifras no puede pasar de treinta y las rejillas se hacen simétricas, es decir que las cifras están distribuidas de forma rotatoria y simétrica en las casillas, lo que concede al conjunto un aspecto más estético.

Las rejillas del Sudoku se inspiran en los cuadros latinos, primos de los cuadros mágicos. Conocidos ya en la antigüedad-remonta probablemente al año 2.000 A.C.- se componen de rejillas cuadradas de n x n casillas en las cuales figuran n símbolos diferentes, donde:

* Cada casilla de la rejilla contiene un símbolo.
* Cada símbolo sómbolo soólo figura una vez en cada fila y cada columna.

El principio matemático fue estudiado por el suizo Leonhard Euler que vivió en el siglo XVII. Un hombre que fue honrado con el título de Prícipe de los Matemáticos el cual no debía de imaginarse que tres siglos más tarde se habría convertido en el padre de este pasatiempo apasionante.

Como se juega

El juego es muy simple: hay una cuadrícula de 81 cuadrados, divididos en 9 bloques de 9 cuadrados cada uno. Algunos de estos cuadrados ya vienen con una cifra escrita. Y el objetivo es rellenar los cuadrados vacíos de forma que los números del 1 al 9 aparezcan solamente una vez en cada fila horizontal, vertical y dentro de cada uno de los nueve bloques que forman la cuadrícula.

Ahora veremos ejemplos de cada una de estas estructuras:

Fila



Una fila está formada por 9 cuadrados de ancho. Los números del 1 al 9 únicamente aparecen 1 vez en cada uno de los cuadrados de una misma fila.

Columna



Una columna está formada por 9 cuadrados de alto. Los números del 1 al 9 únicamente aparecen 1 vez en cada uno de los cuadrados de una misma columna.

Bloque



Un bloque está formado por 9 cuadrados, 3 de alto por 3 de ancho. Los números del 1 al 9 únicamente aparecen 1 vez en cada uno de los cuadrados de un mismo bloque.

Métodos de resolución

La estrategia para resolver un puzle se puede considerar como la combinación de tres procesos: escaneo, marcado y análisis.

Escaneo
El escaneo se realiza desde el principio y periódicamente, durante toda la resolución. El escaneo puede tener que ser ejecutado varias veces entre periodos de análisis. El escaneo consta de dos técnicas básicas: trama cruzada y recuento, que pueden usarse alternativamente.

* Trama cruzada, se trata del escaneo de filas (o columnas) para identificar qué línea en una región particular puede contener un número determinado mediante un proceso de eliminación. Este proceso se repite entonces con las columnas (o filas). Para obtener resultados más rápidos, los números son escaneados de forma ordenada, según su frecuencia de aparición. Es importante realizar este proceso sistemáticamente, comprobando todos los dígitos del 1 al 9.
* Recuento 1-9 por regiones, filas y columnas para identificar números perdidos. El recuento basado en el último número descubierto puede aumentar la velocidad de la búsqueda. También puede ser el caso (es típico en puzles más difíciles) que el valor de una celda individual pueda ser determinado mediante un recuento inverso, esto es, escaneando su región, fila o columna para valores que no pueden ser, para ver cuál es el que falta.

Los resolutores avanzados buscan “contingencias” mientras escanean, esto es, acotan la ubicación de un número en una fila, columna o región o dos o tres celdas. Cuando esas celdas descansan todas en la misma fila (o columna) y región, pueden usarse con un propósito de eliminación durante la trama cruzada y el recuento. Puzles particularmente desafiantes pueden requerir el reconocimiento de múltiples contingencias, quizás en múltiples direcciones o incluso intersecciones – relegando la mayoría de los resolutores al marcado (como se describe más abajo). Los puzles que pueden ser resueltos sólo mediante escaneo, sin requerir la detección de contingencias se clasifican como puzles “fáciles”; otros puzles más difíciles, por definición, no pueden resolverse únicamente mediante escaneo.

Marcado
El escaneo viene a interrumpirse cuando no pueden descubrirse nuevos números. En este punto es necesario centrarse en algún análisis lógico. La mayoría encuentra útil guiar este análisis mediante el marcado de números candidatos en las celdas vacías. Hay dos notaciones populares: subíndices y puntos. En la notación de subíndice, los números candidatos se escriben en pequeño en las celdas. La desventaja es que los puzles originales son publicados en periódicos que habitualmente no dejan demasiado espacio para acomodar más de unos pocos dígitos. Si se usa esta notación, los resolutores crean, a menudo, una copia más grande de el puzle y emplean un lapiz afilado. La segunda notación es un patrón de puntos con un punto en la esquina superior izquierda representando un 1 y un punto en la esquina inferior derecha representando un 9. Esta notación tiene como ventaja que puede usarse en el puzle original. Se requiere destreza para el emplazamiento de los puntos, porque puntos desplazados o marcas inadvertidas llevan, inevitablemente, a confusión y no son fáciles de borrar sin añadir más confusión.

Análisis
Hay dos aproximaciones principales – eliminación y “y-si”.

* En eliminación, el progreso se realiza mediante la sucesiva eliminación de números candidatos para una o más celdas, hasta dejar sólo una elección. Después de lograr cada respuesta, debe realizarse un nuevo escaneo (habitualmente comprobando el efecto del último número). Hay una serie de tácticas de eliminación. Una de las más comunes es el “borrado del candidato no coincidente”. Las celdas con idéntica configuración de números candidatos se dice que coinciden si la cantidad de números candidatos en cada una es igual al número de celdas que los contienen. Por ejemplo, se dice que celdas coinciden con una particular fila, columna o región si dos celdas contienen el mismo par de números candidatos (p,q) y no otros, o si tres celdas contienen el mismo triplete de números candidatos (p,q,r) y no otros. Estas son, esencialmente, contingencias coincidentes. Estos números (p,q,r) que aparecen como candidatos en cualquier lugar en la misma fila, columna o región en celdas no coincidentes, pueden ser borrados.
* En la aproximación “y-si”, se selecciona una celda con sólo dos números candidatos y se realiza una conjetura. Las etapas de arriba se repiten a menos que se encuentre una duplicación, en cuyo caso el candidato alternativo es la solución. En términos lógicos este método se conoce como reducción al absurdo. Nishio es una forma limitada de esta aproximación: para cada candidato para una celda, la cuestión que se plantea: ¿entrará un número particular de una configuración en otro emplazamiento? Si la respuesta es sí, entonces ese candidato puede ser eliminado. La aproximación “y-si” requiere un lapiz y una goma. Esta aproximación puede ser desaprobada por puristas lógicos por demasiado ensayo y error pero puede llegar a soluciones clara y rápidamente.

Idealmente, se necesita encontrar una combinación de técnicas que eviten alguno de los inconvenientes de los elementos de arriba. El recuento de regiones, filas y columnas puede resultar aburrido. Escribir números candidatos en celdas vacías puede consumir demasiado tiempo. La aproximación “y-si” puede ser confusa a menos que seas bien organizado. El quid de la cuestión es encontrar una técnica que minimice el recuento, el marcado y el borrado.

Fuente: Wikipedia