Poster un nouveau sujet Poster une réponse
Solveur de sudoku.
Auteur Message
ld
Avatar

Autorisation : Membre
Nb de messages : 373
Inscrit le : Jeu 23 Sep 2010, 16:05
Posté le : Jeu 21 Mar 2013, 11:32   Citer 

Poste réédité

Salut tout le monde...
Après les générateurs et les vérificateurs de sudoku, voici le solveur.
Pour la solution entrez votre grille 9x9 dans la matrice A et lancez le prgm !

Solveur de sudoku 284 octets.

Code
:{0,1,2,0,1,2,0,1,2->L1
:10->dim(L2
:0->S
:While S=/=405

:For(Y,1,9
:For(X,1,9
:If non([A](Y,X:Then:

:Remplir(1,L2

:For(A,1,9                 
:0->L2(1+[A](Y,A
:0->L2(1+[A](A,X
:End

:For(A,X-L1(X),X+2-L1(X     //Incrément facultatif   ),1+(1=L1(X
:For(B,Y-L1(Y),Y+2-L1(Y     // Idm                   ),1+(1=L1(Y
:0->L2(1+[A](B,A
:End:End

:If 1=somme(L2
:max(L2suite(A,A,0,9->[A](Y,X

:End
:End:End

:Matr>Liste([A],LA,LB,LC,LD,LE,LF,LG,LH,LI
:somme(LA+LB+LC+LD+LE+LF+LG+LH+LI->S

:End
:EffListe L1,L2
:Pause [A]



----------------------
Note Éphéméride Chrono Bombrman BlueFishEncryptor Labygénérateur Nord BandeauDeTexte LunarPhase Syracuse Papy-Jump Convertisseur ! SolveurDeSudoku VérificateurDeCodesBanquaire PrgmADiviser CryptageDeVigenere MiniSolv Reed-Solomon Code128Géodésie
 Adresse email Haut de page Bas de page 
 
linkakro



Autorisation : Membre
Nb de messages : 3767
Inscrit le : Lun 19 Oct 2009, 21:25
Posté le : Jeu 21 Mar 2013, 17:00   Citer 

Intéressant. happy.gif
Il semble cribler les lignes/colones/zones pour détecter les cas uniques de certaines cases. Correct ?

Je préfèrerais utiliser un test plutôt que ta liste L1 et la case L2(1) pour gérer le balayage des zones.
A moins que L2(1) serve à autre chose que je ne vois pas.
Mais je ne comprend pas suffisamment son fonctionnement.

Il manque un EffVar.
J'enlèverais bien la ligne entière pour ne pas perturber l'éditeur de stat.
A la limite j'utiliserais "EffListe L1,L2".

Tu peux placer L1 dans Rép sans avoir à stocker. C'est possible uniquement car TI calcule une seule fois les arguments des For.
EDIT: Oubliez, ce sera plus lent d'interpréter du code brut et de le mettre dans Rép que de lire dans la mémoire.


EDIT 23/3: Le code "While non(min([A]" est faux. Désolé.

Voici ce que j'obtien :
Code
:{0,2,-1,1,-2,0,0,2,-1,1,-2,0,0,2,-1,1,-2,0->L1
:10->dim(L2
:EffVar S
:While non(min([A]   // détecte qu'une case au moins est nulle // EDIT : FAUX

:For(Y,1,9
:For(X,1,9
:If non([A](Y,X:Then:

:Remplir(1,L2

:For(A,1,9
:0->L2(1+[A](Y,A
:0->L2(1+[A](A,X
:End

:For(A,X+L1(2X-1),X+L1(2X // j'ai du mal à comprendre ceci et L2(1)
:For(B,Y+L1(2Y-1),Y+L1(2Y // trop de valeurs pour moi ^^
:0->L2(1+[A](B,A
:End:End

:If 1=somme(L2
:max(L2suite(A,A,0,9->[A](Y,X  // je ne suis pas parfaitement sûr

:End
:End:End

:End
:EffVar L1EffVar L2  //manquait un EffVar // remplaçable par EffListe L1,L2
:Pause [A]


Cependant je crois que cet algorithme n'est pas toujours suffisant.
Même sans utiliser d'algorithme plus puissant, je couplerai cette boucle avec un crible plus lourd à utiliser si la boucle actuelle ne suffit pas. (détecter lorsque deux boucles du while S=/=405 n'ont pas obtenu de différence de tableau)

----------------------
ti82statfr: 2008, inscrit: 2009, ti84pocketfr: noël2011, ti30xbmultiview: iut 2012-2014
Perfectionniste, manque tact. Pas le temps de tout publier depuis 2011. Répond toujours aux questions. (rédigé juin 2014)

Pour tout le monde et surtout les débutants, quelques-uns des articles courants :
*Traductions Algorithmie/Ti-Basic.
*Caractères spéciaux sur Tout82
Les défauts du TI-Basic : Goto_versus_algo et DelVar/End/Lbl/guillemet/store
 Adresse email Haut de page Bas de page 
 
ld
Avatar

Autorisation : Membre
Nb de messages : 373
Inscrit le : Jeu 23 Sep 2010, 16:05
Posté le : Jeu 21 Mar 2013, 22:35   Citer 

Super ! Merci happy.gif
Je note, je vais tergiverser tout çà...

"While non(min([A]" Cà j'aime beaucoup, je vais sûrement garder.

Pour : ":For(A,X+L1(2X-1),X+L1(2X" Je compte y mettre un incrément pour certaines
:For(B,Y+L1(2Y-1),Y+L1(2Y conditions.

":max(L2suite(A,A,0,9->[A](Y,X" Je ne garderai peut'être pas, je voudrai y intégrer un affichage, çà va coincer à un moment.

Oui je compte "coupler cette boucle avec un crible plus lourd à utiliser si la boucle actuelle ne suffit pas." En effet ce prgm là ne peut démarrer que si au début au moins une case de la grille n'a qu'une unique solution. Ce qui n'est pas toujours le cas dans les sudoku les plus difficiles.

Et pourquoi "EffVarL1L2" perturberait l'éditeur de stat ? Je ne connais pas çà ? Cà fonctionne pourtant ?

----------------------
Note Éphéméride Chrono Bombrman BlueFishEncryptor Labygénérateur Nord BandeauDeTexte LunarPhase Syracuse Papy-Jump Convertisseur ! SolveurDeSudoku VérificateurDeCodesBanquaire PrgmADiviser CryptageDeVigenere MiniSolv Reed-Solomon Code128Géodésie
 Adresse email Haut de page Bas de page 
 
linkakro



Autorisation : Membre
Nb de messages : 3767
Inscrit le : Lun 19 Oct 2009, 21:25
Posté le : Jeu 21 Mar 2013, 23:11   Citer 

Je me suis mal exprimmé, le EffVar manquant et la perturbation du menu stat\edit sont indépendants. (j'ai édité la phrase du message précédent)

"EffVar L1L2" efface la liste L1 et ne fait strictement rien à L2. L2 est juste lue et stockée dans Rép.
Il faut un EffVar par variable. "EffVar L1EffVar L2".

EffVar supprimme une liste alors que EffListe vide son contenu.
Supprimmer une liste provoque sa disparition du menu stat\edit, l'éditeur de listes. Or je me sers souvent de cet éditeur.
D'autre part une liste vide peut être plus facilement manipulée par certaines actions qu'une liste qui n'existe pas du tout. (on peut tester sa dimension même nulle à partir de la ti83plus par exemple)

Cependant le statut des 6 listes de base est particulier : elles étaient à l'origine des variables système de la ti82basique , et donner une dimension à une de ces listes après suppression conserve des données qui auraient dû disparaître lors de la suppression.
Ces 6 listes n'apparaisent d'ailleurs pas dans le menu liste avant la ti83plus.

----------------------
ti82statfr: 2008, inscrit: 2009, ti84pocketfr: noël2011, ti30xbmultiview: iut 2012-2014
Perfectionniste, manque tact. Pas le temps de tout publier depuis 2011. Répond toujours aux questions. (rédigé juin 2014)

Pour tout le monde et surtout les débutants, quelques-uns des articles courants :
*Traductions Algorithmie/Ti-Basic.
*Caractères spéciaux sur Tout82
Les défauts du TI-Basic : Goto_versus_algo et DelVar/End/Lbl/guillemet/store
 Adresse email Haut de page Bas de page 
 
ld
Avatar

Autorisation : Membre
Nb de messages : 373
Inscrit le : Jeu 23 Sep 2010, 16:05
Posté le : Sam 23 Mar 2013, 13:50   Citer 

Voici ce qui a été simplifier :

Code
:{0,1,2,0,1,2,0,1,2->

:If non([A](Y,X:Then:

:For(A,X-L1(X),X+2-L1(X     //Incrément facultatif   ),1+(1=L1(X
:For(B,Y-L1(Y),Y+2-L1(Y     // Idm                   ),1+(1=L1(Y

:max(L2suite(A,A,0,9->[A](Y,X

:EffListe L1,L2


Ton "While non(min([A]" ne fonctionne pas Linkakro car "min([A]" n'existe pas, bien dommage...

----------------------
Note Éphéméride Chrono Bombrman BlueFishEncryptor Labygénérateur Nord BandeauDeTexte LunarPhase Syracuse Papy-Jump Convertisseur ! SolveurDeSudoku VérificateurDeCodesBanquaire PrgmADiviser CryptageDeVigenere MiniSolv Reed-Solomon Code128Géodésie
 Adresse email Haut de page Bas de page 
 
linkakro



Autorisation : Membre
Nb de messages : 3767
Inscrit le : Lun 19 Oct 2009, 21:25
Posté le : Sam 23 Mar 2013, 14:37   Citer 

Effectivement. Cela ne marche sur aucune des z80 à ma disposition. (de 82 à 84pocket) . Je croyais avoir testé. Soit je suis étourdi soit j'avais mal effectué mon test. minied.gif

----------------------
ti82statfr: 2008, inscrit: 2009, ti84pocketfr: noël2011, ti30xbmultiview: iut 2012-2014
Perfectionniste, manque tact. Pas le temps de tout publier depuis 2011. Répond toujours aux questions. (rédigé juin 2014)

Pour tout le monde et surtout les débutants, quelques-uns des articles courants :
*Traductions Algorithmie/Ti-Basic.
*Caractères spéciaux sur Tout82
Les défauts du TI-Basic : Goto_versus_algo et DelVar/End/Lbl/guillemet/store
 Adresse email Haut de page Bas de page 
 
ld
Avatar

Autorisation : Membre
Nb de messages : 373
Inscrit le : Jeu 23 Sep 2010, 16:05
Posté le : Sam 23 Mar 2013, 17:33   Citer 

Faites gaffe tout le monde ! Il y a notre Linkakro qui refile des tuyaux percés !
LOL, merci quand même winkle.gif
Pour ce qui est de : je cite : "coupler cette boucle avec un crible plus lourd à utiliser si la boucle actuelle ne suffit pas." J'ai voulu essayer, et oui, çà va être du lourd...

----------------------
Note Éphéméride Chrono Bombrman BlueFishEncryptor Labygénérateur Nord BandeauDeTexte LunarPhase Syracuse Papy-Jump Convertisseur ! SolveurDeSudoku VérificateurDeCodesBanquaire PrgmADiviser CryptageDeVigenere MiniSolv Reed-Solomon Code128Géodésie
 Adresse email Haut de page Bas de page 
 
Poster un nouveau sujet Poster une réponse





  Powered by Fire-Soft-Board v1.0.10 © 2004 - 2024 Groupe FSB
Page générée en 9 requêtes
BlackOne par Grimmlink