Comment jouer et gagner au sudoku - Utiliser les mathématiques et l'apprentissage automatique pour résoudre chaque puzzle de Sudoku

Sudoku (et ses prédécesseurs) est joué depuis plus de cent ans. Quand il est sorti pour la première fois, les gens devaient résoudre les énigmes en utilisant uniquement leur esprit. Maintenant, nous avons des ordinateurs! (Ok, donc la plupart des gens utilisent encore leur esprit ...)

Dans cet article, vous apprendrez à jouer et à gagner au Sudoku. Mais plus important encore, vous apprendrez à utiliser l'apprentissage automatique pour résoudre facilement tous les casse-tête de Sudoku. Qui a besoin de réfléchir quand vous pouvez laisser l'ordinateur penser à votre place. ?

Peter Norvig a développé un programme élégant utilisant Python pour gagner un sudoku en utilisant la propagation et la recherche de contraintes. La solution de Norvig est considérée comme un classique et est souvent mentionnée lorsque les gens développent leur propre code pour jouer au Sudoku. Après avoir examiné Sudoku et certaines stratégies, je décomposerai le code de Norvig étape par étape afin que vous puissiez comprendre comment cela fonctionne.

Qu'est-ce que le Sudoku?

Sudoku est un puzzle de placement de nombres et il existe plusieurs types différents. Cet article concerne le type le plus populaire.

L'objectif est de remplir une grille 9x9 avec des chiffres (1-9) de sorte que chaque colonne, ligne et chacune des neuf sous-grilles 3x3 (également appelées boîtes) contiennent tous chacun des chiffres de 1 à 9. Les puzzles commencent par quelques numéros déjà sur la grille et c'est à vous de remplir les autres numéros.

Dans l'image ci-dessous à partir d'un jeu de Sudoku, le nombre qui devrait figurer dans le carré bleu en surbrillance ne peut être dans aucun des carrés jaunes correspondant à la colonne, à la ligne et à la case 3x3.

Comment résoudre Sudoku

Lorsque vous résolvez un puzzle de Sudoku, vous devez constamment faire deux choses. La première chose à faire est d'éliminer les nombres des lignes, des colonnes et des boîtes (sous-grilles 3x3). La deuxième chose à faire est de rechercher un seul candidat.

Dans l'exemple ci-dessous, les nombres possibles pour chaque carré sont indiqués dans une police plus petite. Les nombres possibles ont été déterminés en éliminant tous les chiffres qui apparaissent dans la même colonne, ligne ou case. La plupart des gens détermineront le nombre possible pour une boîte à la fois, plutôt que pour la grille complète.

Après avoir éliminé les nombres, vous pouvez rechercher des candidats uniques. Cela signifie trouver un carré qui ne peut être qu'un seul nombre possible. Dans l'exemple ci-dessous, les deux carrés surlignés en jaune doivent contenir 1 et 8 car tous les autres chiffres ont été éliminés puisqu'ils apparaissent déjà dans la colonne, la ligne ou la case du carré.

Maintenant que les deux carrés surlignés en jaune sont connus, cela élimine plus de possibilités des autres carrés. Vous savez maintenant que le carré surligné en bleu doit être 7.

Si vous continuez à trouver les candidats uniques puis à éliminer les options des autres cases, vous pouvez éventuellement atteindre le point où il n'y a plus de candidats uniques.

À ce stade, vous pouvez rechercher des solutions possibles aux carrés où le nombre ne se trouve que dans un seul carré dans une boîte, une ligne ou une colonne. Dans l'exemple ci-dessous, nous pouvons déterminer que la solution du carré surligné en bleu doit être 6 puisque le nombre 6 n'apparaît dans aucun autre carré de la boîte jaune.

Parfois, le tableau atteindra un état où il semble que chaque carré non résolu pourrait potentiellement avoir plusieurs valeurs. Cela signifie que vous pouvez choisir plusieurs chemins et il n'est pas évident de savoir quel chemin mènera à la résolution du puzzle.

À ce stade, il est nécessaire d'essayer chaque option. Choisissez-en un et continuez à résoudre jusqu'à ce qu'il devienne clair que l'option que vous avez choisie ne peut pas être une solution. Vous devrez alors revenir en arrière et essayer une autre option.

Ce type de recherche peut être facilement effectué avec un ordinateur en utilisant un arbre de recherche binaire. Lorsqu'il y a l'option de deux nombres différents pour résoudre un carré, il est nécessaire de se diviser en deux possibilités différentes. Un arbre de recherche binaire permettra à un algorithme de descendre dans une branche de choix, puis d'essayer une autre branche de choix.

Nous allons maintenant voir du code Python capable de résoudre des énigmes de Sudoku en utilisant une méthode similaire à celle qui vient d'être décrite.

Le programme de Peter Norvig pour gagner le Sudoku

Peter Norvig a expliqué son approche de la résolution de Sudoku et le code qu'il a utilisé dans son article Solving Every Sudoku Puzzle.

Certains peuvent trouver son explication un peu difficile à suivre, en particulier les débutants. Je vais décomposer les choses pour qu'il soit plus facile de comprendre comment fonctionne le code de Norvig.

Dans cet article, le code Python 2 de Norvig a été mis à jour vers Python 3. (Conversion Python 3 par Naoki Shibuya.) Je vais parcourir le code quelques lignes à la fois mais vous pouvez voir le code complet à la fin de cet article . Pour certaines personnes, il peut être utile de consulter le code complet avant de poursuivre la lecture.

Tout d'abord, nous aborderons la configuration de base et la notation. Voici comment Norvig décrit la notation de base qu'il utilise dans son code:

Un puzzle Sudoku est une grille de 81 carrés; la majorité des passionnés appellent les colonnes 1 à 9, les lignes AI et appellent une collection de neuf carrés (colonne, ligne ou boîte) une unité et les carrés qui partagent une unité les pairs .

Voici les noms des carrés:

 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 définit les chiffres, les lignes et les colonnes comme des chaînes:

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

Vous remarquerez que la valeur colsest égale digits. Bien qu'ils aient la même valeur, ils représentent des choses différentes. La digitsvariable représente les chiffres qui vont dans un carré pour résoudre le puzzle. La colsvariable représente les noms des colonnes de la grille.

Les carrés sont également définis comme des chaînes mais les chaînes sont créées avec une fonction:

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 partie retour de la crossfonction ( [a+b for a in A for b in B]) est juste une manière sophistiquée d'écrire ce code:

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

La squaresvariable équivaut maintenant à une liste de tous les noms de carrés.

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

Chaque carré de la grille a 3 unités et 20 pairs. Les unités d'un carré sont la ligne, la colonne et la boîte dans lesquelles il apparaît. Les pairs d'un carré sont tous les autres carrés des unités. Par exemple, voici les unités et les pairs du carré 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:

nous utiliserons une heuristique commune appelée valeurs minimales restantes, ce qui signifie que nous choisissons le (ou l'un des) carré avec le nombre minimum de valeurs possibles. Pourquoi? Considérez grid2 ci-dessus. Supposons que nous choisissions d'abord B3. Il a 7 possibilités (1256789), nous nous attendons donc à ce que nous devions mal avec la probabilité 6/7. Si à la place nous avons choisi G2, qui n'a que 2 possibilités (89), nous nous attendrions à nous tromper avec une probabilité seulement 1/2. Ainsi, nous choisissons le carré avec le moins de possibilités et les meilleures chances de deviner correctement.

Les chiffres sont considérés dans l'ordre numérique.

Voici la searchfonction, ainsi que la solvefonction qui analyse la grille initiale et les appels 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