Resolver un Sudoku como un problema de optimización

Resolver cualquier Sudoku es un problema que puede parecer complicado si se utilizan métodos de fuerza bruta, probando todas y cada una de las combinaciones posibles. Pero, con el planteamiento adecuado, puede resolverse cualquiera de estos problemas en unos pocos milisegundos. En este artículo voy a mostrar una forma de conseguirlo mediante un correcto planteamiento.

En este enlace puedes descargar el código fuente del programa para resolver sudokus, escrito en csharp con Visual Studio 2015.

Para introducir los datos en el programa de manera sencilla, habrá que crear un archivo de texto con los datos de las casillas separados por comas, una fila en cada línea del archivo, con un cero para las casillas vacías y el número correspondiente para las casillas fijas, sin añadir espacios adicionales.

El programa es un simple cuadro de diálogo con un botón New que nos permitirá seleccionar el archivo deseado y presentará a continuación el sudoku solucionado, con los números fijos en rojo y el resto en color negro:

Vamos a ver como plantear este problema de manera que podamos reducir el número de operaciones a realizar y optimicemos el proceso para encontrar la solución en el menor tiempo posible.

Como todo el mundo sabe, un sudoku es un tablero de 9x9 casillas en las cuales se deben colocar los números del 1 al 9, de manera que en cada fila y columna se encuentren todos ellos sin repetición. El tablero está dividido en 9 sectores de 3x3 casillas que también deben contener todos estos números. Como pista inicial, se proporcionan unas cuantas casillas fijas con parte de la solución final.

El algoritmo más sencillo para resolver este problema es la pura fuerza bruta. Probar todos los valores posibles en cada una de las casillas hasta dar con una solución, pero ese sistema puede tardar varios minutos, ya que el número de posibilidades es altísimo, así que vamos a hacer algo de trabajo para encontrar un planteamiento más inteligente que reduzca todas esas posibilidades al mínimo.

La primera optimación será de tipo genérico. Los tipos de datos simples, como int o bool, además de los tipos struct, son candidatos a almacenarse en la memoria caché del procesador, a diferencia de las clases, que son objetos que se almacenan como referencias en la memoria RAM normal, cuyo tiempo de acceso es mucho más lento. Así que todos los datos que vamos a utilizar estarán definidos teniendo esto en cuenta.

Los números naturales en notación decimal tampoco son apropiados, ya que necesitamos hasta tres bits para representar los valores del 1 al 9. Pero podemos representarlos utilizando un solo bit en una posición diferente para cada uno de ellos, transformándolos con la operación N = 2^n-1, para poder trabajar con ellos más fácilmente utilizando operaciones lógicas como and y or. Como tenemos nueve números, utilizaremos nueve bits diferentes para representarlos:

1 = 000000001
2 = 000000010
3 = 000000100
4 = 000001000
…
9 = 100000000

Para representar cada casilla del tablero, utilizaremos un objeto struct que contendrá una combinación de estos bits para indicar los valores posibles, de manera que no tengamos que recorrer todas las casillas de la fila, la columna y el sector para saber que valores podemos situar en la misma:

private struct sCell
{
public int Value;
public int Row;
public int Col;
public int Sec;
public bool Fixed;
}

El miembro Value contendrá el valor actual de la celda o cero si está vacía. Row contendrá la combinación de bits de todos los números presentes en la fila, Col en la columna y Sec en el sector, mientras que Fixed indicará si se trata de un valor fijo. Para representar el tablero crearemos el array _sudoku de 9x9 elementos de este tipo. Con SetCell fijaremos el valor de una casilla y rellenaremos los datos de todas las casillas de la fila, columna y sector para indicar los valores que ya se encuentran presentes y, por lo tanto, no podemos volver a repetir:

private void SetCell(int row, int col, int v, bool fix)
{
_sudoku[row, col].Value = v;
_sudoku[row, col].Fixed = fix;
for (int c = 0; c < 9; c++)
{
_sudoku[row, c].Row |= v;
_sudoku[c, col].Col |= v;
_sudoku[(3 * (row / 3)) + (c % 3), (3 * (col / 3)) + (c / 3)].Sec |= v;
}
}

Esta función la utilizaremos para inicializar el tablero con los valores fijos que leeremos desde el fichero de datos. Una vez hecho esto, para saber si un determinado valor v puede ir en una determinada casilla, solo tenemos que comprobar la siguiente operación lógica:

(_sudoku[row, col].Row |
_sudoku[row, col].Col |
_sudoku[row, col].Sec) & v) == 0

Pero comprobar casilla por casilla del tablero no es la mejor manera de resolver rápidamente el problema, así que vamos a construir otro array de trabajo a partir de este que contendrá todas las posibles combinaciones de todos los números. Se trata del array _matrix, de 9x9x9 elementos. Las dos primeras dimensiones son para las filas y las columnas, la tercera es para cada uno de los nueve valores que pueden tomar las celdas del tablero. Esta es la estructura de los datos que contiene:

private struct sNum
{
public int Value;
public int Col;
public int ColMask;
public int SecMask;
}

Aquí Value contiene un número binario que utiliza 9 bits para indicar la posición de la casilla dentro de la correspondiente fila del tablero. La casilla tercera se indica, por ejemplo, con el valor 001000000. En lugar de almacenar los datos en la columna correspondiente del tablero para cada fila, lo vamos a hacer de manera continua desde la primera posición. Así, si en la primera fila puede haber tres posiciones que contengan, por ejemplo, un valor 1, digamos que en las casillas segunda, cuarta y octava, usaremos las tres primeras posiciones para indicar esto, y en el miembro Col indicaremos la columna real en la que se encuentran los datos. De esta manera, no hace falta procesar todas las casillas de cada fila, sino solo las primeras hasta encontrar una cuyo Value sea cero.

Los miembros ColMask y SecMask contienen datos auxiliares para comprobar si ya se ha puesto el valor dado en la columna y en el sector. Por ejemplo, para la segunda casilla de la primera fila, ColMask contendrá 101111111 y SecMask 000111111. Estos valores los utilizaremos para determinar si podemos colocar un determinado número en una casilla del tablero.

Con BuildMatrix construiremos este array a partir de los datos contenidos en el array _sudoku:

private void BuildMatrix()
{
int v = 1;
for (int n = 0; n < 9; n++)
{
for (int row = 0; row < 9; row++)
{
int c = 0;
int msec = 0x3F;
int mcol = 0x7EFF;
int bit = 0x100;
for (int col = 0; col < 9; col++)
{
if (_sudoku[row, col].Fixed)
{
if (_sudoku[row, col].Value == v)
{
_matrix[row, c, n].Value = bit;
_matrix[row, c, n].Col = col;
_matrix[row, c, n].ColMask = mcol & 0x1FF;
_matrix[row, c++, n].SecMask = msec;
}
}
else if (((_sudoku[row, col].Row |
_sudoku[row, col].Col |
_sudoku[row, col].Sec) & v) == 0)
{
_matrix[row, c, n].Value = bit;
_matrix[row, c, n].Col = col;
_matrix[row, c, n].ColMask = mcol & 0x1FF;
_matrix[row, c++, n].SecMask = msec;
}
bit >>= 1;
mcol >>= 1;
mcol |= 0x4000;
if (col == 2)
{
msec = 0x1C7;
}
else if (col == 5)
{
msec = 0x1F8;
}
}
}
v <<= 1;
}
}

Ahora ya tenemos todos los datos necesarios para empezar a resolver el sudoku. Utilizaremos un tercer array de enteros, _numbers, para marcar los bits de las casillas en las que ya hemos colocado un número, de manera que no intentemos colocar otro diferente en las casillas marcadas.

El procedimiento es muy simple, empezaremos colocando en cada fila un solo valor 1 hasta que tengamos todas las filas completas, entonces pasaremos a colocar los valores 2, también uno en cada fila, y así hasta el 9. Probaremos todas las combinaciones que sea posible colocar hasta encontrar que tenemos el tablero completo. Si encontramos que no podemos completar un nivel para uno de los números, volveremos al nivel anterior para probar una nueva combinación.

La ventaja de este sistema es que cada nivel limita las posibles combinaciones que pueden darse en el nivel siguiente, ya que no podemos colocar un número en una casilla ocupada. Cuando en la primera fila hayamos puesto el valor en la posición correcta, ya no volveremos a procesarla más. Lo mismo sucederá con la segunda, la tercera, etc. Tampoco volveremos a procesar un nivel una vez que hayamos puesto todos los valores en la posición correcta, de manera que, con cada número, cada vez tendremos menos combinaciones posibles que comprobar. De esto se encarga el método ProcessNextNumber, al que le pasamos como parámetro el número, o nivel, a procesar, empezando con el 0 que corresponde al valor 1.

Lo primero que hacemos es un trabajo de inicialización de variables para el nivel actual:

int[] indexes = new int[9];
int[] oldnumbers = new int[9];
for (int num = 0; num < 9; num++)
{
oldnumbers[num] = _numbers[num];
}
int mcol = 0x1FF;
int msec = 0x1FF;
int ix = 0;
int v = 1 << n;

Usamos indexes para indicar, para cada fila, el índice del array _matrix que estamos utilizando para probar la combinación de valores actual. oldnumbers contiene los valores iniciales, para cada fila, del array _numbers, de manera que podamos recuperar estos valores para probar una nueva combinación. mcol es una máscara de bits para saber qué columnas hemos rellenado ya, y msec es igual para los sectores. ix contiene el índice de la fila que estamos procesando, y v el valor del número correspondiente al nivel en el formato 2^n-1.

El bucle de trabajo tiene dos partes, dependiendo de si podemos colocar un nuevo valor en la fila actual o no. Si podemos colocar un nuevo valor, se ejecuta el siguiente código:

if ((index < 9) &&
((_matrix[ix, index, n].Value & msec & mcol & ~_numbers[ix]) != 0))
{
_numbers[ix] |= _matrix[ix, index, n].Value;
_sudoku[ix, _matrix[ix, index, n].Col].Value = v;
mcol &= _matrix[ix, index, n].ColMask;
if ((ix == 2) || (ix == 5))
{
msec = 0x1FF;
}
else
{
msec &= _matrix[ix, index, n].SecMask;
}
ix++;
if (ix == 9)
{
if (n == 8)
{
return true;
}
if (ProcessNextNumber(n + 1))
{
return true;
}
ix = 8;
_numbers[8] = oldnumbers[8];
mcol |= (~_matrix[8, indexes[8], n].ColMask) & 0x1FF;
msec = _matrix[7, indexes[7], n].SecMask &
_matrix[6, indexes[6], n].SecMask;
indexes[8]++;
}
}

Empezamos marcando, en el array _numbers, la posición que hemos colocado. También colocamos el número en el tablero _sudoku. Eliminamos el bit correspondiente a la columna en la máscara mcol, y hacemos lo mismo con la máscara de sector msec, teniendo en cuenta que hay que volver a inicializarla cada vez que pasamos a un nuevo sector de filas. Incrementamos el índice de fila y, si hemos llegado a la última, comprobamos si estamos colocando el número 9, en cuyo caso hemos terminado el sudoku, o bien procesamos el siguiente nivel.

En el caso de que no sea posible procesar el siguiente nivel, la combinación de valores del nivel actual es incorrecta, así que probamos a cambiar de columna el dato de la fila 9. Reseteamos los valores y las máscaras y tratamos de probar con el siguiente.

En el caso de que no sea posible colocar un número en la fila actual, se ejecuta el siguiente código:

if ((index < 9) && (_matrix[ix, index, n].Value != 0))
{
indexes[ix]++;
}
else
{
if (ix == 0)
{
return false;
}
indexes[ix] = 0;
ix--;
_numbers[ix] = oldnumbers[ix];
mcol |= (~_matrix[ix, indexes[ix], n].ColMask) & 0x1FF;
switch (ix % 3)
{
case 0:
msec = 0x1FF;
break;
case 1:
msec = _matrix[ix - 1, indexes[ix - 1], n].SecMask;
break;
default:
msec = _matrix[ix - 1, indexes[ix - 1], n].SecMask &
_matrix[ix - 2, indexes[ix - 2], n].SecMask;
break;
}
indexes[ix]++;
}

Si todavía no hemos probado todas las posiciones de la fila, pasamos a la siguiente. En otro caso, comprobamos si estamos en la fila 1, lo que quiere decir que la combinación es imposible, y devolvemos el control al nivel anterior. En otro caso, volvemos a la fila anterior y probamos con la siguiente casilla, reseteando el valor de las posiciones de la fila y las máscaras de columna y de sector.

Con este sistema, podemos resolver cualquier sudoku válido en unos pocos milisegundos. El tiempo que tarda el algoritmo no depende de la dificultad del sudoku, sino del tiempo que tardemos en ir dando con las combinaciones correctas para cada nivel de números, de manera que es posible que resolvamos antes un sudoku de dificultad extrema que uno fácil. Para las personas, claro.