[Thomson] SUDOKU, nouveau jeu pour MO et TO

Cette catégorie traite de développements récents pour nos vieilles machines, applications, jeux ou démos... Amis programmeurs, c'est ici que vous pourrez enfin devenir célèbres!

Modérateurs : Papy.G, fneck, Carl

Avatar de l’utilisateur
fxrobin
Messages : 102
Inscription : 07 mars 2019 13:51
Localisation : RENNES
Contact :

Re: [Thomson] SUDOKU, nouveau jeu pour MO et TO

Message par fxrobin »

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.
Daniel
Messages : 17286
Inscription : 01 mai 2007 18:30
Localisation : Vaucluse
Contact :

Re: [Thomson] SUDOKU, nouveau jeu pour MO et TO

Message par Daniel »

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.
Daniel
L'obstacle augmente mon ardeur.
__sam__
Messages : 7909
Inscription : 18 sept. 2010 12:08
Localisation : Brest et parfois les Flandres

Re: [Thomson] SUDOKU, nouveau jeu pour MO et TO

Message par __sam__ »

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.

Code : Tout sélectionner

(main)SUDOKU

DEBUG SET 0
GRID  SET 1

  ORG   $A000
  BRA   INI
[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)

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
Pour les patients, essayez avec GRID à 17, et pour les impatients, voici le résultat du code ci-dessus:
dcmoto.gif
dcmoto.gif (2.02 Kio) Consulté 2649 fois
@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.

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
A noter: pour le GRID=17 c'est en revanche très très lent.
dcmoto.png
dcmoto.png (3.11 Kio) Consulté 2640 fois
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 ?
Pièces jointes
sudoku_solve.zip
Source et binaire TO à lancer en &HA000 (DEBUG=0, GRID=1)
(8.1 Kio) Téléchargé 82 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
Daniel
Messages : 17286
Inscription : 01 mai 2007 18:30
Localisation : Vaucluse
Contact :

Re: [Thomson] SUDOKU, nouveau jeu pour MO et TO

Message par Daniel »

Ça va m'inciter à ajouter un mode "triche" dans le programme de sudoku :wink:
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.
jasz
Messages : 1313
Inscription : 05 oct. 2016 20:05
Localisation : Quelque part dans le 31

Re: [Thomson] SUDOKU, nouveau jeu pour MO et TO

Message par jasz »

Ou limiter à 32Mhz. C'est déjà bien...
__sam__
Messages : 7909
Inscription : 18 sept. 2010 12:08
Localisation : Brest et parfois les Flandres

Re: [Thomson] SUDOKU, nouveau jeu pour MO et TO

Message par __sam__ »

Daniel a écrit : 14 juil. 2021 20:50 J'ai essayé avec plusieurs gilles, ça marche bien.
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é 89 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
Avatar de l’utilisateur
6502man
Messages : 12242
Inscription : 12 avr. 2007 22:46
Localisation : VAR
Contact :

Re: [Thomson] SUDOKU, nouveau jeu pour MO et TO

Message par 6502man »

Avec du retard, Félicitations Daniel :D
Phil.

www.6502man.com

To bit or not to bit.
1 or 0.
__sam__
Messages : 7909
Inscription : 18 sept. 2010 12:08
Localisation : Brest et parfois les Flandres

Re: [Thomson] SUDOKU, nouveau jeu pour MO et TO

Message par __sam__ »

Petit teaser..
Lancer sur TO: EXEC &amp;HA000,&lt;nb d'indices&gt;
Lancer sur TO: EXEC &HA000,<nb d'indices>
dcmoto03.png (3.5 Kio) Consulté 2437 fois
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 :arrow: niveau débutant
    • 40 indices :arrow: niveau facile
    • 26 indices :arrow: niveau difficile
    • 17 indices :arrow: 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é 77 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
Daniel
Messages : 17286
Inscription : 01 mai 2007 18:30
Localisation : Vaucluse
Contact :

Re: [Thomson] SUDOKU, nouveau jeu pour MO et TO

Message par Daniel »

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.
Daniel
L'obstacle augmente mon ardeur.
__sam__
Messages : 7909
Inscription : 18 sept. 2010 12:08
Localisation : Brest et parfois les Flandres

Re: [Thomson] SUDOKU, nouveau jeu pour MO et TO

Message par __sam__ »

Daniel a écrit : 27 juil. 2021 11:05 Reste à trouver un algorithme pour vérifier l'unicité de la solution...
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
__sam__
Messages : 7909
Inscription : 18 sept. 2010 12:08
Localisation : Brest et parfois les Flandres

Re: [Thomson] SUDOKU, nouveau jeu pour MO et TO

Message par __sam__ »

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:
Niveau 21... dur
Niveau 21... dur
dcmoto04.png (3.54 Kio) Consulté 2369 fois
Voici le zip avec les binaires corrigés et le source ASM:
Sudoku_gen.zip
BIN=binaire thomson (TO) à charger avec LOADM.
RAW=fichier binaire brut à charger et lancer en $A000 sous le débuggeur de DCMOTO.
(15.93 Kio) Téléchargé 81 fois

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.
Alors je disais que l'approche est naïve car il n'y a pas vraiment d'intelligence pour choisir de bonne grilles de départ ou a l'inverse éliminer "assez tôt" les mauvaises. Au final cet algo revient à se balader dans l'espace des Sudokus possibles pour tomber sur un qui nous convienne. Suivant la "densité" des Sudokus avec le nombre d'indices souhaité il faudra examiner plus ou moins de grilles de départ. Si on recherche un Sudokus avec beaucoup d'indices (>50) alors pratiquement la 1ère (ou la 2ème) grille de départ fournira un Sudoku. Par contre si on veut moins d'indices (par exemple moins de 25), les Sudokus correspondant sont de plus en plus rares et il faudra en essayer plein (mais vraiment plein.. genre 5000 ou plus) avant d'en trouver un bon. Et parfois, si on a pas de chance il peut mettre beaucoup, mais vraiment beaucoup plus de temps que la moyenne du niveau (mais ils sont beaucoup plus dur à résoudre aussi). Exemple:
Niveau 21... Il faut être patient
Niveau 21... Il faut être patient
dcmoto05.png (3.48 Kio) Consulté 2366 fois

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
  1. 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.)
  2. 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
Daniel
Messages : 17286
Inscription : 01 mai 2007 18:30
Localisation : Vaucluse
Contact :

Re: [Thomson] SUDOKU, nouveau jeu pour MO et TO

Message par Daniel »

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 :
dcsudoku.20210712.zip
(85.47 Kio) Téléchargé 85 fois
Daniel
L'obstacle augmente mon ardeur.
__sam__
Messages : 7909
Inscription : 18 sept. 2010 12:08
Localisation : Brest et parfois les Flandres

Re: [Thomson] SUDOKU, nouveau jeu pour MO et TO

Message par __sam__ »

Daniel a écrit : 28 juil. 2021 08:40 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.
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.
Est-ce plus rapide ou plus lent ? Je n'en ai aucune idée.
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.)
Peu importe, l'algorithme de __sam__ semble très bien fonctionner.
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.
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
__sam__
Messages : 7909
Inscription : 18 sept. 2010 12:08
Localisation : Brest et parfois les Flandres

Re: [Thomson] SUDOKU, nouveau jeu pour MO et TO

Message par __sam__ »

Ouch :o
Avec 20 indices ca devient long!
Avec 20 indices ca devient long!
dcmoto06.png (3.5 Kio) Consulté 2327 fois
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).
Sans titre.png
Sans titre.png (231.92 Kio) Consulté 2325 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
Daniel
Messages : 17286
Inscription : 01 mai 2007 18:30
Localisation : Vaucluse
Contact :

Re: [Thomson] SUDOKU, nouveau jeu pour MO et TO

Message par Daniel »

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.
Daniel
L'obstacle augmente mon ardeur.
Répondre