Técnicas DE Resolución DE Sudokus PDF

Preview

Summary

Técnicas DE Resolución DE Sudokus...

Description

TÉCNICAS DE RESOLUCIÓN DE SUDOKUS

El Sudoku es un rompecabezas que se resuelve mediante lógica (no son necesarios ni adivinar ni la aritmética). La idea básica para completar los rompecabezas es encontrar celdas para las que conocemos un único candidato. Lo Básico: Las reglas del Sudoku son que debemos rellenar con un número cada celda de la cuadrícula, utilizando los números del 1 al 9. Las restricciones son que sólo podemos usar cada número una sola vez en cada fila, cada columna y cada uno de los recuadros de 3x3. Echemos un vistazo a este puzzle incompleto... Los tres interrogantes se encuentran en sitios en los que no hay ningún valor, pero en los que fácilmente podemos encontrar un número para cada uno. Si el resto de la línea o recuadro está completo, con un simple proceso de eliminación sabremos cual es el valor que falta. En este caso, el único número que falta de la fila horizontal es el 3. El número que falta en la columna es el 9. En del recuadro es un 4. TÉCNICAS FÁCILES La mayor parte de Sudokus de los que podemos encontrar en los periódicos se pueden resolver con dos sencillas técnicas: TÉCNICA 1: POSICIÓN ÚNICA Ésta es la técnica más sencilla a aplicar a ojo, y la que más gente aplica cuando resuelve Sudokus. Escojamos una fila, columna o recuadro y después recorramos los números que no hayamos puesto aún. Debido al resto de emplazamientos, las posiciones en las que podemos colocar ese número serán limitadas. A menudo, habrá dos o tres lugares que serán válidos, pero si somos afortunados, sólo habrá uno. Si reducimos las posibles posiciones en las que podemos colocar el número a una sola... podremos colocar ese número en dicho lugar, ya que no puede ir en ningún otro lugar. Ejemplo Explicativo: Echemos un vistazo a este Sudoku, concretamente a la línea resaltada:

¿Dónde podría ir un 7 en esta línea? Dejemos el resaltado en las celdas que están vacías:

Miremos ahora a otros emplazamientos que puedan eliminar algunas de las casillas verdes. Empezando con el cuadrado de la izquierda, vemos que hay un 7 en el medio, que hace que no podamos poner un 7 en las casillas de esa línea contenidas en ese recuadro (marcadas en amarillo). Vemos estas casillas en naranja para marcar que no son válidas.

Si nos fijamos en el recuadro central, de nuevo encontramos un 7, que evita que lo pongamos en dicho bloque. Eliminamos otra posible casilla para el 7.

En el recuadro de la derecha no hay ningún 7, pero si los hay en los bloques de arriba y de abajo. Dichos 7s evitan que se puedan poner 7s en sus mismas filas y columnas. El 7 de abajo no nos afecta (la única fila a la que podría afectar ya está llena con un 6), pero el 7 de arriba nos evita que coloquemos un 7 en una de las casillas que nos quedaba.

De esta forma, combinando tanto los 7s que ya tenemos en nuestra tabla como los números que teníamos ya en la fila, sólo nos queda un lugar en el que podemos poner el 7 en dicha fila.

TÉCNICA 2: CANDIDATOS ÚNICOS Esta es una técnica muy sencilla, especialmente si utilizamos marcas de lápiz para almacenar los candidatos que aún podemos colocar en cada celda. Si hemos conseguido eliminar las posibilidades para una celda en particular, examinando su columna, su fila y su recuadro, dejando sólo un número como posible, podremos rellenar la celda con dicho número. Aquí va un ejemplo:

Echemos un vistazo a algunas de las líneas que más rellenas están, y después, para las casillas vacías, busquemos áreas que sólo contengan un posible valor. Mirando la tercera columna, los únicos números que no están son el 2 y el 1. Debido a que hay un 1 en el recuadro del medio, el único posible candidato para la celda vacía de dicha columna que está en este recuadro es el 2, de forma que podemos escribir el 2 en esa celda. De hecho, si rellenamos todas las posibles marcas, nos encontraremos con la siguiente tabla, y podremos encontrar fácilmente varios candidatos únicos.

Una vez rellenados estos, iremos encontrando nuevos candidatos, y con esta técnica podremos completar muchos de los sudokus más sencillos.

Marcar las Casillas Muchos de los jugadores de Sudoku en papel tienden a utilizar sus propios sistemas para ayudarse a completar los Sudokus. Muy pocos son los que completan la cuadrícula escribiendo directamente los números finales. La forma más común de marcar las casillas es escribir pequeños números (que normalmente se llaman "marcas de lápiz") que en realidad significan "este número sigue siendo posible para esta casilla". Podemos llegar a la conclusión que una celda sólo puede contener el "5 y el 8" pero no cuál de los dos. Si escribimos un pequeño 58 en la celda, seguramente después encontraremos otro lugar que nos permita eliminar una de las marcas (5 u 8). De esta forma, si elimináramos el 5, sabríamos que esta celda sólo podría contener el 8, de forma que podremos borrar ambas marcas y escribir un 8 más grande. No es necesario rellenar todas las marcas (los buenos jugadores piensan que esto les ralentiza en los puzzles más fáciles, pero lo necesitan hacer en los puzzles más difíciles). Muchas de las siguientes técnicas no proporcionan una posición directa, pero nos pueden ayudar permitiéndonos eliminar alguna de las marcas. La utilización de las marcas hace muy sencillo encontrar los Candidatos Únicos (ver el 3 del bloque de 3x3 de arriba a la derecha). En playSudoku.biz tenemos una herramienta dedicada especialmente a esto, llamada "marcadores" que es muy similar a las marcas de lápiz, con la ventaja de no tener que utilizar la goma de borrar. TÉCNICAS MEDIAS Yendo un poco más lejos, hay algunas técnicas extra que nos pueden ayudar a encontrar emplazamientos válidos o a eliminar algunas de las marcas. Obviamente, éstas son difíciles de utilizar sin las marcas en lápiz. TÉCNICA 3: LÍNEAS DE CANDIDATOS Ésta es la primera técnica que no nos dice realmente dónde poner un número, pero, en lugar de esto, nos ayuda a determinar los lugares en los que no podemos emplazarlo. Si usamos marcas de lápiz, esto nos ayudará a eliminar candidatos y, a partir de esto, podremos colocar algunos números. Si miramos en un recuadro y vemos que todos los lugares en los que podemos colocar un número se encuentran en una sola línea, podremos asegurar que pongamos donde pongamos ese número en dicho recuadro, será en esa línea. Incluso si no sabemos dónde poner dicho número, podremos utilizar dicho conocimiento, ya que sabremos que en ninguna otra posición dentro de dicha línea (y contenida en los otros recuadros) podrá contener ese número, de forma que podemos eliminar dichos candidatos. Aquí hay un ejemplo. Echemos un vistazo al recuadro de abajo a la derecha (recuadro número 9).

Sólo hay dos lugares en los que puede ir el 4, y se encuentran en la misma línea (columna).

Esto significa que los 4 de dicha línea deben estar en este recuadro, y no pueden estar en ningún otro lugar de la línea.

Si miramos el resto de posibles lugares para el 4 en la columna...

El resultado es que podemos eliminarlos y dejar el 2 sólo, de forma que podemos rellenar otro valor.

TÉCNICA 4: PAREJAS DOBLES Esta técnica consiste en encontrar dos parejas de candidatos para un valor y utilizar esta técnica para eliminar candidatos de otros recuadros. Echad un vistazo a los lugares en los que podemos colocar un 2 para la segunda columna de bloques

Aquí los tenemos resaltados:

Podemos ver que se encuentran en dos líneas (columnas 4 y 6).

Debido a que los 2s están limitados a estas posiciones en los bloques de arriba, las columnas 4 y 6 se encuentran "cogidas" para este valor. Esto significa que cualquiera de los candidatos para el 2 en el bloque de abajo se puede eliminar de cualquiera de dichas columnas (se ha forzado el 2 en el bloque de abajo en la columna del medio). Podemos eliminar dichos candidatos.

De nuevo esto nos deja un candidato único, el 7, que podemos rellenar. Esta es una sencilla técnica debido a que sólo necesitamos ver los candidatos en dos bloques. TÉCNICA 5: LÍNEAS MÚLTIPLES Esta técnica es muy similar a la de las Dobles Parejas, pero es un poco más difícil de encontrar. Funciona de la misma manera, pero los candidatos que ocupan las líneas se deben encontrar en dos bloques y podrán haber varios candidatos en cada línea. Echemos un vistazo a estos dos bloques de 3x3 y veamos donde están los candidatos para el 5

Hemos resaltado los lugares para que sea más sencillo de ver, y, como podréis observar, los candidatos se encuentran sólo en las dos primeras columnas.

Esto significa que las columnas 1 y 2 ya están tomadas para candidatos del 5, dejando el recuadro del medio con sólo la columna 3 para sus 5s.

Esto no nos permite colocar ningún valor, pero por lo menos nos permite eliminar candidatos para el 5 de la columna del medio en el recuadro del medio. Seguro que esto nos ayuda posteriormente en la resolución del Sudoku.

Esta técnica es un poco más complicada de utilizar debido a que habrá más de dos parejas, pero seguro que nos ayudará a progresar.

TÉCNICAS AVANZADAS Siguiendo la progresión, podemos encontrar otras técnicas para ayudarnos en la resolución. TÉCNICA 6: PAREJAS O TRIPLETAS DESNUDAS Esta es una de las técnicas más inteligentes. Consiste en marcar grupos de parejas (o tríos, o incluso cuartetos) en un área. El área puede ser una fila, columna o grupo, ya que la técnica es la misma en todos. Observad la última fila del sudoku, que ya se ha ido completando.

Podemos describir el contenido del área en términos de un sólo valor o un grupo de candidatos, con el contenido de cada celda entre corchetes {}. De esta forma, la última fila tendría un aspecto como este: {1369} {15} {4} {369} {8} {7} {15} {16} {2}. No tenemos que preocuparnos por las celdas que ya tienen un valor fijado, de forma que podemos quedarnos sólo con las que tienen varios candidatos:{1369} {15} {369} {15} {16}

En la fila del final, encontramos la pareja {15} en dos lugares. No sabemos en cuál de las dos celdas va el 1 y en cual va el 5, pero podemos asegurar que el 1 y el 5 van seguro en una de esas dos celdas. Esto puede no parecer mucho hasta que nos damos cuenta que si esas celdas contienen el 1 y el 5, ninguna de las otras celdas de esta área (en este caso la fila) puede contenerlos, de forma que podemos eliminar el 1 y el 5 como candidatos de todas las otras celdas del área.

Observad como hemos podido eliminar dos 1s como candidatos de otras celdas, lo cual nos ha dejado el 6 como un único candidato. Así facilitamos la resolución del sudoku. Marcar estas parejas es bastante sencillo, pero la misma técnica se puede aplicar a grupos mayores, tríos y cuartetos. También podemos encontrar esta técnica con la denominación de "Subgrupos Disjuntos" (Disjoint Subsets). Un ejemplo de Tríos Desnudos podría ser: {1578} {4} {569} {569} {25} {1589} {569} {27} {3}. Podemos observar como {569} se da tres veces. Esto significa que los valores 5, 6 y 9 existen sólo en dichas celdas, y no pueden existir en ninguna otra. Después de eliminar los candidatos de las otras celdas, obtenemos: {1578} {4} {569} {569} {25} {1589} {569} {27} {3}. Lo cual acaba como: {178} {4} {569} {569} {2} {189} {569} {27} {3}. Así obtenemos un candidato único, el 2. Yendo un poco más lejos: Un poco más complicado es aplicar esta misma técnica a tríos, lo cual podemos hacer bastantes veces, aunque no sea muy evidente. Observad esta área resaltada:

En realidad hay un trío con el que podemos trabajar, aunque no aparezca completo. Observad los 1s, 3s y 8s. Si lo escribiéramos a parte, nos encontraríamos lo siguiente:{149} {18} {1589} {38} {45} {7} {138} {6} {2}. El truco está en buscar celdas que sólo contengan valores con dichos candidatos (en este caso 1,3 y 8). {149} {18} {1589} {38} {45} {7} {138} {6} {2}. Lo que tenemos son tres celdas entre las cuales deben contener el 1, el 3 y el 8, y ningún otro. Debido a esto, podemos eliminar estos números como candidatos de las otras filas:{149} {18} {1589} {38} {45} {7} {138} {6} {2}. Truco: Muchas veces encontramos en los sudokus tres celdas que contienen dos valores cada una, por ejemplo {24} {47} {27}. De nuevo tenemos tres valores compartidos entre tres celdas, de forma que podemos eliminarlos de cualquier

otra celda del área. ¿Por qué se llaman "Desnudos"? Se llaman así porque contienen el grupo que estamos buscando, y éste no se encuentra escondido entre otros candidatos. En el ejemplo de arriba, el 1, el 3 y el 8 eran los únicos números contenidos en las celdas, y no había ningún otro que los escondiera. ¿Podéis encontrar los tríos en estos sudokus?

¿Y los Cuartetos? Los cuartetos son mucho más difíciles de encontrar, ya que cada celda del cuarteto puede tener 2, 3 o 4 candidatos del cuarteto. Cuesta bastante tiempo encontrarlos a ojo y, en general, los encontrareis en sudokus que hayais "trabajado" mucho. ¿Podéis encontrar un cuarteto de 1, 3, 5 y 7 en este sudoku?

TÉCNICA 7: PAREJAS O TRIPLETAS ESCONDIDAS Afortunadamente tenemos la oportunidad de encontrar Parejas o Tripletas escondidas. Si no, practicad buscándolos antes de intentar encontrar el equivalente escondido. Las parejas o tripletas escondidas son un poco más difíciles de encontrar (después de todo están escondidas). Observemos el área resaltada:

Observad que en realidad hay dos lugares en los que puedan ir el 1 y el 3. Los veriais como dos parejas si una de ellas no estuviera escondida tras un 2 extra. Utilizando la misma notación que antes, si nos fijamos a las celdas que no hemos llenado: {46} {24} {13} {26} {123}. Debido a que el 1 y el 3 sólo pueden existir en dos de esas celdas podemos asegurar que deben ir en ellas, dejando fuera a cualquier otro número. Incluso sin saber en cuál va el 1 y en cuál el 3 podemos asegurar que el 2 no va en ninguna de ellas, de forma que lo podemos eliminar como candidato de la última celda. (Los más avispados habréis notado que podríamos haber llegado al mismo resultado mirando al triple desnudo {46} {24} {26}) Buscando Grupos Ocultos

Recordad que estamos buscando un grupo de números que estén limitados a un reducido grupo de celdas. Si buscamos parejas ocultas, buscamos dos números que sólo existen en dos celdas de un área (incluso si hay otros candidatos en la misma celda escondiéndolos). Para tripletas buscaremos en tres casillas, y así sucesivamente. Marcad la pareja oculta en este sudoku:

Más difícil...Esto se pone más complicado con las tripletas y cuartetos ocultos, ya que, de la misma forma que en las tripletas y cuartetos desnudos, cada celda no tiene por qué tener todo el grupo de números que buscamos. Buscad la tripleta oculta de 3, 4 y 7 en este sudoku:

Deberíamos poder eliminar el 1 como candidato de la celda de arriba, pero hacerlo es un reto! ¿Podéis encontrar las tripletas escondidas en estas líneas?

¿El escurridizo Cuarteto Oculto? Afortunadamente muy pocos Sudokus requieren encontrar un cuarteto oculto para resolverlos, porque son particularmente difíciles de encontrar y endemoniadamente difíciles de solucionar.

Incluso con el resaltado para ayudarnos a saber dónde mirar, nos puede llevar un rato encontrar el cuarteto. TÉCNICAS DE MAESTRO Una vez dominadas las anteriores técnicas, podemos ir un poco más lejos y aplicar técnicas más complicadas. TÉCNICA 8: X-WING Los X-Wings son fáciles de resolver, pero un poco más difíciles de entender que otras técnicas. Al igual que otras, utiliza las posiciones de las marcas para deducir lo suficiente como para permitirte eliminar algunos candidatos. Los X-Wings suceden cuando hay dos líneas, cada una de las cuales tiene las mismas dos posiciones para un número. Fíjate en el siguiente sudoku:

Una vez llegas a la conclusión de que no existen métodos fáciles que puedas aplicar para continuar, fíjate en las posiciones posibles para el 6, en las filas 4 y 9.

El truco para entender X-Wings es imaginar qué pasaría si eligieras una de las posiciones solamente. ¿Qué les haría esto a las otras? Imagina que haces que la celda de arriba a la izquierda contenga el 6. Descartaría el otro candidato de esa fila, y también descartaría el candidato de abajo a la izquierda (las flechas rojas).

Y, por tanto, esto forzaría a poner un 6 en la última celda (la flecha verde)

Así que el 6 arriba a la izquierda, fuerza un 6 abajo a la derecha:

Utilizando la misma lógica, un 6 arriba a la derecha, fuerza un 6 abajo a la izquierda. ¿Te das cuenta de la forma en X que fuerzan estas líneas? De ahí surgió el nombre de la técnica.

El nombre está claro pero, ¿en qué me ayuda la técnica? Si lo piensas, cualquier posición que ocupe el 6 en la fila de arriba, fuerza a ocupar la opuesta en la de abajo. Ahora viene la gracia: a pesar de no saber qué fila tiene el 6 a la izquierda y qué fila lo tiene a la derecha, sabes que seguro las dos estarán ocupadas. Y como sabes que el 6 estará en esas dos columnas, puedes mirar en ambas para eliminar cualquier otro candidato. No podemos quitar ningún 6 de la columna de la izquierda en este caso, pero hay dos en la de la derecha que podemos eliminar, y uno de ellos nos deja con un 8 como candidato único. Lo nuevo de esta técnica es que, el conocimiento de 2 filas parecidas te permite eliminar elementos de columnas. Ni que decir tiene que esto funciona al contrario, si consigues encontrar columnas parecidas. A menudo resolverás X-Wings. Son bastante comunes, pero no siempre te llevan a eliminar candidatos. Consejo: El truco para resolver X-Wings es buscar rectángulos con posibles candidatos. Si encuentras 4 candidatos en las esquinas de un rectángulo, comprueba si pueden ser un X-Wing en fila y columna. Con esto ahorrarás tiempo. Algún ejemplo más

X-Wing en filas para el 8.

X-Wing en filas para el 9.

X-Wing en columnas para el 7.

X-Wing en columnas para el 4. TÉCNICA 9: SWORDFISH Esta técnica es muy parecida a la X-Wings, por lo que te permitirá utilizar tu conocimiento acerca de las filas para eliminar candidatos de las columnas, y viceversa. Asegúrate de que entiendes el funcionamiento de XWings antes de probar con Swordfish. La complejidad en este caso radica en que estás utilizando el conocimiento de 3 filas al mismo tiempo, y eso es lo que las hace difíciles de resolver. Al contrario que en X-

Wings, no forman un rectángulo simple. Este sudoku está casi resuelto, pero hemos llegado a un punto en el que los métodos más simples ya no nos ayudan.

Existe un Swordfish en los 4s de este sudoku, así que explicaremos lo que es y cómo funciona. Para empezar, señalando todas las casillas donde el 4 es candidato ayudará a facilitar las cosas. Lo que buscamos son conjuntos de valores que podamos utilizar para hacer una cadena. Así como en un X-Wing necesitaba una cadena cerrada de cuatro valores, un Swordfish necesita una cadena de 6 (o más) valores.

El Swordfish aquí está en 3 filas (3,5 y 8). Quitaremos los otros valores por ahora para hacerlo un poco más claro.

Igual que en ejemplo de X-Wing, un valor en una posición determinada fuerza al otro que esté en la misma fila a no tener ese mismo valor. Vamos a dibujar unas flechas para que se vea mejor. ¿Te das cuenta de que cada flecha acaba en una columna que coincide con una de las otras filas?

Esto crea una cadena cerrada bastante maja. Esto significa que podemos estar seguros de que cada una de esas columnas está ocupada. Para mostrar los enlaces, aquí están las flechas. En realidad, sólo hay dos posibilidades para las posiciones de los 4s en esta cadena:

De cualquiera de las formas en las que se coloquen estos valores, se puede ver que estas tres columnas están ocupadas con el contenido de esas tres filas.

De nuevo, marcando las columnas, sabes que puedes eliminar candidatos para el 4 de cualquiera de esas columnas que no sean las tres filas Swordfish. Es mucho trabajo para quitar un solo candidato, pero cualquier progreso es bueno cuando ...