[Thomson] SUDOKU, nouveau jeu pour MO et TO
Modérateurs : Papy.G, fneck, Carl
Re: [Thomson] SUDOKU, nouveau jeu pour MO et TO
Uhm, ça s'éloigne un peu du post initial de Daniel non ? (même si cela reste intéressant, j'en conviens).
Fan d'ATARI 2600, de THOMSON MO5-TO8 et d'ATARI ST
Mes articles : https://www.fxjavadevblog.fr/retro-programming/
Membre du groupe wide-dot.
Mes articles : https://www.fxjavadevblog.fr/retro-programming/
Membre du groupe wide-dot.
Re: [Thomson] SUDOKU, nouveau jeu pour MO et TO
On peut dire que ça reviendra en plein dans le sujet quand un programmeur portera sur Thomson un algorithme de génération de problèmes de Sudoku.
Je donne une contrainte supplémentaire : maximum 16 Ko, car il faut pouvoir charger en même temps le DOS et le programme pour jouer.
Je donne une contrainte supplémentaire : maximum 16 Ko, car il faut pouvoir charger en même temps le DOS et le programme pour jouer.
Daniel
L'obstacle augmente mon ardeur.
L'obstacle augmente mon ardeur.
-
- Messages : 7987
- Inscription : 18 sept. 2010 12:08
- Localisation : Brest et parfois les Flandres
Re: [Thomson] SUDOKU, nouveau jeu pour MO et TO
Pour les curieux essayez de compiler ceci avec DEBUG à 1. C'est mon algo Lua "findPossibilites1" codé en ASM 6809 hyper optimisé et qui intègre le principe du tableau précalculé (3.4ko) des cases à visiter directement sans avoir à faire les boucles for de la version LUA. [EDIT]: bon ben je sais pas pourquoi, mais le code source complet fait planter le serveur "bad gateway". Aussi utilisez ceci à la place (lien temporaire)
Pour les patients, essayez avec GRID à 17, et pour les impatients, voici le résultat du code ci-dessus:
@Daniel: je pense que l'algo de generation est à portée de main et tiendra dans tes contraintes car l'algo de résolution en lui même fait, sans le debug, seulement 116 octets (j'ai pas mal optimisé) et résout les sudokus que tu utilises en moins d'une seconde sans le debug, et moins de 9secondes avec le debug actif.A noter: pour le GRID=17 c'est en revanche très très lent. Aussi je viens de lancer l'émulateur en mode 64Mhz, mais je me rend compte que le clavier ou le rafraichissement écran est alors extrêmement lent. Est-ce normal ?
Code : Tout sélectionner
(main)SUDOKU
DEBUG SET 0
GRID SET 1
ORG $A000
BRA INI
Code : Tout sélectionner
$ ./c6809.exe -oOP sudoku.ass sudoku.bin
Macro Pass
Pass1
Pass2
START = $A053
SOLVE = $A300
Debug = 1
Grille = 1
Taille Algo = 185
Taille Work = 3404
Taille Stack = 439 bytes
000000 Total Errors
000064 Total Symbols
Code : Tout sélectionner
***************************************
* Algo de resolution
*
* En entree:
* U=routine si sol trouvee
* (retourne Z=1 s'il faut continuer
* la recherche)
*
* En sortie:
* Z=1 si allee jusqu'au bout
* (pas de solution)
* Z=0 sinon
* (solution trouvee)
***************************************
SOLVE
PSHS DP,X,Y,U
LDY #BITCOUNT+128
SETDP POSCNT<-8
LDA #POSCNT<-8 ; utilisation du mode DP pour booster au max
TFR A,DP
STU <SOLFND+1
PULS DP,X,Y,U,PC
* recherche recursive
SOLV0
PSHS B,U
LDB #10 ; majorant
STB <POSCNT+1
* recherche une case vide
LDU #WORK
SOLV1
LDD ,U
LEAU 42,U
BGT SOLV1
BMI SOLV4
LDX ,--U ; calcul des chiffres déjà utilisés
SOLV2
ORA ,X ; c'est un simple or 16 bits
ORB 1,X
LDX ,--U ; qui se termine quand on revient sur
BNE SOLV2 ; la case courante (qui est nulle ==> test gratos)
EORA #1 ; on inverse les bits pour trouver
COMB ; le mask des chiffres possibles
STD <POSMSK+1 ; mask vide ?
BEQ SOLVRET ; oui => termine (pas de soluce)
ADDA B,Y ; nb de bits a 1 (rapide car A=0 ou 1 ici)
POSCNT
CMPA #0 ; meilleure ?
BGT SOLV3
STA <POSCNT+1 ; on sauve le nouveau nb de choix
POSMSK
LDD #0
STD <BSTMSK+1
STU <BSTCEL+1 ; et la case actuelle
SOLV3
LEAU 42,U
BRA SOLV1 ; on passe à la case suivante
* on a fini de trouver la meilleure case possible
SOLV4
LDB <POSCNT+1
SUBB #10
BNE BSTCEL ; il y a eu des cases vides ==> on choisit la meilleure
* la grille est pleine: on a trouvé une solution !
SOLFND
JSR >$1234 ; callback pour continuer (Z=1) ou stopper (Z=0)
PULS B,U,PC
* récup meilleur mask et meilleur case
BSTCEL
LDU #0
BSTMSK
LDD #0
* on essaie toute les possibilités
TSTA ; chiffre 9 possible ?
BEQ SOLV5 ; non ==> on regarde partie basse
STA ,U ; on place 9
BSR SOLV0 ; recherche
BNE SOLVRET ; il faut stopper ?
CLR ,U ; non ==> annulation choix
SOLV5
STB <MSKLOW+1 ; calcul rapide d'un bit a 1
NEGB ; avec la formule (B & -B)
MSKLOW
ANDB #0
STB 1,U ; on fige ce chiffre dans la case
BEQ SOLVRET ; plus de bits ==> fini (pas solution)
EORB <MSKLOW+1 ; effacement du chiffre parmi les possibilités
BSR SOLV0 ; recherche avec cette case figée
BEQ SOLV5 ; Z=1 => on continue
* PAS TROUVE
SOLVRET
PULS B,U,PC
***************************************
* Callback qui stoppe a la 1ere soluce
***************************************
ONESOL
LDB #1 ; on retourne Z=0
RTS
- Pièces jointes
-
- sudoku_solve.zip
- Source et binaire TO à lancer en &HA000 (DEBUG=0, GRID=1)
- (8.1 Kio) Téléchargé 84 fois
Dernière modification par __sam__ le 14 juil. 2021 22:52, modifié 2 fois.
Samuel.
A500 Vampire V2+ ^8^, A1200 (030@50mhz/fpu/64mb/cf 8go),
A500 GVP530(MMU/FPU) h.s., R-Pi, TO9, TO8D, TO8.Démos
A500 Vampire V2+ ^8^, A1200 (030@50mhz/fpu/64mb/cf 8go),
A500 GVP530(MMU/FPU) h.s., R-Pi, TO9, TO8D, TO8.Démos
Re: [Thomson] SUDOKU, nouveau jeu pour MO et TO
Ça va m'inciter à ajouter un mode "triche" dans le programme de sudoku
J'ai essayé avec plusieurs gilles, ça marche bien.
Pour dcmoto à 64M Hz j'ai déjà remarqué le phénomène : quand on augmente la vitesse de façon excessive il arrive un moment où les ressources sont saturées. Je ne sais pas si c'est le processeur, ou la carte graphique, ou la carte son, mais ça provoque une petite panique. Dans les anciennes versions la vitesse était limitée à 10 MHz, il n'y avait pas de problème avec une machine rapide. Aujourd'hui, avec 64 MHz, on atteint les limites. Je vais voir si on peut améliorer en supprimant le son et/ou en affichant l'écran moins souvent.
J'ai essayé avec plusieurs gilles, ça marche bien.
Pour dcmoto à 64M Hz j'ai déjà remarqué le phénomène : quand on augmente la vitesse de façon excessive il arrive un moment où les ressources sont saturées. Je ne sais pas si c'est le processeur, ou la carte graphique, ou la carte son, mais ça provoque une petite panique. Dans les anciennes versions la vitesse était limitée à 10 MHz, il n'y avait pas de problème avec une machine rapide. Aujourd'hui, avec 64 MHz, on atteint les limites. Je vais voir si on peut améliorer en supprimant le son et/ou en affichant l'écran moins souvent.
Daniel
L'obstacle augmente mon ardeur.
L'obstacle augmente mon ardeur.
Re: [Thomson] SUDOKU, nouveau jeu pour MO et TO
Ou limiter à 32Mhz. C'est déjà bien...
-
- Messages : 7987
- Inscription : 18 sept. 2010 12:08
- Localisation : Brest et parfois les Flandres
Re: [Thomson] SUDOKU, nouveau jeu pour MO et TO
Je suis quand même tombé sur quelques bugs pas fondamentaux: 1) la routine de conversion TOSUDOKU n'est pas totalement symétrique de TOWORK.. elle mets le caractère '.' au lieu de '0' ce qui fait que si on stoppe la recherche et qu'on la redémarre depuis ce point on se retrouve à avoir une solution avec que des "9" au lieu d'un "No solution!", et 2) ca bug en sortie de "No solution!" car ce chemin n'éteint pas la routine de timer qui s'occupe du décompte du temps.
- Pièces jointes
-
- sudoku_solve.zip
- (8.35 Kio) Téléchargé 91 fois
Samuel.
A500 Vampire V2+ ^8^, A1200 (030@50mhz/fpu/64mb/cf 8go),
A500 GVP530(MMU/FPU) h.s., R-Pi, TO9, TO8D, TO8.Démos
A500 Vampire V2+ ^8^, A1200 (030@50mhz/fpu/64mb/cf 8go),
A500 GVP530(MMU/FPU) h.s., R-Pi, TO9, TO8D, TO8.Démos
Re: [Thomson] SUDOKU, nouveau jeu pour MO et TO
Avec du retard, Félicitations Daniel
-
- Messages : 7987
- Inscription : 18 sept. 2010 12:08
- Localisation : Brest et parfois les Flandres
Re: [Thomson] SUDOKU, nouveau jeu pour MO et TO
Petit teaser..
Si vous avez l'occasion de jouer avec et trouver que l'algo ne donne pas des vrais Sudoku (eg: pas solvables, ou alors de plusieurs façon) cela m'intéresse [EDIT: je pense qu'il est buggé: il semble qu'il y ait des solutions non uniques au Sudoku trouvé, mais je dois collecter des données pour comprendre d'où ca sort]. Si j'arrive à corriger l'algo et que je suis content du code ASM optimisé je le publierais dans pas trop longtemps j'espère (ainsi qu'une explication de l'algo qui est plus intéressant que le code).
Notes:
Je n'ai pas encore fini de mettre au point, mais ca a l'air de faire des trucs.Si vous avez l'occasion de jouer avec et trouver que l'algo ne donne pas des vrais Sudoku (eg: pas solvables, ou alors de plusieurs façon) cela m'intéresse [EDIT: je pense qu'il est buggé: il semble qu'il y ait des solutions non uniques au Sudoku trouvé, mais je dois collecter des données pour comprendre d'où ca sort]. Si j'arrive à corriger l'algo et que je suis content du code ASM optimisé je le publierais dans pas trop longtemps j'espère (ainsi qu'une explication de l'algo qui est plus intéressant que le code).
Notes:
- Vous pouvez tricher la résolution ici: https://kjell.haxx.se/sudoku/
- sur ce même site ils classent la difficulté en fonction du nombre d'indices:
- 50 indices niveau débutant
- 40 indices niveau facile
- 26 indices niveau difficile
- 17 indices niveau super difficile
- La version actuelle sort des Sudoku avec 23 indices (c'est à dire entre super dur et dur) en moins d'une minute en moyenne. Ils sont résolus en 1sec environ. C'est pas mal pour le petit Thomson. [EDIT: mais si ce ne sont pas des vrais Sudoku avec une seule solution ca n'est pas très significatif.]
- J'arrive à lui faire trouver des sudoku de niveau 17 au bout de 60 000 secondes. C'est super lent (mais c'est logique: il y en a nettement moins que ceux de niveau 26 et ils sont beaucoup plus difficiles à vérifier).
- Pièces jointes
-
- Sudoku_gen.zip
- Le fichier BIN se charge avec LOADM, le RAW se charge directement en &HA000 avec le debuggeur DCMOTO.
- (8.16 Kio) Téléchargé 78 fois
Samuel.
A500 Vampire V2+ ^8^, A1200 (030@50mhz/fpu/64mb/cf 8go),
A500 GVP530(MMU/FPU) h.s., R-Pi, TO9, TO8D, TO8.Démos
A500 Vampire V2+ ^8^, A1200 (030@50mhz/fpu/64mb/cf 8go),
A500 GVP530(MMU/FPU) h.s., R-Pi, TO9, TO8D, TO8.Démos
Re: [Thomson] SUDOKU, nouveau jeu pour MO et TO
Reste à trouver un algorithme pour vérifier l'unicité de la solution...
En attendant je vais faire quelques essais à la main, mais ça risque d'être long et pas exhaustif.
En attendant je vais faire quelques essais à la main, mais ça risque d'être long et pas exhaustif.
Daniel
L'obstacle augmente mon ardeur.
L'obstacle augmente mon ardeur.
-
- Messages : 7987
- Inscription : 18 sept. 2010 12:08
- Localisation : Brest et parfois les Flandres
Re: [Thomson] SUDOKU, nouveau jeu pour MO et TO
Normalement je l'ai sur papier. C'est le codage en ASM, et surtout l'optimisation qui a introduit un BUG que je vais finir par isoler.
[EDIT] ah j'ai peut-être trouvé le soucis... (un chemin d'execution qui ne préserve pas la retenue.. bon ca vous dit rien, mais pour moi c'est juste super important.)
Samuel.
A500 Vampire V2+ ^8^, A1200 (030@50mhz/fpu/64mb/cf 8go),
A500 GVP530(MMU/FPU) h.s., R-Pi, TO9, TO8D, TO8.Démos
A500 Vampire V2+ ^8^, A1200 (030@50mhz/fpu/64mb/cf 8go),
A500 GVP530(MMU/FPU) h.s., R-Pi, TO9, TO8D, TO8.Démos
-
- Messages : 7987
- Inscription : 18 sept. 2010 12:08
- Localisation : Brest et parfois les Flandres
Re: [Thomson] SUDOKU, nouveau jeu pour MO et TO
Oui c'était bien le soucis. A présent tout mes tests semblent montrer un Sudoku avec une seule et unique solution comme attendu. Attention à ne pas choisir un nombre d'indices trop faibles, car d'une part c'est beaucoup plus lent à générer, et surtout ils sont durs. Essayez celui-ci de niveau 21 pour voir:
Description de l'Algo:
A la base c'est une approche complètement naïve, et qui marche bien pour les nombres d'indices >= 23 environ.
L'idée générale est de partir d'une grille pleine respectant les contraintes du Sudoku, puis d'effacer au pif une case. On regarde alors si le Sudoku correspondant n'a qu'une seule solution. Si non on génère une nouvelle grille pleine et on redémarre. Si oui on efface un nouvelle case au pif, on vérifie si le Sudoku n'a qu'une seule solution, etc.. On s'arrête quand la grille fini par atteindre le nombre d'indice désiré. C'est pas plus compliqué (et donc tient dans quelques centaines d'octets de code.)
Questions:
En pratique comme ca explose il vaut mieux se restreinte aux Sudoku avec au moins 25 indices, ce qui prend typiquement 1 minute à être généré et les Sudokus correspondants ne sont pas forcément triviaux (enfin je trouve... mais je ne suis pas bon à ces jeux là.)
A partir de là on peut
Voici le zip avec les binaires corrigés et le source ASM:
Description de l'Algo:
A la base c'est une approche complètement naïve, et qui marche bien pour les nombres d'indices >= 23 environ.
L'idée générale est de partir d'une grille pleine respectant les contraintes du Sudoku, puis d'effacer au pif une case. On regarde alors si le Sudoku correspondant n'a qu'une seule solution. Si non on génère une nouvelle grille pleine et on redémarre. Si oui on efface un nouvelle case au pif, on vérifie si le Sudoku n'a qu'une seule solution, etc.. On s'arrête quand la grille fini par atteindre le nombre d'indice désiré. C'est pas plus compliqué (et donc tient dans quelques centaines d'octets de code.)
Questions:
- comment on génère une grille de départ ? Et bien on place au pif les chiffres de 1 à 9 dans la grilles. Cela ne provoque pas d'impossibilités. Et ensuite on demande au solveur de nous résoudre la grille. Il fait cela très rapidement car il n'y a aucune contrainte en jeu. Cela nous donne autant de grilles possibles que de placement des chiffres 1 à 9 dans la grille (soit Arrangement 9 parmi 81 = 81!/(81-9)! = 9.5E+16 ... on en fera pas le tour tout de suite.)
- comment sait-on qu'une solution est unique ou pas ? Et bien au lieu de stopper le "solveur" à la 1ère solution trouvée, on le laisse continuer à la recherche d'une 2ème avant de le stopper. Cela se fait très facilement dans mon code ASM avec l'usage d'une "callback" passée en paramètre au solveur permettant facilement de decider ce qu'il faut faire quand on trouve une solution (stopper/continuer) ainsi que compter ou afficher la solution trouvée.
En pratique comme ca explose il vaut mieux se restreinte aux Sudoku avec au moins 25 indices, ce qui prend typiquement 1 minute à être généré et les Sudokus correspondants ne sont pas forcément triviaux (enfin je trouve... mais je ne suis pas bon à ces jeux là.)
A partir de là on peut
- optimiser l'ASM ce qui est risqué car on a vite fait d'introduire un bug dans l'algo sans s'en rendre compte et puis comme l'algorithme est exponentiel, il n'y a pas forcément à gagner beaucoup (s'il faut 10h pour trouver une solution, même 2x plus vite ca reste long 5h au final.)
- concevoir un algo un peu plus intelligent qui détecte assez tôt (comment??) les grilles de départ qui ne peuvent pas être solubles avec le nombre d'indices requis.
Samuel.
A500 Vampire V2+ ^8^, A1200 (030@50mhz/fpu/64mb/cf 8go),
A500 GVP530(MMU/FPU) h.s., R-Pi, TO9, TO8D, TO8.Démos
A500 Vampire V2+ ^8^, A1200 (030@50mhz/fpu/64mb/cf 8go),
A500 GVP530(MMU/FPU) h.s., R-Pi, TO9, TO8D, TO8.Démos
Re: [Thomson] SUDOKU, nouveau jeu pour MO et TO
J'ai aussi imaginé un autre algorithme, en commençant avec beaucoup d'indices et en enlevant des chiffres un par un tant qu'il y a une seule solution. Est-ce plus rapide ou plus lent ? Je n'en ai aucune idée.
Peu importe, l'algorithme de __sam__ semble très bien fonctionner. La prochaine étape pourrait être de remplacer les grilles préétablies de mon programme par des grilles calculées. Actuellement la bibliothèque de grilles est stockée en $A000-$BFFF (TO) ou $7200-$91FF (MO). En la supprimant il y a largement la place de mettre le générateur de grilles.
Pour ceux qui veulent essayer je donne ici la dernière version :
Peu importe, l'algorithme de __sam__ semble très bien fonctionner. La prochaine étape pourrait être de remplacer les grilles préétablies de mon programme par des grilles calculées. Actuellement la bibliothèque de grilles est stockée en $A000-$BFFF (TO) ou $7200-$91FF (MO). En la supprimant il y a largement la place de mettre le générateur de grilles.
Pour ceux qui veulent essayer je donne ici la dernière version :
Daniel
L'obstacle augmente mon ardeur.
L'obstacle augmente mon ardeur.
-
- Messages : 7987
- Inscription : 18 sept. 2010 12:08
- Localisation : Brest et parfois les Flandres
Re: [Thomson] SUDOKU, nouveau jeu pour MO et TO
C'est le même algorithme car la grille pleine est une grille avec 81 indices, et ensuite on retire des chiffres tant qu'il y a une solution unique. A noter que si le retrait d'un chiffre entraine une double solution, ce chiffre doit toujours être présent jusqu'à la fin. Si on a trop de tels chiffres figés alors la grille ne pourra fournir une solution. On en change alors, et on repart pour un tour.
Je crois que ca ne change pas grand chose. C'est toujours une marche au hasard dans l'espace des Sudoku (qui compte 6 670 903 752 021 072 936 960 éléments), et donc le temps correspond à la proba de rencontrer un exemplaire de ce qu'on cherche. Si ce qu'on cherche est très fréquent ca va vite. S'ils sont rares, il faut être patient voir super patient (il n'y a que 39 422 grilles à 17 indices à rotations/symétries/permutations près.)Est-ce plus rapide ou plus lent ? Je n'en ai aucune idée.
Il ne faut pas chercher les Sudoku trop rares. Car comme le générateur aléatoire n'a qu'un état de 16bits, il n'est pas même certain que ce qu'on recherche figure dans le sous-espace des états accessible au programme. Je pourrais détecter quand le générateur aléatoire revient à la même valeur au même point de l'algo pour en déduire que le programme boucle et que donc il ne pourra pas satisfaire la recherche. Mais bon, cela va aussi ralentir la recherche. C'est pas tellement mieux. Il suffit de choisir des tailles raisonnables et tout se passe bien.Peu importe, l'algorithme de __sam__ semble très bien fonctionner.
Samuel.
A500 Vampire V2+ ^8^, A1200 (030@50mhz/fpu/64mb/cf 8go),
A500 GVP530(MMU/FPU) h.s., R-Pi, TO9, TO8D, TO8.Démos
A500 Vampire V2+ ^8^, A1200 (030@50mhz/fpu/64mb/cf 8go),
A500 GVP530(MMU/FPU) h.s., R-Pi, TO9, TO8D, TO8.Démos
-
- Messages : 7987
- Inscription : 18 sept. 2010 12:08
- Localisation : Brest et parfois les Flandres
Re: [Thomson] SUDOKU, nouveau jeu pour MO et TO
Ouch
Par contre il est fichtrement difficile !!! Même l'ordi doit faire 138 choix pour le résoudre (normalement c'est quelques unités).
J'ai bien fait de prévoir un compteur temps sur 8 chiffres car là il lui aura fallu pas loin de 28h. Vive le mode accéléré x64 de DCMOTO Par contre il est fichtrement difficile !!! Même l'ordi doit faire 138 choix pour le résoudre (normalement c'est quelques unités).
Samuel.
A500 Vampire V2+ ^8^, A1200 (030@50mhz/fpu/64mb/cf 8go),
A500 GVP530(MMU/FPU) h.s., R-Pi, TO9, TO8D, TO8.Démos
A500 Vampire V2+ ^8^, A1200 (030@50mhz/fpu/64mb/cf 8go),
A500 GVP530(MMU/FPU) h.s., R-Pi, TO9, TO8D, TO8.Démos
Re: [Thomson] SUDOKU, nouveau jeu pour MO et TO
Oui, il est difficile. Je l'ai fait à la main et j'y ai passé plus d'une heure.
Et je me dis que si j'arrive à le faire en une heure, le MO5 devrait pouvoir le faire en quelques secondes en utilisant mon algorithme. Je vais y réfléchir. Le programme risque d'être plus compliqué, mais aussi beaucoup plus rapide car il n'y a aucune arborescence à explorer : quand on place un chiffre, c'est définitif. On ne choisit jamais au hasard.
Et je me dis que si j'arrive à le faire en une heure, le MO5 devrait pouvoir le faire en quelques secondes en utilisant mon algorithme. Je vais y réfléchir. Le programme risque d'être plus compliqué, mais aussi beaucoup plus rapide car il n'y a aucune arborescence à explorer : quand on place un chiffre, c'est définitif. On ne choisit jamais au hasard.
Daniel
L'obstacle augmente mon ardeur.
L'obstacle augmente mon ardeur.