Sudoku Killer

Bonjour

Des sudokus classiques que j'ai su résoudre avec Excel, je suis passé aux sudokus « Killer ».

Les règles du Sudoku s'appliquent (grille de 9x9, avec chiffres de 1 à 9 dans chaque ligne, colonne ou zone).

Mais au lieu de donner des chiffres dans certaines cases, la grille de Killer définit des « formes » (une 30taine par grille). Ces formes sont délimitées par des pointillés (ou des couleurs). Elles sont composées de plusieurs cases et un nombre indique le total des chiffres dans chaque "formes". Et il ne peut pas y avoir deux fois le même chiffre dans une "forme".

On peut soit chercher à résoudre le problème en passant en revue toutes les permutations possibles jusqu'à trouver la bonne mais c'est très long. Ou on peut prendre en compte les quelques principes qui permettent de résoudre manuellement les grilles les plus simples ce qui limite le nombre de cas à examiner.

Mais je ne suis pas assez bon en programmation pour l'une ou l'autre de ces solutions.

Consentiriez-vous à m’aider à résoudre ce problème ?

Si oui, je pourrais vous adresser par Mail des exemples de grilles de Killer, ainsi que quelques principes à mettre en oeuvre .

Merci par avance.

Marc

grilles donnees amp resultats

Bonjour,

je suis en train de regarder comment t'aider.

Bonjour,

Merci de bien vouloir m'aider.

Je me demande si ce sera possible sur Excel parce qu'avec de 9 chiffres par ligne cela fait déjà 9! (362880) permutations possibles. Alors avec 9 lignes ???

A+. Marc

Bonjour,

il y a en effet beaucoup de possibilités, il faut donc les réduire au maximum par déduction.

voici un premier jet, qui trouve les solutions pour les problèmes "faciles" mais qui doit être complété par des algorithmes de déduction plus avancés. je m'y attèle quand j'ai l'occasion.

230sudoku-killer.xlsm (56.71 Ko)

Bonjour,

Merci pour ta réponse. Malheureusement elle ne fonctionne pas sur mon ordi (voir pièce jointe 1 = capture d'écran après avoir appuyé sur la case "résoudre"). J'ai peut-être un problème avec mon ordi mais lequel ?

Afin de t'aider pour ce que tu appelles "des algorithmes de déduction plus avancés" voici (pièce jointe 2) un fichier word dans lequel j'ai décrit les principes dont je me sert pour résoudre ( ou essayer de résoudre) manuellement les sudoku killer.

Encore merci.

Marc

piece 1 execution impossible

Bonjour,

screen

c'est très possible, en effet ! (et j'ai même pas eu besoin d'utiliser ma boule de cristal ! )

dhany

Bonjour Dhany,

En effet je n'avais qu' activer les macros mais je ne m'en était pas servi jusqu'ici.

Merci

Marc

merci pour ton retour ! bonne continuation pour la suite de ce sudoku !

dhany

Bonjour,

Pour ton problème, voir la réponse de Dhany (que je salue bien bas !)

sinon voici une nouvelle version, qui trouve la solution dans un temps acceptable.

Bravo H2 SO4,

J'ai essayé avec une grille marquée "56 mn" et ça a fonctionné en 3-4 mn maxi seulement. Je peux donc considérer mon pb comme résolu,

Mais là je joue un peu le perfectionniste si ce n’est l’utopiste, j’ai toutefois deux remarques à formuler :

1) Pendant la recherche de la solution j'ai observé que l'ordinateur examinait des propositions impossibles soit du fait de la composition et/ou du total dans la forme, soit du fait d'un chiffre déjà présent dans la ligne ou la colonne ou la zone considérée. Il y a peut-être qqchose à faire pour accélérer la recherche. Mais peut-être est-il préférable (+ rapide) de laissé faire l'ordi sans trop se poser la question "je vais essayer le chiffre X, mais X est-il encore possible ?"

2) Les 3-4 mn ne prennent pas en compte le temps de saisie des données de la grille. Ta solution impose, pour une forme à n cases, de répéter n fois le total dans chaque case. J'étais parti (sans y parvenir il est vrai !) avec "Microsoft Small Basic. Pour chaque forme J'aurais voulu pouvoir cliquer sur une couleur, indiquer une seule fois le total puis, avec la souri, aller cliquer sur les cases qui composent la forme, en donnant comme instruction à l’ordi

  • de colorier les cases sélectionnées dans la couleur en question,
  • d’affecter à ces cases le total donné,
  • d’éliminer automatiquement des chiffres possibles à l’origine (1,2,3,4,5,6,7,8,9), les « impossibles » du fait de la composition et/ou du total dans la forme.
Mais en tous cas, que tu cherches à améliorer la solution ou pas, merci beaucoup pour celle que tu m’as apportée.

Marc

Bonjour,

concernant ta remarque 1)

voici ce que le programme fait

a) il détermine bien pour chaque cellule les valeurs possibles en fonction de la somme à obtenir.

b)ajuste la grille en fonction des valeurs uniques ou exclusives dans un groupe (ligne, colonne, carré)

c)ajuste la grille si un groupe de 2 ou 3 valeurs d'un carré se trouvent sur la même ligne ou même colonne

recommence à 1 tant qu'il y a des ajustements

d) fait des hypothèses en essayant des valeurs possibles et recommence à 1 jusqu'à ce qu'une solution soit trouvée ou que toutes les hypothèses possibles aient été examinées.

dans ces cas de figure, il n'y a pas d'examen d'hypothèses basées sur des valeurs impossibles.

l'algorithme ne fait pas de déduction sur la valeurs possibles en examinant les valeurs de 2 ou plusieurs zones.

l'algorithme ne fait pas de déduction de type Xwing, Swordfish, Chained value et autres...

l'algorithme de détection de valeurs uniques ou exclusives est limité.

L'algorithme de sélection des cellules candidates pour une hypothèse a été revu et est beaucoup plus performant

Concernant ta remarque 2)

j'ai implémenté une solution qui devrait rendre la saisie moins longue. Tout en gardant la présentation que le programme souhaite. La valeur précédemment introduite est automatiquement copiée dans la nouvelle cellule sélectionnée, si on change la valeur copiée, celle-ci devient la nouvelle valeur qui sera copiée.

Bonjour H2 SO4,

Cette fois ça a l’air vraiment super ! Je n’en attendais pas autant de toi.

Si tu en est d'accord, on peut donc considérer le problème « Sudoku Killer » comme résolu.

La dernière chose que je voudrais te demander et après, c’est promis, je ne t’embêterai plus : Je désire vraiment me perfectionner en programmation VBA pour Excel afin, à mon tour, d’être capable de créer mes macros personnelles. Sur internet j’ai trouvé de nombreux livres qui traitent du sujet mais je ne sais pas quel livre acheter. Peut-être peux-tu me conseiller un (ou 2) ouvrages pour m’initier aux macros de présentation, de sélection de cases, d’introduction de fonctions (if, or, for, …).

Encore merci.

Marc

Bonjour,

je pense que tu peux trouver ton bonheur en ligne, sur ce site par exemple ou encore silky road pour ne citer que ces deux-là.

Si tu veux vraiment un livre, moi j'ai appris avec le livre "programmation excel avec VBA" de M.Bidault. Il y en a plein d'autres qui sont apparus depuis, que je n'ai pas lus et que je ne peux donc juger.

Bonsoir

Ça y est le livre est commandé. La version « Kindle » est moins chère mais je suis de la vieille école (72 ans !) et j’ai souvent besoin de lire 1 fois ou 2 (ou +) pour comprendre.

Merci

Re-Bonjour,

Excuse moi de te re-déranger....

Pour résoudre un Killer j'ai rentré la grille. Puis, juste après avoir cliqué sur "résoudre" le message "erreur d'exécution 9 - L'indice n'appartient pas la sélection" est apparu. Puis en appuyant sur "débogage" une ligne du programme est apparu sur fond jaune (voir pièce jointe). J'ai dû faire une mauvaise manip mais laquelle ?

Il me semble que l'exécution de programme s'arrête lorsqu'il arrive à la case "10a" qu'il ne reconnait pas ?

Peux-tu arranger ça svp ? Merci d'avance.

Marc

PS : J'ai reçu l'ouvrage "programmation Excel avec VBA". J'ai encore beaucoup à apprendre.

killer erreur 9

Bonjour,

je regarde dès que j'ai l'occasion.

Bonjour,

Comme j'ai observé que ton programme commence à encadrer les formes en partant du haut vers le bas, j'ai eu l'idée d’inverser la même grille (haut en bas) et de rentrer les totaux. En appuyant sur "résoudre" on voit l’entourage des formes se passe bien (y compris pour les 10 et 10a). En fait le programme bloque à la formée "43 en 8 cases" (voir pièce jointe). C'est peut-être là le problème.

Cet aprs-midi je vais essayer de diviser cette forme en deux parties (par ex une forme de total 15 en 4 et une autre de 28 en 4) et voir ce qui se passe.

A+ Marc

grille 6278 haut en bas

Bonjour,

Le problème est dû à une limite qui est atteinte. je ne m'attendais pas à avoir des zones de somme de 8 cases et plus.

Voici une nouvelle version (zone de 12 cases max)

nouvelle version

Rechercher des sujets similaires à "sudoku killer"