Tu primer programa de Inteligencia Artificial: resolver un Sudoku

POST: http://jorditorres.org/tu-primer-programa-de-inteligencia-artificial-resolver-un-sudoku/

Hace unos días el periodista Albert Molins publicaba en La Vanguardia un excelente artículo titulado “Una máquina gana al póquer a los mejores jugadores del mundo” para el que me llamo para contrastar algunos datos sobre este sistema de inteligencia artificial, Libratus, desarrollado por la Universidad Carnegie Mellon. En el mismo artículo Albert se hacia eco de anteriores duelos entre sistemas de inteligencia artificial y humanos en diferentes juegos como el Ajedrez (en 1997 el ordenador Deeper Blue derrotó a Kaspárov), concurso de preguntas y respuestas de la televisión estadounidense (en 2011 el ordenador Watson ganó a Brad Ruttler y Ken Jennings, los dos mejores concursantes del concurso Jeopardy) o el Go (en el 2016 el sistema AlphaGo desarrollado por la empresa DeepMind de Google ganó a Lee Se-dol, campeón mundial de Go).

A raíz de este artículo algunos me han preguntado si podría explicar un poco más a nivel técnico como funcionan por dentro estos sistemas supuestamente inteligentes. Aunque ciertamente son sistemas complejos, que requieren además mucha computación y no están al alcance de cualquiera, no es menos cierto que son algoritmos que un ingeniero informático sin ninguna duda puede entender, y me atrevería a decir, programar.

Por ello, he decidido escribir este post para explicar como es el código de un programa que usa algunas de las técnicas de inteligencia artificial para resolver un juego como puede ser un Sudoku. El sistema que permite la resolución automática de este juego utiliza algunas técnicas de las que usan los sistemas que resuelven los anteriores juegos mencionados, aunque son sistemas mucho más sofisticados que ya intentaré explicar algún día.

Todos sabemos hacer un Sudoku y sus reglas básicas, pero las recuerdo rápidamente pensando ya en el algoritmo que presentaré:

Un Sudoku es básicamente una cuadrícula de 9x9 casillas dividida en 9 cuadrados de 3x3 casillas.
Los valores que puede contener una casilla son 1, 2, 3, 4, 5, 6, 7, 8 o 9.
Si una casilla contiene un determinado valor, entonces ninguna de las casillas en la misma columna, fila o cuadrado de 3x3 al que pertenece dicha casilla puede contener ese mismo valor.
Si solo hay un valor permitido para una determinada casilla dada su columna, fila o cuadrado al que pertenece, entonces ese valor se asignará a dicha casilla.

Con la programación de estas simples reglas, este algoritmo "inteligente" que les propongo, siempre (insisto, siempre) va a resolver cualquier Sudoku más rápido que cualquiera de sus amigos o amigas, suponiendo que ellos o ellas puedan resolverlo. Llévenlo encima en el móvil :-).

Para presentar el tema sigo el modelo "learn by doing" que presupone que el lector va programando en Python (que uso en mis cursos) y experimentando a medida que van avanzando en el post, tal como lo hacemos en los hands-on de los laboratorios de mis clases en la UPC. En realidad les propongo que usen el entorno Anaconda disponible en cualquier sistema operativo actual y que pueden contar con una explicación detallada en uno de los hands-on de nuestra asignatura en la UPC).

Notación y nomenclatura
Eliminación de opciones en una casilla
Casillas con una sola opción
Propagación de restricciones
Estategia Search
Y para acabar
Agradecimientos

1. Notación y nomenclatura

Antes de empezar a programar debemos acordar una cierta notación. Les propongo la siguiente.

En nuestro código las filas las etiquetaremos con las letras A, B, C, D, E, F, G, H, I. Y las columnas con los números 1, 2, 3, 4, 5, 6, 7, 8, 9. Es decir, las posiciones de nuestro tablero quedarán etiquetadas como:

A1 A2 A3| A4 A5 A6| A7 A8 A9     
B1 B2 B3| B4 B5 B6| B7 B8 B9    
C1 C2 C3| C4 C5 C6| C7 C8 C9    
--------+---------+---------    
D1 D2 D3| D4 D5 D6| D7 D8 D9    
E1 E2 E3| E4 E5 E6| E7 E8 E9    
F1 F2 F3| F4 F5 F6| F7 F8 F9    
--------+---------+---------    
G1 G2 G3| G4 G5 G6| G7 G8 G9    
H1 H2 H3| H4 H5 H6| H7 H8 H9   
I1 I2 I3| I4 I5 I6| I7 I8 I9

En el código vamos a usar la siguiente nomenclatura:

A las casillas las llamaremos boxes.
A las columnas, filas o cuadrados 3x3 los llamaremos units. Por tanto, cada elemento de units contiene 9 boxes, siendo 27 el número total de units.
Para una casilla (box) en particular, sus pares (que llamaremos peers) serán todas las otras casillas (boxes) que pertenecen a una misma unit, es decir, serán todas las otras box que pertenecen a cualquier unit común (misma columna, fila o cuadrado 3x3). Por tanto para cada casilla, hay 20 pares. Por ejemplo los pares de A1 son las casillas de la columna A2, A3, A4, A5, A6, A7, A8, A9, junto con las casillas de la columna B1, C1, D1, E1, F1, G1, H1, I1 y junto con las casillas del cuadrado 3x3 formado por B2, B3, C2, C3 (teniendo en cuenta que A1, A2, A3, B1, C1 ya están contabilizados).

Para facilitar la resolución del problema, vamos a almacenar nuestro tablero o cuadrícula en dos formatos: como string y como dictionary.

El formato string consiste en la concatenación de todos los dígitos de todas las casillas de las filas desde arriba hacia abajo. Si el Sudoku aún no está solucionado podemos usar '.' para indicar que la casilla aún no tiene valor asignado. Por ejemplo el tablero:

. . 3 |. 2 . |6 . . 
9 . . |3 . 5 |. . 1 
. . 1 |8 . 6 |4 . . 
------+------+------
. . 8 |1 . 2 |9 . . 
7 . . |. . . |. . 8 
. . 6 |7 . 8 |2 . . 
------+------+------
. . 2 |6 . 9 |5 . . 
8 . . |2 . 3 |. . 9 
. . 5 |. 1 . |3 . .

lo almacenaremos con el string:

'..3.2.6..9..3.5..1..18.64....81.29..7.......8..67.82....26.95..8..2.3..9..5.1.3..'

Por otra parte implementaremos el diccionario de tal manera que las keys serán los strings correspondientes a las casillas ('A1', 'A2', ..., 'I9') y los valores seran o bien el dígito en la casilla o '.'.

Para generar nuestra estructura de datos que contendrá el tablero cuadriculado vamos a empezar programando una función de soporte que llamaremos cross(a, b) que dados dos strings a y b la función retorna la lista (recordemos que una lista se especifica con [ ]) formada por todas las posibles concatenaciones de letras s en el string a con la t en el string b.

def cross(a, b):
      return [s+t for s in a for t in b]

Por ejemplo cross('abc', 'def') retornará la lista ['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']. Ahora, para crear todas las etiquetas de las casillas que almacenaremos en boxes podemos hacerlo de la siguiente manera:

rows = 'ABCDEFGHI'
cols = '123456789'

boxes = cross(rows, cols)

Podemos comprobarlo con print boxes o print (boxes) (dependiendo si usamos Python 2.x o 3.x) que nos dará la siguiente salida:

[['A1', 'A2', 'A3', 'A4', 'A5', 'A6', 'A7', 'A8', 'A9'], ['B1', 'B2', 'B3', 'B4', 'B5', 'B6', 'B7', 'B8', 'B9'], ['C1', 'C2', 'C3', 'C4', 'C5', 'C6', 'C7', 'C8', 'C9'], ['D1', 'D2', 'D3', 'D4', 'D5', 'D6', 'D7', 'D8', 'D9'], ['E1', 'E2', 'E3', 'E4', 'E5', 'E6', 'E7', 'E8', 'E9'], ['F1', 'F2', 'F3', 'F4', 'F5', 'F6', 'F7', 'F8', 'F9'], ['G1', 'G2', 'G3', 'G4', 'G5', 'G6', 'G7', 'G8', 'G9'], ['H1', 'H2', 'H3', 'H4', 'H5', 'H6', 'H7', 'H8', 'H9'], ['I1', 'I2', 'I3', 'I4', 'I5', 'I6', 'I7', 'I8', 'I9']]

En este punto tenemos en formato string el contenido de nuestro tablero y vamos a pasarlo a formato diccionario de Python usando la notación que hemos decidido anteriormente. Es decir, el string '..3.2.6..9..3.5..1..18.64....81.29..7.......8..67.82....26.95..8..2.3..9..5.1.3..' lo queremos tener como:

{
  'A1': '.'
  'A2': '.',
  'A3': '3',
  'A4': '.',
  'A5': '2',
  
  ...
  
  'I9': '.'
}

Para ello implementamos una nueva función que llamaremos grid_values() basada en la librería de Python [zip] (https://docs.python.org/3.3/library/functions.html) que nos facilitará esta tarea de repartir este string de entrada que contiene los valores de las casillas (boxes):

def grid_values_original(grid):
    return dict(zip(boxes, grid))

Recordemos que el string de entrada a la función que representa el tablero de nuestro sudoku debe ser de 81 caracteres (9x9) compuesto de dígitos 1, 2, 3, 4, 5, 6, 7, 8, 9, o bien de . si aún no lo sabemos. Veamos un ejemplo, pero previamente nos dotamos de una función para visualizar más fácilmente nuestro tablero de sudoku:

def display(values):
    """
    Visualiza nuestro tablero de sudoku
    """
    width = 1+max(len(values[s]) for s in boxes)
    line = '+'.join(['-'*(width*3)]*3)
    for r in rows:
        print(''.join(values[r+c].center(width)+('|' if c in '36' else '')
                      for c in cols))
        if r in 'CF': print(line)
    return

Con esta función podemos visualizar el tablero en el formato que estamos acostumbrados. Aplicando esta función a nuestro ejemplo anterior:

example='483.2.6..9..3.5..1..18.64....81.29..7.......8..67.82....26.95..8..2.3..9..5.1.382'
display(grid_values_original(example))

el resultado de display será:

. . 3 |. 2 . |6 . . 
9 . . |3 . 5 |. . 1 
. . 1 |8 . 6 |4 . . 
------+------+------
. . 8 |1 . 2 |9 . . 
7 . . |. . . |. . 8 
. . 6 |7 . 8 |2 . . 
------+------+------
. . 2 |6 . 9 |5 . . 
8 . . |2 . 3 |. . 9 
. . 5 |. 1 . |3 . .

2. Eliminación de opciones en una casilla

Descripción

Como primer paso en nuestra estrategia usaremos lo que llamamos eliminación que trata de eliminar posibilidades de los pares.

Empezaremos mirando una casilla y analizando que valores pueden ir allí. Por ejemplo en la posición E6, marcado con una X en el siguiente tablero:

. . 3 |. 2 . |6 . . 
9 . . |3 . 5 |. . 1 
. . 1 |8 . 6 |4 . . 
------+------+------
. . 8 |1 . 2 |9 . . 
7 . . |. . X |. . 8 
. . 6 |7 . 8 |2 . . 
------+------+------
. . 2 |6 . 9 |5 . . 
8 . . |2 . 3 |. . 9 
. . 5 |. 1 . |3 . .

vemos que de entre todos los valores 1, 2, 3, 4, 5, 6, 7, 8, 9 no todos son posibles puesto que ya aparecen o bien en la misma columna, o en la misma fila o en el cuadrado 3x3 correspondiente a la posición E6. En concreto, 1, 7, 2 y 8 ya se encuentran en el mismo cuadrado 3x3. Los valores 3, 5, 6 y 9 se encuentran en la misma columna. Y los valores 7 y 8 se encuentran en la misma fila, aunque ya los habíamos descartado por encontrarse en el mismo cuadrado. Por tanto, en este caso, solo tenemos el 4 que cumple los requisitos.

Ahora que ya conocemos como eliminar valores, podemos hacerlo para todas las casillas que no tienen valor y eliminar los valores que no pueden aparecer en la casilla al estar ya presentes en su misma columna, fila o cuadrado 3x3.

función `grid_values()`

Para ello, de momento vamos a reprogramar la función grid_values() para que nos devuelva '123456789' en vez del '.'para las casillas vacías, puesto que los valores iniciales para estas casillas puede ser cualquier valor.

def grid_values(grid):
    values = []
    for c in grid:
        if c == '.':
            values.append('123456789')
        elif c in '123456789':
            values.append(c)
    return dict(zip(boxes, values))

Ahora esta función convierte el string que recibe de entrada (con 9x9 carácteres) en un diccionario {<box>: <value>} que contiene para cada clave (que indica la posición dentro del tablero) su valor correspondiente o '123456789' si está vacío.

example='483.2.6..9..3.5..1..18.64....81.29..7.......8..67.82....26.95..8..2.3..9..5.1.382'
display(grid_values_original(example))
display(grid_values(example))

4 8 3 |. 2 . |6 . . 
9 . . |3 . 5 |. . 1 
. . 1 |8 . 6 |4 . . 
------+------+------
. . 8 |1 . 2 |9 . . 
7 . . |. . . |. . 8 
. . 6 |7 . 8 |2 . . 
------+------+------
. . 2 |6 . 9 |5 . . 
8 . . |2 . 3 |. . 9 
. . 5 |. 1 . |3 8 2 
    4         8         3     |123456789     2     123456789 |    6     123456789 123456789 
    9     123456789 123456789 |    3     123456789     5     |123456789 123456789     1     
123456789 123456789     1     |    8     123456789     6     |    4     123456789 123456789 
------------------------------+------------------------------+------------------------------
123456789 123456789     8     |    1     123456789     2     |    9     123456789 123456789 
    7     123456789 123456789 |123456789 123456789 123456789 |123456789 123456789     8     
123456789 123456789     6     |    7     123456789     8     |    2     123456789 123456789 
------------------------------+------------------------------+------------------------------
123456789 123456789     2     |    6     123456789     9     |    5     123456789 123456789 
    8     123456789 123456789 |    2     123456789     3     |123456789 123456789     9     
123456789 123456789     5     |123456789     1     123456789 |    3         8         2

función `eliminate()`

El siguiente paso consiste en reducir los valores posibles de las casillas de acuerdo a la descripción que hemos hecho anteriormente.

Para ello primero debemos tener controladas todas las columnas, todas las filas y todos los cuadrados de 3x3 relacionados con una determinada casilla del tablero. Para ello con la misma función cross('abc', 'def') vamos a generar todas las columnas, todas las filas y todos los cuadrados de 3x3:

row_units = [cross(r, cols) for r in rows]
column_units = [cross(rows, c) for c in cols]
square_units = [cross(rs, cs) for rs in ('ABC','DEF','GHI') for cs in ('123','456','789')]

Lo podemos comprobar:

print (row_units)
[['A1', 'A2', 'A3', 'A4', 'A5', 'A6', 'A7', 'A8', 'A9'], ['B1', 'B2', 'B3', 'B4', 'B5', 'B6', 'B7', 'B8', 'B9'], ['C1', 'C2', 'C3', 'C4', 'C5', 'C6', 'C7', 'C8', 'C9'], ['D1', 'D2', 'D3', 'D4', 'D5', 'D6', 'D7', 'D8', 'D9'], ['E1', 'E2', 'E3', 'E4', 'E5', 'E6', 'E7', 'E8', 'E9'], ['F1', 'F2', 'F3', 'F4', 'F5', 'F6', 'F7', 'F8', 'F9'], ['G1', 'G2', 'G3', 'G4', 'G5', 'G6', 'G7', 'G8', 'G9'], ['H1', 'H2', 'H3', 'H4', 'H5', 'H6', 'H7', 'H8', 'H9'], ['I1', 'I2', 'I3', 'I4', 'I5', 'I6', 'I7', 'I8', 'I9']]
print(column_units)
[['A1', 'B1', 'C1', 'D1', 'E1', 'F1', 'G1', 'H1', 'I1'], ['A2', 'B2', 'C2', 'D2', 'E2', 'F2', 'G2', 'H2', 'I2'], ['A3', 'B3', 'C3', 'D3', 'E3', 'F3', 'G3', 'H3', 'I3'], ['A4', 'B4', 'C4', 'D4', 'E4', 'F4', 'G4', 'H4', 'I4'], ['A5', 'B5', 'C5', 'D5', 'E5', 'F5', 'G5', 'H5', 'I5'], ['A6', 'B6', 'C6', 'D6', 'E6', 'F6', 'G6', 'H6', 'I6'], ['A7', 'B7', 'C7', 'D7', 'E7', 'F7', 'G7', 'H7', 'I7'], ['A8', 'B8', 'C8', 'D8', 'E8', 'F8', 'G8', 'H8', 'I8'], ['A9', 'B9', 'C9', 'D9', 'E9', 'F9', 'G9', 'H9', 'I9']]
print (square_units)
[['A1', 'A2', 'A3', 'B1', 'B2', 'B3', 'C1', 'C2', 'C3'], ['A4', 'A5', 'A6', 'B4', 'B5', 'B6', 'C4', 'C5', 'C6'], ['A7', 'A8', 'A9', 'B7', 'B8', 'B9', 'C7', 'C8', 'C9'], ['D1', 'D2', 'D3', 'E1', 'E2', 'E3', 'F1', 'F2', 'F3'], ['D4', 'D5', 'D6', 'E4', 'E5', 'E6', 'F4', 'F5', 'F6'], ['D7', 'D8', 'D9', 'E7', 'E8', 'E9', 'F7', 'F8', 'F9'], ['G1', 'G2', 'G3', 'H1', 'H2', 'H3', 'I1', 'I2', 'I3'], ['G4', 'G5', 'G6', 'H4', 'H5', 'H6', 'I4', 'I5', 'I6'], ['G7', 'G8', 'G9', 'H7', 'H8', 'H9', 'I7', 'I8', 'I9']]

Juntamos todo en una sola lista:

unitlist = row_units + column_units + square_units

Con el constructor dict() que construye diccionarios directamente de secuencias de pares clave-valor vamos a generar el diccionario units que nos dice por cada casilla s in boxes que casillas componen la fila, la columna i el cuadrado de 3x3 cuyo valor debemos tener en cuenta:

units = dict((s, [u for u in unitlist if s in u]) for s in boxes)

Por otro lado, usando el módulo sets (que permite construir y manipular colecciones no ordenadas de elementos únicos) construimos el diccionario peers que nos elimina duplicados de casillas por cada casilla:

peers = dict((s, set(sum(units[s],[]))-set([s])) for s in boxes)

En resumen, la función eliminate() iterará sobre todas las celdas de la cuadrícula que tienen solo un valor asignado, y borrará este valor de todos sus pares. La vamos a implementar de tal manera que reciba como entrada un diccionario y retornará otro diccionario con los valores eliminados.

def eliminate(values):
    solved_values = [box for box in values.keys() if len(values[box]) == 1]
    for box in solved_values:
        digit = values[box]
        for peer in peers[box]:
            values[peer] = values[peer].replace(digit,'') "elimina el dígito"
    return values

example='483.2.6..9..3.5..1..18.64....81.29..7.......8..67.82....26.95..8..2.3..9..5.1.382'
display(grid_values(example))
display(eliminate(grid_values(example)))

    4         8         3     |123456789     2     123456789 |    6     123456789 123456789 
    9     123456789 123456789 |    3     123456789     5     |123456789 123456789     1     
123456789 123456789     1     |    8     123456789     6     |    4     123456789 123456789 
------------------------------+------------------------------+------------------------------
123456789 123456789     8     |    1     123456789     2     |    9     123456789 123456789 
    7     123456789 123456789 |123456789 123456789 123456789 |123456789 123456789     8     
123456789 123456789     6     |    7     123456789     8     |    2     123456789 123456789 
------------------------------+------------------------------+------------------------------
123456789 123456789     2     |    6     123456789     9     |    5     123456789 123456789 
    8     123456789 123456789 |    2     123456789     3     |123456789 123456789     9     
123456789 123456789     5     |123456789     1     123456789 |    3         8         2     
   4      8      3   |   9      2      17  |   6     579     57  
   9     267     7   |   3      47     5   |   78     27     1   
   25    257     1   |   8      79     6   |   4    23579   357  
---------------------+---------------------+---------------------
   35    345     8   |   1     3456    2   |   9    34567  34567 
   7    123459   49  |  459   34569    4   |   1    13456    8   
  135   13459    6   |   7     3459    8   |   2     1345   345  
---------------------+---------------------+---------------------
   13    1347    2   |   6     478     9   |   5     147     47  
   8     1467    47  |   2     457     3   |   17    1467    9   
   6     4679    5   |   4      1      47  |   3      8      2

3. Casillas con una sola opción

Ahora estamos en la situación de que nos encontramos en un punto donde hemos marcado casillas que en teoría pueden contener varias opciones pero que dados sus pares solo puede ser una de ellas. Para ello, vamos a ir a través de todas las units y en el caso de que encontremos una unit con un valor que solo encaja en una casilla, vamos a asignar este valor en dicha casilla. Por ejemplo, en nuestro ejemplo, el primer cuadrado 3x3 tiene los siguientes valores:

+---------------------+
|   4      8      3   |  
|   9     267     7   |   
|   25    257     1   |  
+---------------------+

Si miramos la casilla B2 vemos que puede contener tres valores: 2,6 o 7. Pero resulta que solo el 6 puede aparecer en esta casilla, por ello ya le asignamos este valor a la casilla eliminando las otras opciones.

display(example_after_eliminate)
example_after_only_choice=only_choice(example_after_eliminate)
print (" "), print (" "), print (" ")
display(example_after_only_choice)

   4      8      3   |   9      2      17  |   6     579     57  
   9     267     7   |   3      47     5   |   78     27     1   
   25    257     1   |   8      79     6   |   4    23579   357  
---------------------+---------------------+---------------------
   35    345     8   |   1     3456    2   |   9    34567  34567 
   7    123459   49  |  459   34569    4   |   1    13456    8   
  135   13459    6   |   7     3459    8   |   2     1345   345  
---------------------+---------------------+---------------------
   13    1347    2   |   6     478     9   |   5     147     47  
   8     1467    47  |   2     457     3   |   17    1467    9   
   6     4679    5   |   4      1      47  |   3      8      2   
 
 
 
  4     8     3   |  9     2     1   |  6    579    57  
  9     6     7   |  3     4     5   |  8     27    1   
  2     5     1   |  8     7     6   |  4   23579  357  
------------------+------------------+------------------
  35   345    8   |  1    3456   2   |  9     7     6   
  7     2     9   |  5   34569   4   |  1   13456   8   
 135  13459   6   |  7    3459   8   |  2    1345  345  
------------------+------------------+------------------
  13   1347   2   |  6     8     9   |  5    147    47  
  8    1467   47  |  2     5     3   |  7     6     9   
  6     9     5   |  4     1     7   |  3     8     2

4. Propagación de restricciones

Después de analizar estas dos estrategias para encontrar limitaciones locales que nos permiten encontrar valores a las casillas, lo que intuitivamente se nos ocurre es combinarlas iterativamente para ir resolviendo el sudoku, donde en cada iteración, los nuevos valores resueltos nos dan la solución para otras casillas. Por tanto, el código que nos queda podría ser:

def reduce_puzzle(values):
    stalled = False
    while not stalled:
        # Check how many boxes have a determined value
        solved_values_before = len([box for box in values.keys() if len(values[box]) == 1])

        # se the Eliminate Strategy
        values = eliminate(values)

        # Use the Only Choice Strategy
        values = only_choice(values)

        # Check how many boxes have a determined value, to compare
        solved_values_after = len([box for box in values.keys() if len(values[box]) == 1])
        # If no new values were added, stop the loop.
        stalled = solved_values_before == solved_values_after
        # Sanity check, return False if there is a box with zero available values:
        if len([box for box in values.keys() if len(values[box]) == 0]):
            return False
    return values

En este código tenemos en cuenta cuando debemos parar, con la condición de stalled = solved_values_before == solved_values_after, que nos indica cuando en una nueva iteración no se ha podido resolver ninguna nueva casilla. Es el caso que retorna false porque alguna casilla no contenga ningún valor posible (lo veremos en el siguiente apartado).

Si retomamos el ejemplo inicial vemos que con estas dos simples estrategias podemos solucionar el sudoku:

example='..3.2.6..9..3.5..1..18.64....81.29..7.......8..67.82....26.95..8..2.3..9..5.1.3..'
display(grid_values_original(example))
display(reduce_puzzle(grid_values(example)))

. . 3 |. 2 . |6 . . 
9 . . |3 . 5 |. . 1 
. . 1 |8 . 6 |4 . . 
------+------+------
. . 8 |1 . 2 |9 . . 
7 . . |. . . |. . 8 
. . 6 |7 . 8 |2 . . 
------+------+------
. . 2 |6 . 9 |5 . . 
8 . . |2 . 3 |. . 9 
. . 5 |. 1 . |3 . . 
 
 
 
4 8 3 |9 2 1 |6 5 7 
9 6 7 |3 4 5 |8 2 1 
2 5 1 |8 7 6 |4 9 3 
------+------+------
5 4 8 |1 3 2 |9 7 6 
7 2 9 |5 6 4 |1 3 8 
1 3 6 |7 9 8 |2 4 5 
------+------+------
3 7 2 |6 8 9 |5 1 4 
8 1 4 |2 5 3 |7 6 9 
6 9 5 |4 1 7 |3 8 2

5. Estategia `Search`

¿Pero estamos seguros que únicamente con las dos anteriores estrategias tenemos suficiente para resolver cualquier sudoku? Veamos el siguiente ejemplo:

example='2.............62....1....7......8...3...9...7...6..4...4....8....52.............3'
display(grid_values_original(example))
display(reduce_sudoku(grid_values(example)))

2 . . |. . . |. . . 
. . . |. . 6 |2 . . 
. . 1 |. . . |. 7 . 
------+------+------
. . . |. . 8 |. . . 
3 . . |. 9 . |. . 7 
. . . |6 . . |4 . . 
------+------+------
. 4 . |. . . |8 . . 
. . 5 |2 . . |. . . 
. . . |. . . |. . 3 

   2     356789  346789 |1345789  134578  134579 | 13569  1345689  145689 
 45789   35789   34789  |1345789  134578    6    |   2     134589  14589  
 45689   35689     1    | 34589   23458   23459  |  3569     7     45689  
------------------------+------------------------+------------------------
 145679  125679  24679  | 13457   123457    8    | 13569   123569  12569  
   3     12568    2468  |  145      9      1245  |  156    12568     7    
 15789   125789   2789  |   6     12357   12357  |   4     123589  12589  
------------------------+------------------------+------------------------
  1679     4     23679  | 13579   13567   13579  |   8     12569   12569  
 16789   136789    5    |   2     134678  13479  |  1679    1469    1469  
 16789   126789  26789  | 145789  145678  14579  | 15679   124569    3

¿Qué pasa si tenemos un sudoku que no sabemos solucionar tan fácilmente? Vamos a presentar otra técnica básica del mundo de la Inteligencia Artificial para solucionar este problema. Se conoce como Backtracking. No entraremos en detalle, pero la idea es que en el proceso de resolución de problemas, a menudo llegamos al punto en que existen varias posibilidades. Una forma de atacar el problema es crear un árbol completo de posibilidades y recorrer el árbol hasta encontrar nuestra solución.

Por ejemplo, la casilla A2 tiene 5 posibilidades: 4, 5, 7, 8 y 9. Lo que hacemos es considerar que contiene un 4 y resolver el Sudoku. Si no lo podemos resolver (nos vendrá indicado por el retorno de false en la función reduce_puzzle()) probamos con el siguiente, el 5, y así sucesivamente. Evidentemente es 5 veces más trabajo, pero es la manera de conseguir todas las opciones.

El código que realiza recursivamente esta iteración por todas las opciones es:

def search(values):
    values = reduce_puzzle(values)
    if values is False:
        return False ## Failed earlier
    if all(len(values[s]) == 1 for s in boxes): 
        return values ## Solved!
    
    # Choose one of the unfilled squares with the fewest possibilities
    unfilled_squares= [(len(values[s]), s) for s in boxes if len(values[s]) > 1]
    n,s = min(unfilled_squares)
    
    # recurrence to solve each one of the resulting sudokus
    for value in values[s]:
        nova_sudoku = values.copy()
        nova_sudoku[s] = value
        attempt = search(nova_sudoku)
        if attempt:
            return attempt

def solve(grid):
    # Create a dictionary of values from the grid
    values = grid_values(grid)
    return search(values)

Veamos ahora si se puede resolver nuestro anterior ejemplo:

example='2.............62....1....7......8...3...9...7...6..4...4....8....52.............3'
display(grid_values_original(example))
display(solve(example))

2 . . |. . . |. . . 
. . . |. . 6 |2 . . 
. . 1 |. . . |. 7 . 
------+------+------
. . . |. . 8 |. . . 
3 . . |. 9 . |. . 7 
. . . |6 . . |4 . . 
------+------+------
. 4 . |. . . |8 . . 
. . 5 |2 . . |. . . 
. . . |. . . |. . 3 

2 9 6 |3 4 7 |1 5 8 
5 3 7 |8 1 6 |2 4 9 
4 8 1 |9 2 5 |3 7 6 
------+------+------
1 5 9 |4 7 8 |6 3 2 
3 6 4 |1 9 2 |5 8 7 
7 2 8 |6 5 3 |4 9 1 
------+------+------
9 4 3 |7 6 1 |8 2 5 
8 1 5 |2 3 9 |7 6 4 
6 7 2 |5 8 4 |9 1 3

6. Y para acabar

En este post he querido mostrar con la excusa de resolver un Sudoku como es un algoritmo que usa técnicas simples de inteligencia artificial. Ahora bien, debo enfatizar que en realidad los problemas como el Ajedrez, GO o Poker, mencionados anteriormente, tienen una complejidad tal que aplicar un algoritmo de Backtracking como el presentado aquí es imposible, pues tardaríamos siglos en computar la solución (el juego del Sudoku a pesar de todo tiene muy pocas combinaciones para explorar). En estos casos existen un gran número de técnicas que si el lector le interesa profundizar un poco más le recomiendo el libro Artificial Intelligence, a modern approach que solo contiene 1132 páginas. Quizás hay otros con menos páginas pero no duden que este está muy bien.

En el repositorio de github encontrarán el notebook .ipynb que seguro les puede facilitar seguir este post. Suerte!

## 7. Agradecimientos Para este ejercicio me he inspirado en el [fantástico post de Peter Norvig](http://norvig.com/sudoku.html) y parte del programa de [Artificial Intelligence de Udacity](https://www.udacity.com). Añadir mi agradecimiento a [Francesc Sastre Cabot](https://xiscosc.github.io/) y [Alberto Pou Quirós](https://github.com/bertini36) por la revisión que han realizado a la versión [github](https://github.com/jorditorresBCN/Sudoku) de este post antes de su publicación.

Name		Name	Last commit message	Last commit date
Latest commit History 47 Commits
LICENSE		LICENSE
README.md		README.md
Sudoku.ipynb		Sudoku.ipynb

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Repository files navigation

Tu primer programa de Inteligencia Artificial: resolver un Sudoku

1. Notación y nomenclatura

2. Eliminación de opciones en una casilla

Descripción

función `grid_values()`

función `eliminate()`

3. Casillas con una sola opción

4. Propagación de restricciones

5. Estategia `Search`

6. Y para acabar

About

Releases

Packages

Contributors 2

Languages

License

jorditorresBCN/Sudoku

Folders and files

Latest commit

History

Repository files navigation

Tu primer programa de Inteligencia Artificial: resolver un Sudoku

1. Notación y nomenclatura

2. Eliminación de opciones en una casilla

Descripción

función grid_values()

función eliminate()

3. Casillas con una sola opción

4. Propagación de restricciones

5. Estategia Search

6. Y para acabar

About

Resources

License

Stars

Watchers

Forks

Releases

Packages 0

Contributors 2

Languages

función `grid_values()`

función `eliminate()`

5. Estategia `Search`

Packages