Solveur de Sudoku le plus court en Python - Comment ça marche ?

Question

J'étais en train de jouer avec mon propre solveur de Sudoku et je cherchais des indications pour une conception bonne et rapide quand je suis tombé sur ceci :

def r(a):i=a.find('0');~i or exit(a);[m
in[(i-j)%9*(i/9^j/9)*(i/27^j/27|i%9/3^j%9/3)or a[j]for
j in range(81)]or r(a[:i]+m+a[i+1:])for m in'%d'%5**18]
from sys import*;r(argv[1])

Ma propre mise en œuvre résout les Sudokus de la même manière que je les résous dans ma tête, mais comment fonctionne cet algorithme énigmatique ?

http://scottkirkwood.blogspot.com/2006/07/shortest-sudoku-solver-in-python.html

Answer 1

Eh bien, vous pouvez rendre les choses un peu plus faciles en améliorant la syntaxe :

def r(a):
  i = a.find('0')
  ~i or exit(a)
  [m in[(i-j)%9*(i/9^j/9)*(i/27^j/27|i%9/3^j%9/3)or a[j]for j in range(81)] or r(a[:i]+m+a[i+1:])for m in'%d'%5**18]
from sys import *
r(argv[1])

Je nettoie un peu :

from sys import exit, argv
def r(a):
  i = a.find('0')
  if i == -1:
    exit(a)
  for m in '%d' % 5**18:
    m in[(i-j)%9*(i/9^j/9)*(i/27^j/27|i%9/3^j%9/3) or a[j] for j in range(81)] or r(a[:i]+m+a[i+1:])

r(argv[1])

Ok, donc ce script attend un argument de ligne de commande, et appelle la fonction r dessus. S'il n'y a pas de zéros dans cette chaîne, r sort et imprime son argument.

(Si un autre type d'objet est passé, None est équivalent à passer zéro, et tout autre objet est imprimé dans sys.stderr et entraîne un code de sortie de 1. de 1. En particulier, sys.exit("un message d'erreur") est un objet de type moyen rapide de quitter un programme lorsqu'une erreur se produit. Voir http://www.python.org/doc/2.5.2/lib/module-sys.html )

Je suppose que cela signifie que les zéros correspondent à des espaces ouverts, et qu'un puzzle sans zéros est résolu. Et puis il y a cette vilaine expression récursive.

La boucle est intéressante : for m in'%d'%5**18

Pourquoi 5**18 ? Il s'avère que '%d'%5**18 évalue à '3814697265625' . Cette chaîne de caractères contient au moins une fois chacun des chiffres de 1 à 9. Elle essaie donc peut-être de les placer tous. En fait, on dirait que c'est ce que r(a[:i]+m+a[i+1:]) fait : appeler récursivement r, avec le premier blanc rempli par un chiffre de cette chaîne. Mais cela ne se produit que si l'expression précédente est fausse. Voyons cela :

m in [(i-j)%9*(i/9^j/9)*(i/27^j/27|i%9/3^j%9/3) or a[j] for j in range(81)]

Le placement n'est donc effectué que si m ne figure pas dans cette liste de monstres. Chaque élément est soit un nombre (si la première expression est non nulle), soit un caractère (si la première expression est nulle). m est exclu comme substitution possible s'il apparaît comme un caractère, ce qui ne peut arriver que si la première expression est nulle. Quand l'expression est-elle nulle ?

Il comporte trois parties qui se multiplient :

• (i-j)%9 qui vaut zéro si i et j sont séparés par un multiple de 9, c'est-à-dire la même colonne.
• (i/9^j/9) qui est nulle si i/9 == j/9, c'est-à-dire la même ligne.
• (i/27^j/27|i%9/3^j%9/3) qui est nul si les deux sont nuls :
• • i/27^j^27 qui est nul si i/27 == j/27, c'est-à-dire le même bloc de trois lignes
• • i%9/3^j%9/3 qui est nul si i%9/3 == j%9/3, c'est-à-dire le même bloc de trois colonnes

Si l'une de ces trois parties est nulle, l'expression entière est nulle. En d'autres termes, si i et j partagent une ligne, une colonne ou un bloc 3x3, alors la valeur de j ne peut pas être utilisée comme candidat pour le blanc en i. Aha !

from sys import exit, argv
def r(a):
  i = a.find('0')
  if i == -1:
    exit(a)
  for m in '3814697265625':
    okay = True
    for j in range(81):
      if (i-j)%9 == 0 or (i/9 == j/9) or (i/27 == j/27 and i%9/3 == j%9/3):
        if a[j] == m:
          okay = False
          break
    if okay:
      # At this point, m is not excluded by any row, column, or block, so let's place it and recurse
      r(a[:i]+m+a[i+1:])

r(argv[1])

Notez que si aucun des placements ne fonctionne, r reviendra et remontera jusqu'au point où quelque chose d'autre peut être choisi, il s'agit donc d'un algorithme basique de profondeur première.

N'utilisant aucune heuristique, il n'est pas particulièrement efficace. J'ai pris ce puzzle de Wikipedia ( http://en.wikipedia.org/wiki/Sudoku ) :

$ time python sudoku.py 530070000600195000098000060800060003400803001700020006060000280000419005000080079
534678912672195348198342567859761423426853791713924856961537284287419635345286179

real    0m47.881s
user    0m47.223s
sys 0m0.137s

Addendum : Comment je le réécrirais en tant que programmeur de maintenance (cette version a une vitesse d'environ 93x :)

import sys

def same_row(i,j): return (i/9 == j/9)
def same_col(i,j): return (i-j) % 9 == 0
def same_block(i,j): return (i/27 == j/27 and i%9/3 == j%9/3)

def r(a):
  i = a.find('0')
  if i == -1:
    sys.exit(a)

  excluded_numbers = set()
  for j in range(81):
    if same_row(i,j) or same_col(i,j) or same_block(i,j):
      excluded_numbers.add(a[j])

  for m in '123456789':
    if m not in excluded_numbers:
      # At this point, m is not excluded by any row, column, or block, so let's place it and recurse
      r(a[:i]+m+a[i+1:])

if __name__ == '__main__':
  if len(sys.argv) == 2 and len(sys.argv[1]) == 81:
    r(sys.argv[1])
  else:
    print 'Usage: python sudoku.py puzzle'
    print '  where puzzle is an 81 character string representing the puzzle read left-to-right, top-to-bottom, and 0 is a blank'

Answer 2

Le désobscurcir :

def r(a):
    i = a.find('0') # returns -1 on fail, index otherwise
    ~i or exit(a) # ~(-1) == 0, anthing else is not 0
                  # thus: if i == -1: exit(a)
    inner_lexp = [ (i-j)%9*(i/9 ^ j/9)*(i/27 ^ j/27 | i%9/3 ^ j%9/3) or a[j] 
                   for j in range(81)]  # r appears to be a string of 81 
                                        # characters with 0 for empty and 1-9 
                                        # otherwise
    [m in inner_lexp or r(a[:i]+m+a[i+1:]) for m in'%d'%5**18] # recurse
                            # trying all possible digits for that empty field
                            # if m is not in the inner lexp

from sys import *
r(argv[1]) # thus, a is some string

Donc, nous avons juste besoin de travailler sur l'expression de la liste interne. Je sais qu'elle collecte les chiffres définis dans la ligne -- sinon, le code qui l'entoure n'a aucun sens. Cependant, je n'ai aucune idée de la façon dont elle le fait (et je suis trop fatigué pour m'occuper de cette fantaisie binaire maintenant, désolé).

Answer 3

r(a) est une fonction récursive qui tente de remplir un fichier 0 dans le tableau à chaque étape.

i=a.find('0');~i or exit(a) est la terminaison en cas de succès. Si plus aucun 0 les valeurs existent dans le conseil, nous avons terminé.

m est la valeur actuelle, nous essayerons de remplir le champ 0 avec.

m in[(i-j)%9*(i/9^j/9)*(i/27^j/27|i%9/3^j%9/3)or a[j]for j in range(81)] évalue à truthy s'il est manifestement incorrect de mettre m dans l'actuel 0 . Nous le surnommerons "is_bad". C'est la partie la plus délicate :)

is_bad or r(a[:i]+m+a[i+1:] est une étape récursive conditionnelle. Elle essaiera récursivement d'évaluer le prochain 0 dans le conseil si le candidat actuel à la solution semble être sain d'esprit.

for m in '%d'%5**18 énumère tous les chiffres de 1 à 9 (de manière inefficace).

Answer 4

De nombreux solveurs de sudoku courts essaient récursivement tous les nombres légaux possibles jusqu'à ce qu'ils remplissent les cellules avec succès. Je ne l'ai pas démonté, mais en le survolant, on dirait que c'est ce qu'il fait.

Answer 5

Le code ne fonctionne pas réellement. Vous pouvez le tester vous-même. Voici un exemple de puzzle sudoku non résolu :

807000003602080000000200900040005001000798000200100070004003000000040108300000506

Vous pouvez utiliser ce site web ( http://www.sudokuwiki.org/sudoku.htm ), cliquez sur import puzzle et copiez simplement la chaîne ci-dessus. La sortie du programme python est : 817311213622482322131224934443535441555798655266156777774663869988847188399979596

ce qui ne correspond pas à la solution. En fait, vous pouvez déjà voir une contradiction, deux 1 dans la première ligne.