Magazine Science

Python : un petit Sudoku pour commencer

Publié le 12 octobre 2008 par Dr_goulu @goulu

Ces temps-ci, je découvre Python, un langage de programmation très apprécié en particulier dans la communauté scientifique. Ce “langage interprété multi paradigme” intègre des concepts développés dans plusieurs langages récents, ce qui en fait peut-être le langage le plus complet disponible actuellement.

Pour une première approche de ce langage, je vous propose l’analyse du

Plus Court Solveur de Sudoku

Voici un  programme en Python de 173 caractères seulement qui serait le plus court solveur de sudoku connu actuellement :

def r(a): i=a.find('0') if i<0:print 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`14**7*9`]r(raw_input())

Ce programme est extrêmement compact et condensé, voire cryptique à l’instar des Cignatures. Ce n’est pas forcément la meilleure façon de programmer, mais ça révèle souvent la puissance cachée de certains langages. Ce programme est décrit en anglais et en détail ici, mais voici son principe en gros et en français:

def r(a): ... r(raw_input()) // définit la fonction “r” qui résout le sudoku, puis on l’appelle en passant en paramètre ce que l’utilisateur a entré au clavier. Ca doit être une chaine de 81 caractères contenant ligne par ligne les chiffres de 1 à 9 donnés, et des 0 aux emplacements vides.

i=a.find('0') if i<0:print a // au début de la fonction, on cherche le premier emplacement vide. Si on ne le trouve pas, on imprime le sudoku résolu

la partie principale de la fonction utilise deux concepts puissants de Python:

  1. la “lazy evaluation” qui fait que l’expression “a or b” est équivalente à “if not(a):b”
  2. la “compréhension de liste” qui permet de créer une liste en écrivant une boucle à l’intérieur de [crochets]. Par exemple “l = [x**2 for x in range(10)]” crée la liste des carrés des 10 premiers nombres entiers

ainsi cette expression [(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)] fournit la “liste d’exclusion” contenant les chiffres qui ne peuvent pas figurer dans le trou à la position i. On l’obtient en parcourant toutes les celllules et en ajoutant à la liste la valeur des cases a[j] situées sur la même ligne, la même colonne ou dans le même bloc que i. Le grand test compliqué détermine ces conditions en utilisant les opérateurs modulo (%), ou binaire (|) et ou exclusif (^).

Finalement, le [m in [...] or r(a[:i]+m+a[i+1:])for m in`14**7*9`] remplit successivement la grille avec les chiffres possibles en utilisant la ‘lazy evaluation’ une fois de plus : ce n’est que si le chiffre m n’est pas dans la liste d’exclusion qu’on execute la partie droite du or, laquelle appelle récursivement la fonction r en lui passant la grille en paramètre la grille a[:i]+m+a[i+1:]. Ici , l’opérateur + sert à concaténer des listes : d’abord les i-èmes premières cases, puis le chiffre m proposé pour la case vide, puis les cases à partir de la i+1 ème.

Ce programme utilise donc une approche “force brute” loin d’être optimale en temps de calcul : on essaie les chiffres possibles dans chaque case vide jusqu’à ce que ça marche.

Reste à découvrir une astuce de geek que je ne connaissais pas : 14**7*9 vaut 948721536, un nombre qui contient les chiffres 123456789, dans le désordre, mais ça va aussi pour notre application. Les backquotes ´…´ servent à former une chaine, comme d’ailleurs la fonction str(). L’avantage de ´14**7*9´sur “123456789″ ? ben c’est évident : il faut deux bytes de moins …

Posted in Programmation  Tagged: langages, Python  

Vous pourriez être intéressé par :

Retour à La Une de Logo Paperblog

Ces articles peuvent vous intéresser :

  • Pour meilleur ami... un python !

    Un petit Cambodgien a pour meilleur ami... un python ! En tant que parents responsables, le paysan cambodgien Khuorn Sam Ol et sa femme ne devraient pas être... Lire la suite

    Par  Chantal Doumont
    INSOLITE
  • Monty Python: Bicycle repairman!

    L’humour anglais dans toute sa splendeur avec un sketch des Monty Python. Avec le célèbre bicycle repairman ! … toujours là pour dépanner votre vélo j’ai... Lire la suite

    Par  Zigzornif
    HUMOUR, INSOLITE, VIDÉOS INSOLITES
  • Installer Python sous Mac OS X avec Macports

    Lors de ma découverte de Mac OS X et comment développer sur cette plate-forme, j'ai, je dois le dire, rencontré quelques problèmes concernant l'installation de... Lire la suite

    Par  Jibaku
    HIGH TECH, INFORMATIQUE
  • Gare au python !

    Teresa Rossiter, gérante d'un magasin d'animaux à Eugene, dans l'Oregon (nord-ouest des Etats-Unis), a été attaquée par un python de 3,6 mètres de long exposé... Lire la suite

    Par  Chantal Doumont
    INSOLITE
  • BibiServer : un serveur web en Python

    Pour la plupart des personnes, un serveur web n’est qu’une machine sur laquelle est installée un logiciel (le plus souvent Apache) et qui rend accessible nos... Lire la suite

    Par  Kphoen
    INTERNET, WEB2.0
  • Sudoku et Bomberman sur iPhone / iPod Touch

    L'iPhone n'est pas encore disponible au Japon, mais les éditeurs japonais travaillent déjà depuis quelques temps sur les applications qu'ils pourront proposer... Lire la suite

    Par  Thomas Bertrand
    ASIE, RÉGIONS DU MONDE, VOYAGES
  • Photos...Un Python de Deux Mètres sort des WC...

    Une histoire très insolite, digne d'un film d'horreur, celle qu'a vécu un citoyen australien dans l'un des endroits les plus intimes de son appartement. Lire la suite

    Par  Ouss
    INSOLITE, SOCIÉTÉ

A propos de l’auteur


Dr_goulu 3475 partages Voir son profil
Voir son blog