Archives par étiquette : résolveur

Sudoku

Résolveur de Sudoku en C++

Laisser un commentaire

Je souhaite vous faire profiter d’un petit projet personnel que j’avais réalisé en 2006 : un résolveur de sudoku (9×9) en C++. Vous trouverez dans l’archive :

  • les sources,
  • quelques grilles,
  • le fichier de projet Dev-C++.

Les grilles à résoudre sont représentée dans les fichiers par une suite de chiffre qui peuvent être mis en forme (les caractère qui ne sont pas numériques sont ignorés, les zéros représentent les inconnues). Les deux exemples suivants sont deux représentations de la même grille :

  • 907500006006009007001002000
    000004130000000000038090000
    004700200500400800070003605
  • 9 0 7|5 0 0|0 0 6
    0 0 6|0 0 9|0 0 7
    0 0 1|0 0 2|0 0 0
    -----------------
    0 0 0|0 0 4|1 3 0
    0 0 0|0 0 0|0 0 0
    0 3 8|0 9 0|0 0 0
    -----------------
    0 0 4|7 0 0|2 0 0
    5 0 0|4 0 0|8 0 0
    0 7 0|0 0 3|6 0 5

Je sais qu’il existe déjà plein de résolveurs sur le Web mais celui là, il pense comme moi 🙂 : il applique mes méthodes de résolutions et il se trouve bloqué au mêmes endroits que moi sur les grilles complexes…

Télécharger le résolveur (version 0.0.1)

Creative Commons GNU GPL

Programme sous Creative Commons GNU GPL

Taquin

Résolveur de taquin

1 réponse

Je ne sais pas si quand vous vous lancez dans une énigme et que vous ne trouvez pas la solution, vous finissez par juste vouloir la réponse pour passer à autre chose. Ce fût mon cas récemment avec : l’énigme 135 du jeu Professeur Layton et l’étrange village sur Nintendo DS.

Quand je suis bloqué comme ça, j’aime pas non plus qu’on me donne la solution bêtement. Je préfère un compromis (un peu geek certe) : faire un programme qui va résoudre l’énigme à ma place.

Solution

Pour ceux qui viennent de Google et qui en ont rien à faire de mon code, la liste des étapes pour résoudre l’énigme est là :

Solution énigme 135

Pour comprendre la représentation du taquin :

Énigme 135

 <-> 
<><>@
12^@
34v@
<><>@

Code

Pour ceux qui sont intéressés par comment j’ai fait, voici une brève explication :

  1. Il y a trois listes importantes : celle des taquins générés, celle des taquins à explorer et celle des taquin qui sont dans la position finale (juste avant la sortie).
  2. On insère la position de départ dans les listes.
  3. On explore : c’est à dire qu’on génère tous les taquins possibles à partir d’un autre.
  4. Les nouveaux taquins ne doivent pas correspondre à  un autre déjà existant. Si ce n’est pas le cas, on ajoute le nouveau à la liste des taquins trouvés et à celle à explorer.
  5. Si certains sont en position finale on les ajoute à la liste de taquins finaux.
  6. Si il y a un taquin (ou plus) dans la liste à explorer, on prend le premier et on retourne à l’étape 3.
  7. Quand il n’y a plus rien à explorer, c’est qu’on a fait le tour des possibilités de mouvements. On prend le premier des finaux et on affiches les étapes qui ont conduit à sa création.

Défauts du scripts :

  • La représentation du taquin est un tableau de caractère ce qui n’est pas très propre mais ça marche.
  • La méthode n’est pas très intelligente, c’est du brute force qui tâche mais pour une fois j’ai fait un brute en itératif et non en récursif.
  • Les solutions ne sont pas forcement les plus courtes.

Pour le dernier point, j’essairai d’y remédier si j’en ai la motivation car ça va prendre du temps (pour rien, ça on peut le dire).

Voici la source du programme, c’est du python.

enigme-135.py

Creative Commons GNU GPL

Programme sous Creative Commons GNU GPL