Autorisation : Membre
Nb de messages : 3293
Inscrit le : Sam 31 Déc 2005, 19:48
Posté le : Ven 22 Jui 2012, 15:08
Bonjour, ça fait longtemps (mais alors vraiment très longtemps) que je n'avais pas fait de programme.
Puis ce matin en surfant sur le net, j'ai eu la curiosité de voir comment générer des grilles de sudoku et j'ai découvert les joies de la permutation. Du coup, j'ai refait un générateur de grille (le premier datant d'il y a 4 ou 5 ans) et comme j'ai pas du tout de calto sous la mains, je vous met le code ici afin que vous le testiez et que vous m'indiquiez si la vitessse d'exécution est correcte et pas de bourde dans le code.
Code
ClrDraw
0->Xmin
0->Ymin
94->Xmax
62->Ymax
[[3,6,9,4,5,8,1,2,7][7,5,2,9,6,1,8,4,3][1,4,8,2,3,7,5,6,9][4,8,7,3,9,6,2,1,5][5,9,1,8,7,2,6,3,4][2,3,6,1,4,5,7,9,8][9,7,5,6,2,4,3,8,1][8,2,3,7,1,9,4,5,6][6,1,4,5,8,3,9,7,2->[A]
for(A,1,100
3int(rand 3->B
int(rand 3+1->C
int(rand 3+1->D
int(rand 4->E
if E>2
t[A]->[A] ← le t est le symbole de la transposée
for(F,0,2(E=2 or E=4
rowswap([A],F+B+C,F+B+D->[A]
end
if E>2
t[A]->[A]
end
pi/2*int(rand4->A
{9,9->dim([B]
for(B,1,9
for(C,1,9
[[B-5,0][0,C-5]][cos(A),sin(A)][-sin(A),cos(A
[A](5+ans(2,1),5+ans(1,2->[B](B,C
end
end
[B]->[A]
DelVar [B] DelVar C
lbl 0
for(A,1,9
for(B,1,9
text(-4+3int((A-1)/3)+5A,-4+3int((B-1)/3)+5A,[A](A,B
end
for(A,1,3
horizontal 1+15A
vertical 1+15A
end
if Z=1
Stop
pause
for(A,1,50
lbl 1
int(rand 9+1->B
int(rand 9+1->C
if non([A](B,C
goto 1
0->[A](B,C
end
goto 0
D'ailleurs, vers la fin d"e mon programme lorsque je fait tourner ma matrice, j'utilise une matrice de rotation 2*2 pour déterminer les nouvelles coordonnées et pour cela, je créer une autre matrice donc si vous avez une méthode moins gourmande en place, je suis preneur.
Autorisation : Membre
Nb de messages : 3293
Inscrit le : Sam 31 Déc 2005, 19:48
Posté le : Ven 22 Jui 2012, 15:17
Le principe de ce générateur c'est qu'en inversant des lignes et colonnes, tu obtient toujours une grille valide. Pour cela, il faut qu'elles fassent partie de la même cellule (les carrés en gras)
Cela fait (il parait car j'arrive pas à autant de termes) 6*6*6 possibilités.
Après, on permute les lignes/colonnes 3 par 3 ce qui ne change toujours pas la validité de la grille donc on multiplie par 6*6 le résultat précédent.
Enfin, on fait tourner la matrice pour rajouter encore des possibilités (3 fois plus).
Et parce que c'est fun, j'ai repris le concept de mon premier générateur de mettre du blanc sur le cases (ou juste en afficher certaines s'pareil). aléatoirement donnant l'illusion d'une nouvelle grille si jamais on refait la même.
Autorisation : Membre
Nb de messages : 3738
Inscrit le : Lun 19 Oct 2009, 21:25
Posté le : Ven 22 Jui 2012, 19:44
Alors là tu me blouses !
C'est vraiment malin de permuter des zones d'une matrice déjà écrite !
Bon retour parmi nous alors !
J'ai bien l'intention de tester ton programme, et éventuellement de tenter d'en écrire une variante.
---------------------- 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)
Autorisation : Membre
Nb de messages : 3293
Inscrit le : Sam 31 Déc 2005, 19:48
Posté le : Ven 22 Jui 2012, 20:41
L'idée n'est pas de moi mais trouvée sur un blog. Et du coup c'est vrai que ça permet beaucoup de possibilités.
Quelles sont les valeurs de F+B+C et F+B+D? Normalement ce sont des nombres compris entre 1 et 9.
Autorisation : Membre
Nb de messages : 3293
Inscrit le : Sam 31 Déc 2005, 19:48
Posté le : Sam 23 Jui 2012, 18:47
Quelles sont les valeurs de F,B,C et D. Si je ne me plante pas, elles sont de 0,9,1 et 1. Du coup, je pense qu'il faut modifier le rand de B de la façon suivante:
Code
3int(rand2->B
Le but étant que B aient pour valeurs possible 0,3 et 6.
Autorisation : Membre
Nb de messages : 177
Inscrit le : Dim 27 Mai 2012, 20:38
Posté le : Sam 23 Jui 2012, 18:55
En fait, les valeurs varient à chaque fois.
Le programme s'arrête quand F+B+C=10 ou F+B+D=10 et en refaisant plusieurs essais, je me suis rendu compte que parfois seul un des deux était égal à 10.
Je pense pas que ta ligne résolve le problème du coup parce que j'ai déjà eu cette erreur avec B=6.
Je viens d'essayer avec ta modification et maintenant ça me met erreur syntaxe ici :
Code
[[B-5,0][0,C-5]][cos(A),sin(A)"]"[-sin(A),cos(A
Sur le crochet que j'ai mis entre guillemets (non je n'ai pas mis les guillemets dans le programme )
---------------------- Il y a 10 types de personnes dans le monde : celles qui comprennent le binaire et celles qui ne le comprennent pas.
Autorisation : Membre
Nb de messages : 3738
Inscrit le : Lun 19 Oct 2009, 21:25
Posté le : Sam 23 Jui 2012, 19:58
Ajoute un crochet ouvrant après le sixième.
Dans une TI le "t" de transposée est à droite de la matrice contrairement aux mathématiques.
Si les aléatoires bugguent et que vous êtes sur 82stat, vous pouvez utiliser randInt(), c'est plus simple.
Pour l'instant je recopie scrupuleusement, ainsi je ne créerai pas de bug supplémentaires.
Le problème de int(randA) est que le nombre sera entre 0 et A-1.
Donc il faut écrire int(5randüE pour avoir entre 0 et 4
EDIT : ou bien 1+int(4randüE pour avoir entre 1 et 4
Tu effectues des transposées pour mélanger les colonnes, mais tu pourrais effectuer des transposées en tant que manipulation en elle-même ! En effet cela ne change pas les propriétés du sudoku.
Le programme me semble faux au niveau du rowSwap().
Pour commencer, mon test bug à ce niveau, ensuite je ne parviens pas à comprendre le lien entre les aléatoires et la permutation.
---------------------- 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)
Autorisation : Membre
Nb de messages : 177
Inscrit le : Dim 27 Mai 2012, 20:38
Posté le : Sam 23 Jui 2012, 23:49
Ah mon avis on doit pouvoir faire des choses vraiment "élaborés" avec mais il faut faire des études poussées en mathématiques (je sais même pas si en maths sup et maths spé on voit toutes les applications...). Wikipédia le confirme d'ailleurs et là ça me rend totalement
---------------------- Il y a 10 types de personnes dans le monde : celles qui comprennent le binaire et celles qui ne le comprennent pas.
Autorisation : Membre
Nb de messages : 3738
Inscrit le : Lun 19 Oct 2009, 21:25
Posté le : Dim 24 Jui 2012, 0:07
Rassure toi les matrices ne servent pas seulement à résoudre des systèmes linéaires aussi classiques que ce à quoi tu penses.
Je peux dériver des polynomes si tu veux avec une matrice.
Une matrice représente une famille de vecteurs (pas forcément géométriques ), et pratiquer des opérations entre ces marices permet de représenter toutes les applications linéaires et d'en déduire des équations, ou le contraire, et enfin de les résoudre.
De plus ces vecteurs sont exprimés dans diverses bases (comme un repère en géométrie), et changer de base peut simplifier un problème du tout au tout.
Histoire de devenir définitivement aliéné, citons les équations différentielles matricielles complexes utilisées en physique quantique.
---------------------- 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)
Autorisation : Membre
Nb de messages : 3738
Inscrit le : Lun 19 Oct 2009, 21:25
Posté le : Dim 24 Jui 2012, 0:20
Oui pardon j'était en transe. Moi cela m'émerveille de découvrir des choses et de pouvoir les raconter.
J'ai quand même dit des choses simplement.
Je me casse toujours les dents sur le programme de sangohan38.
Le problème semble ne pas venir de la génération des aléatoires mais de leur exploitation par rowSwap().
---------------------- 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)
Autorisation : Membre
Nb de messages : 177
Inscrit le : Dim 27 Mai 2012, 20:38
Posté le : Dim 24 Jui 2012, 0:32
Bah en même temps, faut se dire que ça fait environ 30000 ans que l'homme existe, donc depuis ce temps on a quand même réussi à élaborer des choses pas mal et des théories mathématiques improbables
Citer
Moi cela m'émerveille de découvrir des choses et de pouvoir les raconter.
T'inquiète pas, je crois que c'est normal chez tous ceux qui ont fait ou qui sont en prépa : j'en connais dès que tu dis un mot quasiment ils te donnent une anecdote dessus... On se sent un peu con à côté
Sinon pour le programme de Shanogan38, j'ai réussi à le faire fonctionner avec son astuce et ta correction mais après je tombe sur cet écran :
Il faut que je fasse quoi exactement parce que j'ai pas vu de getKey dans le programme alors je suis un peu perdu
---------------------- Il y a 10 types de personnes dans le monde : celles qui comprennent le binaire et celles qui ne le comprennent pas.
Autorisation : Membre
Nb de messages : 3293
Inscrit le : Sam 31 Déc 2005, 19:48
Posté le : Dim 24 Jui 2012, 16:46
La j'ai juste le générateur. Dans ton screen, tu as vérifié que tout les chiffres de la matrice étaient affichés?
Normalement, tu devrait avoir une première grille complète avant la pause et ensuite la même grille mais avec la moitié de chiffre.
Bon, comme j'ai à nouveau une calto sous la main, j'vais pouvoir le tester mais j'ai trouvé l'exercice intéressant de poser son code sur papier sans savoir si il allait fonctionner.
Autorisation : Membre
Nb de messages : 3738
Inscrit le : Lun 19 Oct 2009, 21:25
Posté le : Mar 26 Jui 2012, 20:36
Il manque un End après le Text.
Je vois deux possibilités incompatibles dans ton objectif avec cette partie :
Code
3int(2rand->B
1+int(3rand->C
1+int(3rand->D
int(5rand->E
If E>2
[A]t->[A]
For(F,0,2(E=2 or E=4
rowSwap([A],F+B+C,F+B+D->[A]
End
End
SOIT F sert à permuter trois paires lignes afin de globalement permuter deux zones, au quel cas il faut corriger B,C,D.
SOIT F sert à permuter à l'intérieur d'une zone au quel cas il faut corriger F et B,C,D d'une autre manière.
---------------------- 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)
Autorisation : Membre
Nb de messages : 3738
Inscrit le : Lun 19 Oct 2009, 21:25
Posté le : Ven 29 Jui 2012, 19:01
UP
J'ai carrément réécrit les instructions de permutations.
Cela ne bug pas et je pense que cela marche maintenant pour les deux aspects présents dans mon précédent message.
J'ai maintenant mieux compris comment fonctionnent les instructions de rotation, mais je ne comprends pas tout et elle me cause des bugs comme celui signalé par F-BVXT.
J'envisage d'effectuer des symétries axiales. C'est facile, il faut seulement effectuer un produit matriciel (à droite ou à gauche) par la matrice symétrique par rapport à l'identité. (une diagonale de 1 depuis en bas à gauche jusqu'en haut à droite)
---------------------- 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)
DelVar [C] // génère la future matrice de symétrie
{9,9->dim([C]
For(W,1,9
1->[C](10-W,W
End
For(A,1,100
Repeat D-E and B-C // génère les aléatoires nécessaires aux rowSwap
3int(2rand->B
3int(2rand->C
1+int(3rand->D
1+int(3rand->E
3int(2rand->G
End
If int(2rand // transposition
[A]t->[A]
rowSwap([A],G+D,G+E->[A] // permutation de lignes/colonnes selon transposition
If int(2rand
[A]t->[A]
For(F,1,3
rowSwap([A],B+F,C+F->[A] // permutation de zones
End
If int(2rand // symétrie verticale
[A][C]->[A]
If int(2rand
[C][A]->[A] // symétrie horizontale
For(W,1,int(rand4 // rotation globale
[C][A]t->[A] // rotation élémentaire positive
End
End
DelVar Z
Lbl 0
For(A,1,9
For(B,1,9
Text(6A-6+2int((A-1)/3),4B-4+2int((B-1)/3),[A](A,B
End
End
For(A,1,3
Horizontal 63-20A
Vertical 14A-2
End
If Z=1
Stop
1->Z
Pause
For(A,1,50
Repeat [A](B,C
int(9rand+1->B
int(9rand+1->C
End
0->[A](B,C
End
Goto 0
Remarque : pour effectuer une rotation sans produit matriciel, il fallait corriger la procédure avec une de ces options :
Code
[A]->[B]
pi/2*int(rand4->A
If A
Then
For(B,1,9
For(C,1,9
[[cos(A),sin(A)][-sin(A),cos(A]][[B-5][C-5
[B](5+Ans(1,1),5+Ans(2,1->[A](B,C
End
End
DelVar [B]DelVar C
End
Code
[A]->[B]
int(rand4->A
If A
Then
For(B,1,9
For(C,1,9
[[0,1][-1,0]]^A[[B-5][C-5
[B](5+Ans(1,1),5+Ans(2,1->[A](B,C
End
End
DelVar [B]DelVar C
End
Objectifs éventuels d'amélioration du concept :
-variété des enchaînements des opérations
-nouvelles opérations
-imbrication d'opérations ayant des éléments identiques (par exemple la rotation élémentaire est composée d'une transposition puis d'une symétrie ou le contraire)
Autres objectifs éventuels :
-optimiser le codage de chaque instruction (ça c'est évident )
-gestion des cases à cacher pour obtenir une grille de jeu parfaite
(une grille de jeu parfaite mène à une unique grille solution)
(pour le faire, je pense qu'il faut suivre un des modèles ci-dessous)
Remarque : il existe probablement plusieurs grilles parfaites de jeu aboutissant à une même solution.
Idée possible d'opération : permuter deux groupes de chiffres (tous les 1 deviennet 2 et tous les 2 deviennent 1 par exemple), mais attention à ne pas permuter les références de cases à cacher.
Remarque: cela ne change pas le comportement de la grille mais donne illusion d'un changement. Ainsi j'appellerai "transformation" toutes les autres opérations
Ma première vision du générateur parfait :
-prendre une grille solution et une grille de jeu (parfaite) qui aboutit à celle-ci
-différencier sur la grille de jeu les cases qui devront être cachées et celles qui devront être montrées, avec des zéros et des uns par exemple. La grille obtenue pourra être appelée "grille de cache".
-pratiquer une même série d'opérations de transformation sur les deux grilles
-pratiquer une permutation de deux groupes de chiffres sans modifier la grille de cache
-remplacer les 1 (si on a choisit 1 pour repérer les cases à montrer) par les chiffres présents aux mêmes emplacements dans la grille solution
Ma deuxième vision du générateur parfait :
-prendre une grille de jeu parfaite (on pourra associer le chiffre 0 à chaque case cachée)
-pratiquer la série d'opérations de transformation
-pratiquer une permutation de deux groupes de chiffres parmi les cases visibles
La plus grande difficulté pour générer une grille de sudoku est la variété des manières de cacher des cases sans rendre impossible la résolution avec une unique solution.
C'est l'aspect qui manque à notre aproche.
---------------------- 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)
Autorisation : Membre
Nb de messages : 3738
Inscrit le : Lun 19 Oct 2009, 21:25
Posté le : Lun 16 Juil 2012, 18:52
Certes, il est possible que la présence d'un certain nombre d'indices permette systématiquement de résoudre la grille avec une unique solution. Je ne sais ni le prouver ni l'infirmer.
Cependant je sais qu'il est possible d'avoir plusieurs solutions dans des situations que je ne saurai pas définir, sachant que j'ai déjà vu un solveur de sudoku (celui de ma mère ) trouver deux solutions pour une même grille.
Si vous avez des idées à proposer pour aller plus loin, ne vous gènez pas, surtout s'il s'agit de nouvelles opérations ou d'une optimisation.
PS: moi je suis très fier de la rotation matricielle que j'ai trouvé par hasard après avoir manipulé plusieurs systèmes d'équation qui n'aboutissaient à rien.
---------------------- 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)
Autorisation : Membre
Nb de messages : 3738
Inscrit le : Lun 19 Oct 2009, 21:25
Posté le : Lun 16 Juil 2012, 21:26
J'ai écrit à la mode ti82 pour rester dans le même monde que sangohan38. Cependant :
Code
1+int(3rand // 5 octets
randInt(1,3 // 4 octets
int(2rand // 3 octets
randInt(0,1 // 4 octets
---------------------- 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)
)
Un grand fan de Matrix comme moi ! Un mythe tombe ! /cry
