SudokuSolver, la leyenda

Corría octubre del 2005. Los juegos para GameCube comenzaban a escasear y la Xbox empezaba su debacle frente a la 360. La “Guerra de los mundos” de Spielberg intentaba asustarnos sin conseguirlo. Las tías seguían tan frías como de costumbre (bueno más, porque se acercaba el invierno). La fiebre del sudoku barría el vivero de empresas de Portugalete y por supuesto, como coder de pura cepa, decidí que pasaba de resolver un sudoku a mano así que arranqué el VisualStudio…

Sudoku 4ever!La verdad es que el programa es muy sencillo, y tras un modelo básico para las celdas del sudoku resultó bastante más sencillo todavía. La clave estaba en dotar de “inteligencia” a estas celdas, y para ello se encapsuló dentro de la misma el array de valores posibles y la lógica de descarte y búsqueda de valores, todo ello mediante referencias a los grupos de celdas únicos del sudoku: fila, columna y bloque.

Los grupos de celdas son iguales entre sí, y lo único que los diferencia son las celdas que contienen, así que lo importante es reaprovechar la clase para reaprovechar el código, y por ello se creó “CellGroup”, clase de la que derivan estos tres grupos de celdas.

Finalmente, todo el sudoku se encuentra dentro de la clase “Sudoku” que contiene todas las celdas y grupos de celdas del mismo, así como una pila de estados para los valores para el algoritmo recursivo del que hablaremos más tarde. Dentro de esta clase tenemos el método “SolveStep()” que aplica los tres métodos de solución uno detrás de otro: intenta resolver con el primero, y cuando no es posible, aplica el siguiente método. Si halla una solución, vuelve de nuevo al primero, y si no pasa al tercero; de la misma forma, del tercero pasamos de nuevo al primero y vamos subiendo de nuevo.

 Los métodos de resolución son los siguientes:

  1. Resolver valores únicos: búsqueda de valores posibles para una celda, y si el valor posible sólo es uno, pues ya está.
  2. Resolver por frecuencia de aparición: ahora, dentro de un grupo de valores, para las celdas vacías analizamos las veces que se repiten los valores posibles para todas esas celdas y si hay algún valor que sólo se repite una vez, es decir, sólo es posible en esa celda de las libres, ya tenemos otro.
  3. Resolver por adivinación (o potra): si no funciona ninguno de los métodos anteriores lo que hacemos es coger el primer valor posible para la celda, y partiendo de esa hipótesis intentamos solucionar el sudoku utilizando de nuevo estos métodos en el orden descrito. Si llegamos a una incoherencia descartamos ese valor y probamos el siguiente, así hasta que dejen de producirse incoherencias. Llegados a ese punto el sudoku ya está resuelto.

Os subiré el código en cuanto pueda porque parece que estos de WordPress se han puesto farrucos y no me dejan subir zips. De todas formas, podéis enviarme un correo (los que lo tengáis y si no, a través de los comentarios) y os paso el código de mientras.

Anuncios

2 comentarios en “SudokuSolver, la leyenda

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s