SUDOKU

SUDOKU

INTRODUCCIÓN
Sudoku es un rompecabezas matemático que se popularizó en Japón en 1986 y se dio a conocer
en el ámbito internacional en 2005. Es un pasatiempo que consiste en un tablero de 9 filas x 9
columnas que componen 81 casillas. El tablero está dividido en subcuadrículas de 3x3 casillas. El
objetivo del juego es rellenar todas las casillas libres de dicho tablero con los números del1 al 9
considerando que inicialmente existen algunos números ya colocados en algunas casillas. En el
tablero solución se debe cumplir la restricción de que no se repite ningún número en una misma
fila, columna o subcuadrícula. La solución es única.

EJEMPLO DE POSIBLE CONFIGURACIÓN
INICIAL DE TABLERO JUNTO CON SU
SOLUCIÓN.

ALGORITMO GENÉTICO PARA RESOLVER
EL SUDOKU
El Sudoku puede considerarseun problema de optimización con restricciones, a nivel de fila,
columna y subcuadrícula. Partiendo de esta base, podemos presuponer una buena idea utilizar un
algoritmo evolutivo para resolverlo, dados los buenos resultados obtenidos en este tipo de
problemas.
A continuación se analiza la representación utilizada para las posibles soluciones, la función de
aptitud y los operadores genéticosapropiados al problema.

QUE ES ALGORITMOS GENÉTICOS ?
El algoritmo genético clásico utiliza una población de individuos, que representan posibles
soluciones candidatas a un problema. Esta población se somete a un proceso de
selección que normalmente favorece a los mejores según su aptitud y después los
somete a una serie de transformaciones.
Cada generación consiste en un ciclo de transformación yselección. Se espera que
después de número de generaciones el mejor individuo de la población esté cerca de la
solución buscada

El algoritmo genético simple (goldberg, 1989), aplicado al la resolución del sudoku, incorpora los siguientes
aspectos:

• Criterio de codificación: es específico de cada problema y en el caso del sudoku utilizaremos representación
con permutaciones de valores enteros.
•Criterio de inicialización: la población inicial está formada por secuencias de enteros que representan los
valores de cada celda vacía del tablero.
• Funciones de evaluación y aptitud: la función de aptitud coincide con la de evaluación. La función de
evaluación viene dada a través de una función objetivo explicada posteriormente.
• Operadores genéticos: operadores de cruce y mutación explicadosposteriormente.
• Criterio de selección y de reemplazo.
• Criterio de terminación y parámetros de funcionamiento.

Si el algoritmo utiliza elitismo, se garantiza que los mejores individuos no desaparecen con la evolución.
Para ello se muestrea una élite de r miembros de entre los mejores de la población. Durante el
reemplazo los individuos de la élite se preservan, descartando si es necesario aalguno de sus hijos
(siempre que sea peor). Está comprobado que si el algoritmo utiliza elitismo, es posible alcanzar el
óptimo.
A continuación se muestra el seudocódigo de un algoritmo genético simple con elitismo:

REPRESENTACIÓN DEL INDIVIDUO
El Sudoku es un claro ejemplo de representación basado
en otros problemas de optimización combinatoria (Lawler,
1985).
Cada individuo (tablero) secodifica en un array de 81
posiciones; este array representa el cromosoma que está
formado por 9 genes (filas). De esta forma, supongamos
que tenemos el siguiente tablero:

En nuestra representación, cada individuo o
cromosoma se representa por un array compuesto por
9 genes de 9 elementos cada uno. Cada gen se
corresponde con una fila del tablero.

FUNCIÓN DE APTITUD
La función de aptitud se basa enque los elementos de cada fila y columna deben
ser los valores del conjunto digitos = {1,2,3,4,5,6,7,8,9}. La función calcula el
número de elementos que faltan en cada submatriz y columna. A nivel de fila no
existe penalización pues los elementos son permutaciones.
APTITUD = TOTAL DE FALTAS DE CADA SUBCUADRÍCULA + TOTAL DE
FALTAS DE LAS COLUMNAS
Se trata de un problema de minimización y el...