Cómo jugar y ganar sudoku: uso de matemáticas y aprendizaje automático para resolver todos los rompecabezas de sudoku

El sudoku (y sus predecesores) se ha jugado durante más de cien años. Cuando salió a la luz, la gente tenía que resolver los acertijos usando solo sus mentes. ¡Ahora tenemos computadoras! (Ok, entonces la mayoría de la gente todavía usa sus mentes ...)

En este artículo, aprenderá a jugar y ganar Sudoku. Pero lo que es más importante, aprenderá a utilizar el aprendizaje automático para resolver fácilmente todos los Sudoku. Quién necesita pensar cuando puede dejar que la computadora piense por usted. ?

Peter Norvig desarrolló un elegante programa usando Python para ganar sudoku usando la propagación de restricciones y la búsqueda. La solución de Norvig se considera un clásico y a menudo se la menciona cuando las personas desarrollan su propio código para jugar al Sudoku. Después de revisar el Sudoku y algunas estrategias, desglosaré el código de Norvig paso a paso para que puedas entender cómo funciona.

¿Qué es el Sudoku?

Sudoku es un rompecabezas de colocación de números y hay algunos tipos diferentes. Este artículo trata sobre el tipo más popular.

El objetivo es llenar una cuadrícula de 9x9 con dígitos (1-9) para que cada columna, fila y cada una de las nueve subcuadrículas de 3x3 (también llamadas cajas) contengan cada uno de los dígitos del 1 al 9. Los acertijos comienzan con algunos números que ya están en la cuadrícula y depende de usted completar los otros números.

En la imagen de abajo de un juego de Sudoku, el número que debe ir en el cuadro resaltado en azul no puede estar en ninguno de los cuadrados amarillos correspondientes a la columna, fila y cuadro 3x3.

Cómo resolver sudoku

Al resolver un Sudoku, debes hacer dos cosas constantemente. Lo primero que debe hacer es eliminar números de filas, columnas y cuadros (subcuadrículas de 3x3). Lo segundo que debe hacer es buscar un solo candidato.

En el siguiente ejemplo, los números posibles para cada cuadrado se indican en una fuente más pequeña. Los números posibles se determinaron eliminando todos los dígitos que aparecen en la misma columna, fila o casilla. La mayoría de la gente determinará el número posible para un cuadro a la vez, en lugar de para la cuadrícula completa.

Después de eliminar los números, puede buscar candidatos únicos. Eso significa encontrar un cuadrado que solo puede ser un número posible. En el siguiente ejemplo, los dos cuadrados resaltados en amarillo deben contener 1 y 8 porque todos los demás dígitos han sido eliminados porque ya aparecen en la columna, fila o casilla del cuadrado.

Ahora que se conocen los dos cuadrados resaltados en amarillo, eso elimina más posibilidades de otros cuadrados. Ahora sabes que el cuadrado resaltado en azul debe ser 7.

Si sigue encontrando candidatos únicos y luego eliminando opciones de otros cuadrados, eventualmente puede llegar al punto en el que no haya más candidatos únicos.

En este punto, puede buscar posibles soluciones para cuadrados donde el número está solo en un solo cuadrado en un cuadro, fila o columna. En el siguiente ejemplo podemos determinar que la solución al cuadrado resaltado en azul debe ser 6 ya que el número 6 no ocurre en ningún otro cuadrado del cuadro amarillo.

A veces, el tablero llegará a un estado en el que parece que cada cuadrado sin resolver podría tener varios valores. Eso significa que hay varios caminos que puede elegir y no es obvio qué camino conducirá a resolver el rompecabezas.

En ese momento es necesario probar cada opción. Elija uno y siga resolviendo hasta que quede claro que la opción que eligió no puede ser una solución. Luego tendrá que retroceder y probar una opción diferente.

Este tipo de búsqueda se puede realizar fácilmente con una computadora usando un árbol de búsqueda binario. Cuando existe la opción de dos números diferentes para resolver un cuadrado, es necesario dividir en dos posibilidades diferentes. Un árbol de búsqueda binaria permitirá que un algoritmo vaya por una rama de opciones y luego pruebe con una rama diferente de opciones.

Ahora veremos código Python que puede resolver acertijos de Sudoku usando un método similar al que se acaba de describir.

El programa de Peter Norvig para ganar Sudoku

Peter Norvig explicó su enfoque para resolver Sudoku y el código que usó en su artículo Resolver cada rompecabezas de Sudoku.

Algunos pueden encontrar su explicación un poco difícil de seguir, especialmente los principiantes. Desglosaré las cosas para que sea más fácil entender cómo funciona el código de Norvig.

En este artículo, el código Python 2 de Norvig se ha actualizado a Python 3. (Conversión de Python 3 por Naoki Shibuya). Revisaré el código unas pocas líneas a la vez, pero puede ver el código completo al final de este artículo. . Para algunas personas, puede ser útil revisar el código completo antes de seguir leyendo.

Primero, cubriremos la configuración básica y la notación. Así es como Norvig describe la notación básica que usa en su código:

Un Sudoku es una cuadrícula de 81 cuadrados; la mayoría de los entusiastas etiquetan las columnas 1-9, las filas AI, y llaman a una colección de nueve cuadrados (columna, fila o caja) una unidad y los cuadrados que comparten una unidad los pares .

Aquí están los nombres de los cuadrados:

 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

Norvig define los dígitos, filas y columnas como cadenas:

digits = '123456789' rows = 'ABCDEFGHI' cols = digits

Notarás que colsestá ajustado a igual digits. Si bien tienen el mismo valor, representan cosas diferentes. La digitsvariable representa los dígitos que van en un cuadrado para resolver el rompecabezas. La colsvariable representa los nombres de las columnas de la cuadrícula.

Los cuadrados también se definen como cadenas, pero las cadenas se crean con una función:

def cross(A, B): "Cross product of elements in A and elements in B." return [a+b for a in A for b in B] squares = cross(rows, cols)

La parte de retorno de la crossfunción ( [a+b for a in A for b in B]) es solo una forma elegante de escribir este código:

squares = [] for a in rows: for b in cols: squares.append(a+b)

La squaresvariable ahora es igual a una lista de todos los nombres de cuadrados.

['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']

Cada cuadrado de la cuadrícula tiene 3 unidades y 20 pares. Las unidades de un cuadrado son la fila, la columna y el cuadro en el que aparece. Los pares de un cuadrado son todos los demás cuadrados de las unidades. Por ejemplo, aquí están las unidades y pares para el cuadrado C2:

All the units for each square are created using the cross function with the following code:

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

In Python a dictionary is a collection of key value pairs. The following lines of code creates dictionaries that use the square names as the keys and the three units or 20 peers as the values.

units = dict((s, [u for u in unitlist if s in u]) for s in squares) peers = dict((s, set(sum(units[s],[]))-set([s])) for s in squares)

Now, the 3 units of ‘C2’ can be accessed with units['C2'] and will give the following result:

[['A2', 'B2', 'C2', 'D2', 'E2', 'F2', 'G2', 'H2', 'I2'], ['C1', 'C2', 'C3', 'C4', 'C5', 'C6', 'C7', 'C8', 'C9'], ['A1', 'A2', 'A3', 'B1', 'B2', 'B3', 'C1', 'C2', 'C3']]

Next we'll need two representations of the full Sudoku playing grid. A textual format named grid will be the initial state of the puzzle.

Another representation of the grid will also be needed to internally describe the current state of a puzzle. It will keep track of all remaining possible values for each square and be named values.

Similar to units and peers, values will be a dictionary with squares as keys. The value of each key will be a string of digits that are the possible digits for the square. If the digit was given in the puzzle or has been figured out, there will only be one digit in the key. For example, if there is a grid where A1 is 6 and A2 is empty, values would look like {'A1': '6', 'A2': '123456789', ...}.

Parse Grid and Grid Values Functions

The parse_grid function (code below) converts the grid to a dictionary of possible values.  The grid is the given Sukou puzzle. The grid_values function extracts the important values which are digits, 0, and .. In the values dictionary, the squares are the keys and the given digits in the grid are the values.

For each square with a given value, the assign function is used to assign the value to the square and eliminate the value from the peers. The assign function is covered soon. If anything goes wrong, the function returns False.

Here is the code for the parse_grid and grid_values functions.

def parse_grid(grid): """Convert grid to a dict of possible values, {square: digits}, or return False if a contradiction is detected.""" ## To start, every square can be any digit; then assign values from the grid. values = dict((s, digits) for s in squares) for s,d in grid_values(grid).items(): if d in digits and not assign(values, s, d): return False ## (Fail if we can't assign d to square s.) return values def grid_values(grid): "Convert grid into a dict of {square: char} with '0' or '.' for empties." chars = [c for c in grid if c in digits or c in '0.'] assert len(chars) == 81 return dict(zip(squares, chars))

Constraint Propagation

The initial values for the squares will be either specific digits (1-9) or an empty value. We can apply constraints to each square and eliminate values that are impossible.

Norvig uses two strategies to help determine the correct values for the squares (which correspond to the strategies above):

(1) If a square has only one possible value, then eliminate that value from the square's peers.

(2) If a unit has only one possible place for a value, then put the value there.

An example of the first strategy is that if we know that A1 has a value of 5, then 5 can be removed from all 20 of its peers.

Here is an example of the second strategy: if it can be determined that none of A1 through A8 contains 9 as a possible value, then we can be sure that A9 has a value of 9 since 9 must occur somewhere in the unit.

Every time a square is updated, it will cause possible updates to all its peers. This process will keep continuing and it is called constraint propagation.

Assign Function

The assign(values, s, d) function is called inside the parse_grid function. It returns the updated values. It accepts three arguments: values, s, and d.

Remember, values is a dictionary that associates each square to all possible digit values for that square. s is the square we are assigning a value to and d is the value that needs to be assigned to the square. At the start d comes from the given puzzle we are solving.

It calls the function eliminate(values, s, d) to eliminate every value from s except d.

If there is a contradiction, such as two squares being assigned the same number, the eliminate function will return False.

def assign(values, s, d): """Eliminate all the other values (except d) from values[s] and propagate. Return values, except return False if a contradiction is detected.""" other_values = values[s].replace(d, '') if all(eliminate(values, s, d2) for d2 in other_values): return values else: return False

Eliminate Function

We saw that the assign function calls the eliminate function. The eliminate function is called like this: eliminate(values, s, d2) for d2 in other_values)

The eliminate function will eliminate values that we know can't be a solution using the two strategies mentioned above. The first strategy is that when there is only one potential value for s, that value is removed from the peers of s. The second strategy is that when there is only one location that a value d can go, that value is removed from all the peers.

Here is the full function:

def eliminate(values, s, d): """Eliminate d from values[s]; propagate when values or places <= 2. Return values, except return False if a contradiction is detected.""" if d not in values[s]: return values ## Already eliminated values[s] = values[s].replace(d,'') ## (1) If a square s is reduced to one value d2, then eliminate d2 from the peers. if len(values[s]) == 0: return False ## Contradiction: removed last value elif len(values[s]) == 1: d2 = values[s] if not all(eliminate(values, s2, d2) for s2 in peers[s]): return False ## (2) If a unit u is reduced to only one place for a value d, then put it there. for u in units[s]: dplaces = [s for s in u if d in values[s]] if len(dplaces) == 0: return False ## Contradiction: no place for this value elif len(dplaces) == 1: # d can only be in one place in unit; assign it there if not assign(values, dplaces[0], d): return False return values

Display Function

The display function will display the result after calling parse_grid.

def display(values): "Display these values as a 2-D grid." width = 1+max(len(values[s]) for s in squares) 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) print()

Here is an example of what the grid will look like after calling the display function after parsing a grid that is a hard puzzle.

You will notice that many of the squares have multiple potential values, while some are completely solved. This grid above is the result of rote application of the two strategies from above. But as you can see, those strategies alone are not enough to completely solve the puzzle.

Search

There are many ways to solve a Sukoku problem but some are much more efficient than others. Norvig suggests a specific type of search algorithm.

There are a few things the search algorithm does. First, it makes sure that no solution or contrition have already been found. Then, it chooses an unfilled square and considers all values that are still possible. Finally, one at a time, it tries to assign the square each value, and searches from the resulting position.

Variable ordering is used to choose which square to start exploring. Here is how Norvig describes it:

Usaremos una heurística común llamada valores mínimos restantes, lo que significa que elegimos el cuadrado (o uno de los) con el número mínimo de valores posibles. ¿Por qué? Considere la cuadrícula2 anterior. Supongamos que elegimos B3 primero. Tiene 7 posibilidades (1256789), por lo que esperaríamos adivinar mal con probabilidad 6/7. Si, en cambio, elegimos G2, que solo tiene 2 posibilidades (89), esperaríamos estar equivocados con una probabilidad de solo 1/2. Por lo tanto, elegimos el cuadrado con la menor cantidad de posibilidades y la mayor probabilidad de acertar.

Los dígitos se consideran en orden numérico.

Aquí está la searchfunción, junto con la solvefunción que analiza la cuadrícula inicial y llama search.

def solve(grid): return search(parse_grid(grid)) def search(values): "Using depth-first search and propagation, try all possible values." if values is False: return False ## Failed earlier if all(len(values[s]) == 1 for s in squares): return values ## Solved! ## Chose the unfilled square s with the fewest possibilities n,s = min((len(values[s]), s) for s in squares if len(values[s]) > 1) return some(search(assign(values.copy(), s, d)) for d in values[s])

Per the rules of Sudoku, the puzzle is solved when each square has only one value. The search function is called recursively until the puzzle is solved. values is copied to avoid complexity.

Here is the some function used to check if an attempt succeeds to solve the puzzle.

def some(seq): "Return some element of seq that is true." for e in seq: if e: return e return False

This code will now solve every Sudoku puzzle. You can view the full code below.

Full Sudoku solver code

def cross(A, B): "Cross product of elements in A and elements in B." return [a+b for a in A for b in B] digits = '123456789' rows = 'ABCDEFGHI' cols = digits squares = cross(rows, cols) unitlist = ([cross(rows, c) for c in cols] + [cross(r, cols) for r in rows] + [cross(rs, cs) for rs in ('ABC','DEF','GHI') for cs in ('123','456','789')]) units = dict((s, [u for u in unitlist if s in u]) for s in squares) peers = dict((s, set(sum(units[s],[]))-set([s])) for s in squares) def parse_grid(grid): """Convert grid to a dict of possible values, {square: digits}, or return False if a contradiction is detected.""" ## To start, every square can be any digit; then assign values from the grid. values = dict((s, digits) for s in squares) for s,d in grid_values(grid).items(): if d in digits and not assign(values, s, d): return False ## (Fail if we can't assign d to square s.) return values def grid_values(grid): "Convert grid into a dict of {square: char} with '0' or '.' for empties." chars = [c for c in grid if c in digits or c in '0.'] assert len(chars) == 81 return dict(zip(squares, chars)) def assign(values, s, d): """Eliminate all the other values (except d) from values[s] and propagate. Return values, except return False if a contradiction is detected.""" other_values = values[s].replace(d, '') if all(eliminate(values, s, d2) for d2 in other_values): return values else: return False def eliminate(values, s, d): """Eliminate d from values[s]; propagate when values or places  1) return some(search(assign(values.copy(), s, d)) for d in values[s]) def some(seq): "Return some element of seq that is true." for e in seq: if e: return e return False