DANIEL RAMIREZ PORRAS N.
L 49
SUDOKU
Trabajo 9
DANIEL RAMIREZ PORRAS N.L 49
Sudoku ( en japons: sudoku, numero nico ) es un
pasatiempo cuyo objetivo es rellenar una cuadricula
de 9x9 celdas divididas en subcuadriculas de 3x3 con
las cifras del 1 al 9 partiendo de algunos nmeros ya
dispuestos en algunas de las celdas ( figura 1 ). No se
debe repetir ninguna cifra en una misma fila, columna
o subcuadricula. La resolucin del problema requiere
paciencia y ciertas dotes lgicas.
Se cree que este rompecabezas numrico puede
haberse originado en Nueva york en el ao 1979. En
ese tiempo, la empresa Dell Magazine publico este
puzle, ideado por Howard Garns, bajo el nombre de
Number Place ( el lugar de los nmeros ).
Es muy probable que el sudoku se creara a partir de
los trabajos de leonhard Euler, famoso matemtico
suizo del siglo XVIII, quien no creo el juego en si, sino
que utilizo el sistema llamado cuadrado latino para
realizar clculos de probabilidades.
Un cuadro latino es una matriz de nxn elementos, en
la que cada casilla esta ocupada por uno de los n
smbolos de tal modo que cada uno de ellos aparece
Trabajo 9
DANIEL RAMIREZ PORRAS N.L 49
exactamente una vez en cada columna y en cada fila
(figura 2).
Posteriormente Nikoli, empresa japonesa especializada
en pasatiempos para prensa, lo exporto a japon
publicndolo en el peridico Monthly Nilolist en abril
de 1984 bajo el tiulo sjiwa dokushin ni kagiru, que se
puede traducir como los numero deben estar solos.
Fue kaji maki presidente de nikoli, quien lke puso el
nombre. El nombre se abrevio a sudoku ( su: numero,
doku: solo) ya que es prctica comn en Japn tomar
el primer canj (caracteres empleados en la ortografa
japonesa) de palabras compuestas para abreviarlas.
En 1986, nikoli introdujo dos innovaciones que
garantizan la popularidad del rompecabezas: el
nmero de cifras que venan dadas estaran
restringida a un mximo de 30 y los puzles serian
simtricos (es decir, las celdas con cifras dadas
estaran dispuestas de formas simtrica).
REGLAS DEL JUEGO
El sudoku se representa normalmente como una tabla
de 9x9 compuesta por subtablas de 3x3 denominadas
regiones (tambin se le llaman cajas o bloques).
Algunas celdas ya contienen nmeros, conocidos
como nmeros dados o pistas. El objetivo es rellenar
las celdas vacas, con un nmero en cada una de ellas,
de tal forma que cada columna, fila o regin contenga
los nmeros del 1 al 9 solo una vez. Adems, cada
numero de la solucin aparece solo una vez en cada
una de las tres direcciones, de ah el los nmeros
deben estar solos que evocas el nombre del juego.
METODOS DE RESOLUCION
Trabajo 9
DANIEL RAMIREZ PORRAS N.L 49
La estrategia para resolver este rompecabezas se
puede considerar como la combinacin de tres
procesos: escaneo, marcado y anlisis.
ESCANEO: las reglas del juego exigen que la cifras
aparezcan solamente una vez en una lnea, columna o
subcuadricula. Entonces, cuando se quiera poner por
ejemplo la cifra 7 en una casilla, se puede controlar en
primer lugar si hay va otro 7 en el juego (figura 4). Si
es as lgicamente hay otra cifra. Con este mtodo se
puede ver en cada casilla libre, para encontrar la
solucin. Se trata de identificar qu lnea en una
regin particular puede contener un nmero
determinado mediante un proceso de eliminacin,
este proceso se repite entonces con todas las
columnas.
MARCADO: El escaneo se interrumpe cuando no
pueden descubrirse nuevos nmeros. En este punto es
necesario centrase en algn anlisis lgico. La
mayora encuentra til guiar este anlisis mediante el
marcado de nmeros candidatos en las celdas vacas.
Trabajo 9
DANIEL RAMIREZ PORRAS N.L 49
Hay dos notaciones populares, subndices y puntos
(figura 5).
En la notacin de subndice los nmeros candidatos se
escriben en pequeos en celdas. La desventaja es que
los puzles originales se publican en peridicos que
habitualmente no dejas demasiado espacio para
acomodar mas que unos dgitos. La segunda notacin
es un patrn de puntos con punto en la esquina
superior izquierda representando un 9. Esta notacin
tiene como ventaja que ahorra espacio. Sin embargo,
se requiere de puntos desplazados o marcas
inadvertidas lleva, inevitablemente, a confusin y no
son felices de borrar sin aadir mas confusin.
Figura 5. Mtodo del marcado.
ANALISIS: Hay dos aproximaciones principales:
eliminacin e y- si. La eliminacin, el proceso se
realiza mediante la sucesiva eliminacin de nmeros
candidatos para una o ms celdas, hasta dejar solo
una eleccin. Despus de lograr cada respuesta, debe
realizarse un nuevo escaneo habitualmente
comprobado el efecto del ltimo nmero. Hay una
serie de tcticas de eliminacin. Una de las ms
Trabajo 9
DANIEL RAMIREZ PORRAS N.L 49
comunes es el borrado del candidato no coincidente.
Las celdas con idntica configuracin de nmeros
candidatos se dice que coinciden si la cantidad de
nmeros candidatos en cada una es igual al nmero
de celdas que los contienen. Por ejemplo, swe dice
que las celdas coinciden con una particular fila,
columna o regin si dos celdas contienen el mismo par
de nmeros candidato (p q) y no otros, o si tres celdas
contienen el mismo triplete de nmeros candidatos
(p,q,r) que aparecen como candidatos en cualquier
lugar en la misma fila, columna o regin en celdas no
coincidentes, pueden ser borrados.
Trabajo 9
