Discussion :

[mrhinn]

Bonjour,

Voici une petite Macro que j'ai réalisé pour résoudre les Sudoku.
Pour information, je ne suis pas codeur professionnel, mais plutôt consultant en BI. Je suis donc désolé si mon code ne suit pas l'ensemble des règles d'usages et je serais particulièrement intéressé par toute critique constructive.

Note: je n'ai testé que sur Excel 2010, mais normalement pas de problème de compatibilité

Comment cela fonctionne-t-il? Je vous propose de vous expliquer ma démarche:
(j'éditerai le poste au fur et à mesure pour vous expliquer bien tout en détail si cela intéresse du monde, pour aujourd'hui je donne qu'un rapide aperçu par faute de temps)

1) Création des fonctions de base

Au sudoku vous disposez d'une grille de 9 cases sur 9 cases. Notre algorithme va déterminer dans chaque case non rempli un ensemble de valeurs possibles et à chaque itération, en éliminer jusqu'à ce qu'il n'y ai plus qu'une seule valeur

Pour simplifier le problème, je propose d'utiliser un langage pseudo-binaire pour représenter les valeurs possibles d'une case.
Une case à une valeur binaire sur 9 caractères. Pour chacun de ces caractères, si la valeur est égale à 1, c'est que le chiffre correspondant à cette position et possible, sinon c'est qu'il est impossible.
Par exemple,
Si les chiffres 2 et 4 sont possibles, la valeur de la case sera 000001010
Si seul le 9 est possible (la valeur est connue), la valeur de la case sera 100000000

De ce fait, il est très facile de réaliser les fonctions de bases dont nous avons besoin pour réaliser notre sudoku. Voici les fonctions que j'ai écrites:

- isFinal: teste si la valeur d'une case est déterminée. Autrement dit s'il n'y plus qu'une seule possibilité donc que la valeur contient qu'un seul 1.
- binaryInverse: pour tout 1 renvoi 0 et pour tout 0 renvoi 1. Par exemple, si l'on entre 1001, la fonction renvoi 0110.

- keepOnlyCompatible: on lui envoi une case, elle regarde dans une direction (ligne, colonne ou carré) l'ensemble des isFinal et renvoi le binaryInverse.

- La fonction Fill: effectue des itérations de keepOnlyCompatible jusqu'à ce que le jeux soit bloqué

2) On est bloqué, forçons!
Dans la fonction principale, il peut arriver que l'on soit bloqué. Dans ce case, le code va:
- enregistrer la position actuelle
- Prendre une solution au hasard, et tester, jusqu'à voir si on tombe sur une incohérence (dans quel cas on revient à la position enregistrée), si l'on résoud le sudoku, ou si l'on est encore bloqué, dans quel cas il faut enregistrer la position et recommencer à prendre une solution au hasard.

J'espère que mon code vous plaira! Vous trouverez dans le deuxième onglet un sudoku très difficile que mon code résout en environ 30 secondes.

Bonne journée à vous,

mrhinn