Resolver Sudokus en C/C++

Si lo que quieres es el código: CODIGO

El siguiente texto trata sobre el programa “Resolver Sudokus en C” cuyo código se encuentra en esta misma página en este enlace y puesto arriba: CODIGO. El fin de este texto es mostrar cómo se ha trabajado para la elaboración del programa así como la lógica necesaria de implementar en el programa para que éste sea capaz de resolver cualquier Sudoku (Aún no he encontrado ninguno que se pueda resolver por lógica y que el programa no sea capaz).En este texto se muestran los principales trucos para Resolver Sudokus de todos los nivles, ya sean faciles, dificiles o de mayor complejidad.

He de decir que no he sido capaz de encontrar ningún otro código en C/C++ de un programa que resuelva Sudokus por lógica, no por prueba y error. Si lo que quieres es únicamente el código, visita este enlace  CODIGO. Aquí les dejo el comentario al programa:

El siguiente programa nos muestra como un ordenador, con las instrucciones correspondientes, es capaz de llegar a una resolución lógica de una Sudoku (Si es que existe ésta). El programa trabaja únicamente con lógica (Utilizando los trucos para resolver sudokus explicados mas abajos), en ningún momento utiliza la técnica de prueba y error. Al final de la ejecución se muestran las técnicas utilizadas por el programa para llegar a la resolución completa del mismo.

El sudoku se carga mediante un fichero de texto, en el que los huecos que aparezcan en blanco se marcan mediantes un 0. El formato en el que debe de encontrarse el sudoku no es importante, pueden escribirse todos los números seguidos, sin saltos de línea, o con espacios en blanco entre medio… lo importante es que se encuentren en orden, cada uno detrás del que aparece más a su izquierda en el tablero. A mi me gusta introducirlos con algo de formato, que os sirva de ejemplo la imagen del sudoku introducido en un bloc de notas:

A la hora de trabajar la lógica de resolución me he guiado por la información que aparece en la siguiente página: http://www.lalunarosa.com/sudoku/, y que paso a explicar. El programa tiene implementadas en total 6 funciones para la resolución del sudoku, y dentro de cada una de estas funciones puede llegar a utilizar hasta 6 técnicas diferentes que se basan en el mismo principio. Pues bien, aunque disponga de todas estas funciones, el programa solo utilizara las que le sean necesarias y sean las más fáciles. Esto se consigue disponiendo las funciones de manera que para utilizar una función de dificultada mayor haya tenido que probar todas las funciones más sencillas que ella (Que en realidad representan técnicas de mayor sencillez) y no haber conseguido poner ningún número o eliminar ningún candidato. De esta manera las funciones que representan mayor complejidad rara vez son utilizadas por el programa puesto que no le es necesario llegar hasta ellas. Las instrucciones en orden creciente de dificulta son:

CANDIDATOS SOLOS: En primer lugar se crea una función que sea la encargada de eliminar de los posibles candidatos de cada casilla, los números que se encuentren en su misma fila, columna o casilla 3x3, además situar un número en una casilla cuando está solo tenga un posible candidato. Esta función es la que en el programa se llama “CandidatosSolos”.

SOLOS ESCONDIDOS Y CANDIDATOS BLOQUEADOS 1: Muy frecuentemente existe sólo un candidato para una determinada fila, columna o caja 3x3, pero se encuentra escondido entre otros candidatos.

En el ejemplo de abajo, el candidato 6 aparece sólo en la celda de la derecha de la segunda fila de la caja 3x3. Como cada caja 3x3 debe contener un 6, esa celda será ese 6.

                                               
Otras veces pasa que un candidato está restringido a una fila o columna dentro de una caja 3x3. Como alguna de esas celdas debe contener a ese candidato específico, éste podrá ser excluido de las restantes celdas de esa fila o columna fuera de la caja.

En el ejemplo de debajo, la caja 3x3 de la derecha sólo tiene al 2 como candidato en la fila inferior. Por tanto, una de esas celdas será un 2 y ninguna otra celda de esa fila fuera de la caja podrá ser un 2. De esta forma, podemos eliminar al 2 como candidato de las celdas coloreadas en amarillo.

Estas dos técnicas se juntan en una misma función llamada “CandBloq1”.

Candidatos bloqueados 2: A veces un candidato está restringido a una caja 3x3 dentro de una fila o columna. Como alguna de esas celdas debe contener a ese candidato específico, éste podrá ser excluido de las restantes celdas de esa caja 3x3.

En el ejemplo de abajo, la columna de la izquierda sólo tiene al 9 como candidato en la caja 3x3 de en medio. Por tanto, una de esas celdas será un 9 (si no, la columna no tendría ningún 9) y el 9 puede ser eliminado como candidato de todas las celdas de esa caja 3x3, excepto las de la columna de la izquierda.

                                                                     

Esta función está implementada como “CandBloq2”.

Parejas, Tríos, Cuartetos Desnudos:
Si dos celdas en un grupo (fila, columna o caja) contienen un par idéntico de candidatos, y sólo esos dos candidatos, ninguna otra celda de ese grupo podría tener esos valores. El mismo principio que se aplica a las Parejas Desnudas sirve para los Tríos y Cuartetos Desnudos.

Esos dos candidatos pueden ser eliminados de las demás celdas del grupo.

En el ejemplo de debajo, los candidatos 6 y 8 de las columnas sexta y séptima forman una Pareja Desnuda dentro de la fila. Por tanto, dichos candidatos pueden ser eliminados de las restantes celdas de la fila.

                            

Este procedimiento aparece implementado como la función “Desnudas”.

Parejas, Tríos y Cuartetos Escondidos:
Si dos celdas de un grupo (fila, columna o caja 3x3) contienen un par idéntico de candidatos que no aparecen en ninguna otra celda de ese grupo, entonces los demás candidatos de esas dos celdas pueden ser excluidos tranquilamente. Lo mismo ocurre con los Tríos y Cuartetos.

En el ejemplo de abajo, los candidatos 1 y 9 sólo aparecen en las dos celdas amarillas de la caja 3x3, y por tanto forman una pareja. Todos los candidatos excepto el 1 y el 9 pueden ser eliminados de esas dos celdas, pues una debe contener al 1 y otra al 9. 

                                                           

Esto aparece implementado como:  “Escondidas”.

X-Wing: Dado un candidato específico, el esquema X-Wing requiere dos filas que contengan cada una dos celdas (y sólo dos celdas) con ese candidato, y dichas celdas deben compartir las mismas dos columnas formando un rectángulo. Análogamente, dos columnas con dos celdas cada una (y sólo dos celdas) que contengan a ese candidato compartiendo dos filas, también forman un X-Wing. Estas cuatro celdas son las únicas posibles para ese candidato dentro de esas dos filas y columnas. El candidato en cuestión puede ser eliminado de cualquier grupo que contenga dos esquinas de este rectángulo. (Supongo que se le llama X-Wing porque la localización final del candidato es en esquinas opuestas del rectángulo, formando una de sus diagonales.)

Esto se entenderá mejor examinando el ejemplo de debajo. En él se ha aplicado un filtro, de forma que sólo son visibles los candidatos correspondientes al 6. 

                                  
Las celdas verdes y azul celeste forman un X-Wing clásico, ya que las filas primera y novena tienen sólo dos celdas con candidatos al 6, y esas cuatro celdas forman un rectángulo (porque comparten las columnas sexta y novena). Nota: o las dos celdas verdes, o bien las dos azules, contienen a los 'verdaderos' candidatos. Por tanto, los otros candidatos al 6 de las columnas sexta y novena (marcados de amarillo) pueden eliminarse tranquilamente, ya que dichas columnas contienen una celda de esquina verde y otra azul.

Swordfish: El esquema Swordfish (Pez Espada) es una variante del X-Wing anterior.
Dado un candidato determinado, el esquema Swordfish está formado por una de las siguientes situaciones:
  1. tres filas que contienen cada una de ellas no más de tres celdas con ese candidato, y compartiendo todas ellas no más de tres columnas, o
  2. tres columnas que contienen cada una no más de tres celdas con el candidato y compartiendo todas las mismas tres filas.
Estas celdas forman una cuadrícula de nueve celdas que son los únicos lugares posibles para el candidato en esas 3 filas y columnas. Cualquier candidato en un grupo que contenga tres celdas de la cuadrícula (excepto las de la cuadrícula mismas) puede ser eliminado.
En el ejemplo de debajo se ha aplicado un filtro para que sólo queden visibles los candidatos del 5.
Tres columnas (segunda, quinta y octava) tienen candidatos al 5 en no más de tres celdas (en dos concretamente, en este caso), y todas esas celdas, marcadas en azul, comparten no más de tres filas (la primera, cuarta y novena). Tenemos un esquema "Swordfish". En el resto de celdas con candidato 5 en esta cuadrícula (marcadas en amarillo) puede ser eliminado el candidato. Recuerda: como se ve en este ejemplo, no es necesario que haya 3 celdas en cada fila (o columna); a menudo hay sólo dos.

 

                                            

Esta son entonces todas las funciones disponibles para que el programa resuelva el sudoku. En total todo el programa viene a ocupar unas 1100 líneas de código, y el sudoku es resuelto de manera instantánea. Si quereis mas información acerca de la lógica visitad http://www.lalunarosa.com/sudoku/ que es de donde yo he obtenido la información. 

Aqui les dejo una ejecucion del programa:

Una vez que tenemos implementadas todas estas funciones, podríamos crear un programa que en vez de resolver el sudoku, ayudará dando información a cerca de paso próximo a realizar.
 

Un Saludo.