Résolvez le Sudoku avec l'algorithme X

Dans cet article, nous considérons «l'algorithme X» de Knuth et son application pour résoudre le sudoku. La beauté de l'algorithme est que Sudoku est résolu rapidement sans programmation de techniques de solution avancées.

Tout a commencé, en fait, avec les tâches de Project Euler , où, pour obtenir une réponse, vous devez résoudre 50 sudoku. Et il semble qu'il ait reçu une réponse en écrivant un programme pour résoudre une recherche plutôt stupide, mais d'une manière ou d'une autre l'insatisfaction quant à la rapidité de la solution est restée. Après avoir vu comment les gens normaux résolvent le sudoku, j'ai trouvé que l'algorithme X, inventé par Donald Knut, était utilisé pour cela.

Algorithme X

Cet algorithme résout le problème de couvrir précisément l'ensemble. Ou, si vous le souhaitez, il recueille un "puzzle discret", contenant des informations sur la forme des pièces disponibles. Plus formellement:

• Il y a beaucoup de s
• Il existe un ensemble de sous-ensembles Y de cet ensemble
• La tâche consiste à choisir parmi Y de tels éléments Y * que chaque élément de S soit contenu dans un seul des ensembles inclus dans Y *
• Autrement dit, l'union de tous les ensembles dans Y * constitue (couvre) l'ensemble S , et en même temps dans Y * il n'y a pas d'ensembles se croisant par paire

Par exemple, considérons les ensembles
S = {1, 2, 3, 4, 5} et
Y = { A = {1, 2},
B = {2, 3},
C = {1, 5},
D = {1, 4},
E = {5}}
Les ensembles B , D et E forment une couverture exacte de l'ensemble S.

Pour l'algorithme X Knuth, l'ensemble Y est représenté comme une matrice binaire, où les lignes correspondent aux éléments Y et A _{i, j} = 1, si S _j est dans Y _i . C'est-à-dire pour l'exemple ci-dessus:

L'algorithme de recherche de couverture exacte est le suivant:

• Données d'entrée: définit S et Y ; Stack ensembles potentiellement inclus dans la couverture (peut être initialement vide ou avoir déjà certains éléments)
  
  1. Si l'ensemble S est vide, le couvercle souhaité se trouve sur la pile.
  2. Si l'ensemble Y est vide, le revêtement est introuvable.
  3. Nous recherchons un élément s dans l'ensemble S qui est inclus dans le nombre minimum d'ensembles dans Y.
  4. Choisissez parmi Y toutes les lignes X contenant s .
  5. Pour chaque série X, répétez 6-9.
  6. Ajoutez X à la pile comme élément de couverture potentiel.
  7. Nous formons les ensembles S ' et Y' : S ' est S duquel tous les éléments contenus dans X sont supprimés, Y' sont des ensembles de Y qui ne se coupent pas avec X.
  8. Nous appelons l'algorithme X pour S ' , Y' et Stack .
  9. S'il a été constaté à l'étape 7 que la couverture est impossible, retirez l'élément du haut de la Stack et passez au X suivant . Si une solution est trouvée, nous la renvoyons.
  10. S'il n'y a pas de solution pour un X , la tâche n'est pas résolue pour cette entrée.

En général, rien de particulièrement compliqué. Essentiellement - la recherche habituelle en profondeur. Soit dit en passant, nous notons que si vous définissez initialement la pile comme non vide, le problème peut être formulé comme «trouver la couverture exacte qui inclut les éléments qui se trouvent déjà sur la pile».

La subtilité est qu'en pratique cet algorithme est utilisé pour les problèmes où les ensembles en Y sont "petits", c'est-à-dire la matrice est très clairsemée, à cause de laquelle, par exemple, la recherche d'intersections entre colonnes pendant le stockage standard sous la forme d'une matrice prend un temps inacceptable.
Par conséquent, Knut complète cet algorithme avec un mécanisme de "liaison dansante" . La matrice est représentée sous la forme d'une liste bidimensionnelle à double liaison: pour chaque ligne de la liste, seuls les numéros de colonne sont stockés, où cette ligne contient des unités. La liste contient également des liens vers l'élément suivant et précédent dans une ligne et une colonne. Cette organisation vous permet de supprimer des colonnes et des lignes d'une matrice clairsemée pendant O (1) par rapport à O ( m * n ) lorsqu'elle est stockée dans un tableau à deux dimensions.

Il est intéressant de noter qu'Ali Assaf propose une alternative au mécanisme de danse des liens à l'aide de listes associatives, qui vous permet d'implémenter l'algorithme X en plusieurs dizaines de lignes dans des langages de haut niveau.

L'idée est de stocker les colonnes et les lignes de matrice dans des listes associatives. Dans les colonnes, nous stockons les indices de ligne, à l'intersection avec laquelle il y a des éléments non nuls, dans les lignes, respectivement, les indices de colonne. De plus, nous allons stocker les index dans les lignes de manière ordonnée, dans un tableau, nous notons que dans l'algorithme de Knuth, il n'est essentiellement pas nécessaire de modifier les lignes, donc l'optimisation pour supprimer rapidement un élément d'une ligne n'est pas nécessaire. Mais les colonnes seront définies sous la forme d'ensembles, car lors de la suppression d'une ligne d'une matrice, il est nécessaire de supprimer son identifiant de toutes les colonnes (et lors de sa suppression de toutes les colonnes, la ligne disparaît «d'elle-même»).

Considérez l'implémentation de l'algorithme sur Julia.
La matrice de l'exemple ressemblera maintenant à ceci:

 Y = Dict( 'A' => [1, 2], 'B' => [2, 3], 'C' => [1, 5], 'D' => [1, 4], 'E' => [5] ) S = Dict( 1 => Set(['A', 'C', 'D']), 2 => Set(['A', 'B']), 3 => Set(['B']), 4 => Set(['D']), 5 => Set(['C', 'E']) ) 

Pour que l'algorithme fonctionne, vous avez besoin d'une fonction qui supprime des lignes de la matrice qui coupent avec la donnée, et d'une fonction qui renvoie ces lignes à leur place.

 function extract_intersects!(rows, columns, base_row) buf = [] for elt in rows[base_row] #        push!(buf, pop!(columns, elt)) #         for intersecting_row in buf[end] for other_elt in rows[intersecting_row] if other_elt != elt delete!(columns[other_elt], intersecting_row) end end end end return buf end function restore_intersects!(rows, columns, base_row, buf) #       base_row  ,      for elt in Iterators.reverse(rows[base_row]) columns[elt] = pop!(buf) for added_row in columns[elt] for col in rows[added_row] push!(columns[col], added_row) end end end end 

Pour que ces deux fonctions fonctionnent comme il se doit, un stockage ordonné des éléments dans les rangées de la matrice a été requis. Dans la fonction extract_intersects!() , À chaque itération de la boucle externe, les lignes qui se croisent avec base_row mais ne contiennent pas d'éléments vus dans les itérations précédentes sont supprimées de la matrice. Cela garantit que lorsque nous insérons les colonnes dans restore_intersects!() Dans l'ordre inverse, dans la boucle la plus intérieure au moment de l'appel, push!(columns[col], added_row) la columns[col] sera déjà retournée à la matrice, et toutes supprimées dans extract_intersects!() éléments des colonnes seront retournés à leur emplacement d'origine.

Maintenant l'algorithme X lui-même:

 function algorithm_x(rows, columns, cover = []) if isempty(columns) return cover else #       m, c = findmin(Dict(k => length(v) for (k, v) in columns)) for subset in collect(columns[c]) push!(cover, subset) #     #   subset  buf_cols = extract_intersects!(rows, columns, subset) s = algorithm_x(rows, columns, cover) #     - ,  s == nothing || return s restore_intersects!(rows, columns, subset, buf_cols) pop!(cover) end #      columns[c] , #        return nothing end end 

Sudoku

Il y a un algorithme, la question est petite - pour présenter Sudoku comme une tâche de trouver la couverture exacte.

Nous formulons les exigences qui doivent être remplies par un sudoku résolu:

1. Dans chaque cellule, il y a un nombre de 1 à 9 (ou jusqu'à n ² si des carrés de taille différente sont résolus).
2. Dans chaque ligne, chaque numéro apparaît une fois.
3. Dans chaque colonne, chaque nombre apparaît une fois.
4. Dans chaque quadrant, chaque nombre apparaît une fois.

Chacune de ces exigences doit être remplie une seule fois, c'est-à-dire ils forment l'ensemble qui doit être couvert. Il a exactement 4 n ² éléments (colonnes dans la matrice).

Les sous-ensembles que nous considérons sont formés en substituant un nombre spécifique dans une cellule spécifique. Par exemple, le nombre 9 à l'intersection de 1 ligne et 4 colonnes "couvre" un sous-ensemble "dans la cellule (1,4) est un nombre, dans 1 ligne il y a un nombre 9, dans 4 colonnes il y a un nombre 9, dans 2 quadrants il y a un nombre 9" (ce qui implique l'habituel Sudoku 9 × 9).

Après cela, l'algorithme de solution est écrit trivialement.

 #    9×9,      #   -   (row, col, num) #  : # (0, row, col) -   row  col   # (1, row, num) -   row   num # (2, col, num) -   col   num # (3, q, num) -   q   num function xsudoku(puzzle::AbstractMatrix{Int}) rows = Dict() cols = Dict() #   for row in 1:9, col in 1:9, num in 1:9 r = [] quad = ((row-1)÷3)*3 + (col-1)÷3 + 1 push!(r, (0, row, col), (1, row, num), (2, col, num), (3, quad, num)) rows[(row, col, num)] = r end #   for type in 0:3, n1 in 1:9, n2 in 1:9 cols[(type, n1, n2)] = Set() end for (rk, rv) in rows for v in rv push!(cols[v], rk) end end # s -    #  ,     ,    s = [] for i in 1:9, j in 1:9 if puzzle[i, j] > 0 elt = (i, j, puzzle[i,j]) push!(s, elt) #    ,       extract_intersects!(rows, cols, elt) end end # ,   -   success = algorithm_x(rows, cols, s) success != nothing || return nothing #      ret = similar(puzzle) for (i, j, num) in s ret[i,j] = num end return ret end 

Vérifions un exemple:

  julia> @time xsudoku([0 0 0 0 0 0 4 0 0; 3 0 6 0 0 0 0 0 0; 0 0 0 1 9 6 0 3 0; 0 7 0 0 0 0 0 1 0; 8 0 0 2 5 0 0 9 0; 0 4 0 0 0 0 8 0 0; 0 6 0 4 0 9 0 0 8; 0 0 5 0 0 0 0 2 0; 0 0 0 5 0 0 0 0 7]) 0.006326 seconds (54.91 k allocations: 3.321 MiB) 9×9 Array{Int64,2}: 1 5 7 8 3 2 4 6 9 3 9 6 7 4 5 2 8 1 2 8 4 1 9 6 7 3 5 6 7 2 9 8 4 5 1 3 8 3 1 2 5 7 6 9 4 5 4 9 6 1 3 8 7 2 7 6 3 4 2 9 1 5 8 4 1 5 3 7 8 9 2 6 9 2 8 5 6 1 3 4 7 

Cela semble fonctionner et la vitesse est acceptable.

Il convient de noter qu'aucune technique spécifique au Sudoku (comme, par exemple, ici ou ici ) n'était pas définie dans l'algorithme, à l'exception d'une représentation spécifique de l'ensemble souhaité et des éléments de couverture.