[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

__sam__
Messages : 7923
Inscription : 18 sept. 2010 12:08
Localisation : Brest et parfois les Flandres

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

Message par __sam__ »

Mon solveur le résout en 77secondes (voir bas de la capture écran).

Mon algo de génération (cf GENERATE dans le source) ne revient jamais sur un chiffre effacé conduisant à une solution unique. Il n'y a aucun backtrack contrairement au solveur (routine SOLVE). Du coup il doit itérer plein de fois à partir de grilles préremplies avant de tomber sur une dont on arrive à effacer le nombre de cases désirées.

Quand on y songe, on est pas loin de l'esprit du tri random avec cet algo de génération. Il ne tient compte d'aucune propriété du Sudoku pour générer les grilles de départ ou choisir une case à vider. Ca donne un code petit (il tient sur une page écran, cf contenu du zip), assez rapide pour des grilles correctes, mais peu satisfaisant intellectuellement.

J'ai vaguement regardé l'état de l'art des autres générateurs de Sudoku mais je pense que personne ne va plus loin que cela. Tout repose sur la chance et le choix d'une organisation des données accélérant la vitesse d'execution.
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 : 7923
Inscription : 18 sept. 2010 12:08
Localisation : Brest et parfois les Flandres

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

Message par __sam__ »

Ah, je viens de tomber sur un algo qui n'utilise pas de solveur pour la génération. Cela vient de chercheurs à Oxford il n'y a pas très longtemps:
Abstract a écrit : This paper describes a new algorithm for generating unique-solution Sudoku puzzles. Distinguished from common algorithms, it guarantees a unique solution itself rather than relaying on some unique-solution test algorithms. What is more, the time complexity of our algorithm is polynomial, which is a significant progress as most of the generation algorithms are non-polynomial.
https://www.researchgate.net/publicatio ... ion_Sudoku

L'algo est polynomial, ce qui nous serait plus qu'utile sur Thomson. Par contre j'ai pas l'impression qu'il prenne en entrée un nombre d'indice. Il part d'une grille remplie et élimine (rapidement) le plus d'indices possibles. Si on est en dessous du nombre d'indice que l'on veut, il suffit de combler certaines cases éliminées. Mais si on a encore trop d'indices, j'ai l'impression qu'il faut à nouveau générer un nouveau sudoku totalement résolu et relancer l'algo. C'est à nouveau parti pour une marche aléatoire à la recherche du trèfle à 4 feuilles.. euh du sudoku résoluble avec le nombre d'indices souhaité.

A propos de générer un sudoku totalement rempli rapidement il y a cette stratégie:
  • Remplir la 1ere ligne avec les nombres 1 à 9 placés dans un ordre aléatoire.
  • Ecrire en 2e ligne le contenu de la 1ere ligne décalée de 3 cases dans une direction que l'on fixe pour la suite (droite par exemple.)
  • Ecrire en 3e ligne la 2e ligne encore décalée de 3 cases dans la même direction.
  • Mettre en 4e ligne la 3e ligne décalée d'une seule case dans la même direction
  • La 5e ligne est la 4e mais décalée de 3 cases dans la même direction
  • La 6e ligne est la 5e mais décalée de 3 cases (même direction)
  • la 7eligne est la 6e décalée d'une case (même dir... bon je répète plus)
  • la 8e est la 7e décalée de 3, et enfin
  • la 9e est la 8e décalée de 3
Cet algo est capable de nous générer 9!=362880 grilles remplies valides. C'est beaucoup moins que ce que je présente plus haut (94670977328928000), mais cela va aussi un peu plus vite (pas de solveur pour combler les trous.)
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 : 17316
Inscription : 01 mai 2007 18:30
Localisation : Vaucluse
Contact :

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

Message par Daniel »

L'algorithme de création d'un problème est super intéressant, et permet certainement de réduire le temps de calcul.

La génération d'une grille avec décalage de ligne gagne sans doute beaucoup de temps, mais donne des grilles sur le même modèle. Si le joueur devine l'algorithme, la résolution du problème devient beaucoup plus simple : quand on a trouvé une ligne on peut facilement en déduire toutes les autres.

Le nombre d'indices est un critère parmi d'autres pour évaluer la difficulté, mais je ne suis pas sûr que ce soit le meilleur. J'ai déjà vu des problèmes avec peu d'indices très faciles à résoudre. C'est pourquoi il n'est pas forcément indispensable de fixer le nombre d'indices quand on génère un problème. J'imagine plutôt un autre algorithme indépendant du générateur pour déterminer le niveau de difficulté.
Daniel
L'obstacle augmente mon ardeur.
__sam__
Messages : 7923
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 : 31 juil. 2021 14:05 La génération d'une grille avec décalage de ligne gagne sans doute beaucoup de temps, mais donne des grilles sur le même modèle. Si le joueur devine l'algorithme, la résolution du problème devient beaucoup plus simple : quand on a trouvé une ligne on peut facilement en déduire toutes les autres.
C'est pour cela qu'il est recommandé ensuite de jouer des symétries.
Le nombre d'indices est un critère parmi d'autres pour évaluer la difficulté, mais je ne suis pas sûr que ce soit le meilleur. J'ai déjà vu des problèmes avec peu d'indices très faciles à résoudre. C'est pourquoi il n'est pas forcément indispensable de fixer le nombre d'indices quand on génère un problème. J'imagine plutôt un autre algorithme indépendant du générateur pour déterminer le niveau de difficulté.
Le solveur en ligne (sur le web) donné plus haut donne le nombre de choix qu'il a du faire pour résoudre le sudoku. Ca me semble un indicateur assez pertinent de la difficulté, mais il me semble difficile à étalonner car un choix peut parfois se faires entre 2 valeurs seulement, et un autre entre 5: les deux ne "pèsent" pas pareil. Il faudrait peut-être prendre le produit du nombre de choix total (ou le log pour ne pas avoir des nombres trop grands).

Par contre un truc plus simple est de donner une limite de temps T en entrée, puis:
  1. on génère une grille pleine (perso moi je place les nombres de 1 à 9 au pif, puis je résout. C'est super rapide, même sur thomson.)
  2. On établi une liste avec toutes les cases à visiter. On mélange la liste.
  3. Si la liste est vide on va en 1.
    Sinon on retire la 1ère case de la liste (de sorte qu'on ne retombe plus dessus plus tard).
  4. On efface l'indice de cette case.
  5. On résout en mesurant le temps (t) pris pour trouver la 1ere solution
    (Note: il y a toujours au moins une solution en ce point).
    On poursuit la recherche et on s'arrête si on trouve une 2e solution.
  6. Si une 2e solution a été trouvée on remets l'indice effacé et on repart en 3.
  7. Si t<T, on va en 3.
  8. Terminé! on a une solution unique dont la résolution prends au moins T secondes.
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 : 7923
Inscription : 18 sept. 2010 12:08
Localisation : Brest et parfois les Flandres

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

Message par __sam__ »

Je poursuis dans la recherche d'algos. J'en ai un qui va plus vite que le précédent car mieux codé, mais en regardant l'analyse des traces d'execution je me suis rendu compte d'un truc tout bête. L'algo passe 99% de son temps à calculer les cases laissées libres dans le sudoku après chaque choix lors de la recherche de solution. Il fait cela à chaque effacement, pour chacune des 81 cases, chacune nécessitant de regarder 21 voisines (8 sur la même colonne, 8 sur la même ligne et 5 dans le bloc) afin de trouver la case vide ayant le moins de choix. Or en fait, un choix n'impacte pas l'ensemble du Sudoku, mais uniquement les cases sur les mêmes lignes/colonnes/blocs, bref les cases qu'on a utilisées pour justement trouver les chiffres disponibles. On fait donc le calcul à chaque tour sur des cases qui n'ont pas été affectées par le dernier choix et dont les possibilités sont restées inchangées.

Cela veut dire qu'avec l'algorithme actuel on passe son temps à recalculer ce qu'on a déjà calculé au tour d'avant et qui n'a pas changé. C'est le principe #1 de l'optimisation qui n'est pas respecté: on ne fait pas deux fois la même chose dans un algorithme efficace!.

Aussi j'ai en train de naitre dans ma tête une modification légère et astucieuse qui évite cela. Je vous tiens au courant si cela rend l'algo de résolution encore plus rapide.
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 : 7923
Inscription : 18 sept. 2010 12:08
Localisation : Brest et parfois les Flandres

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

Message par __sam__ »

__sam__ a écrit : 09 août 2021 20:38 Aussi j'ai en train de naitre dans ma tête une modification légère et astucieuse qui évite cela. Je vous tiens au courant si cela rend l'algo de résolution encore plus rapide.
Bon j'ai codé un autre algorithme qui calcule moins de choses. L'idée est de ne recalculer le bitmask des chiffres utilisés non pas sur l'ensemble des 81 cases, mais uniquement sur les cases dépendante de celle à laquelle on affecte une valeur. Il va effectivement un peu plus vite (2 minutes de moins environ):
dcmoto07.png
dcmoto07.png (3.23 Kio) Consulté 2109 fois
(pour comparaison on avait 2236secs avant)

Bref, c'est mieux, mais pas tant que cela. Je soupçonne qu'on passe "trop" de cycles dans l'administration et la mise à jour de la structure de donnée. Je vais voir pour la changer de sorte que qu'on ait encore moins de calculs à effectuer. J'ai une petite idée. A voir ce que cela va donner une fois implémenté des débuggé...
Pièces jointes
Sudoku_solve2.zip
(34.58 Kio) Téléchargé 74 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 : 17316
Inscription : 01 mai 2007 18:30
Localisation : Vaucluse
Contact :

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

Message par Daniel »

L'intérêt d'un ordinateur lent est de nous obliger à réfléchir 8)
Avec un PC moderne ce n'est même pas drôle, la force brute est largement suffisante. Avec un MO5 ou un TO8 c'est du grand art...

Il est peut-être possible de diminuer le temps de calcul avec une pré-analyse du problème, pour placer le plus de chiffres possibles avant d'explorer l'arborescence. Par exemple, quand il y a le même couple de chiffres dans deux cases d'une même ligne, d'une même colonne ou d'un même carré, ces chiffres ne sont pas ailleurs dans la ligne, la colonne ou le carré, ce qui permet souvent d'en placer d'autres directement.
Daniel
L'obstacle augmente mon ardeur.
__sam__
Messages : 7923
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 : 18 août 2021 11:34 L'intérêt d'un ordinateur lent est de nous obliger à réfléchir 8)
Et c'est ce qui me plait justement.

Bon je savais bien que sur le papier mon algo devait être mieux, et j'ai été déçu de ce que j'ai obtenu hier où je n'ai pas vu grande différence. Aussi aujourd'hui matin je l'ai ré-écrit plus simplement sans m'appuyer sur la technique de kool-c0d3r qui optimise avant de voir si ca vaut le coup et j'obtiens ceci:
dcmoto08.png
dcmoto08.png (3.19 Kio) Consulté 2054 fois
On obtient un facteur 3 par rapport à hier 8) Le sudoku "ultime" qui mettait 40mins à être résolu par le Thomson ne prends plus que 12 minutes a présent. Je pense que ca c'est ce qu'on peut appeler de l'optimisation. :mrgreen:

Je n'ai pas utilisé des ruses de sioux en assembleur, mais une structure de données mieux adaptée au problème. Ca fait toute la différence. L'algo est toujours exponentiel mais grace à une structure de donnée qui maintient les contraintes avec le minimum de calcul (on ne calcule jamais deux fois la même chose), on réduit la "constante devant le grand-O" (pour ceux à qui ca parle.)

Le code détaillé est dans l'ASM, mais le mieux pour comprendre est de considérer que c'est la version Thomson de ce pseudo code vaguement Pascal:

Code : Tout sélectionner

(* structure de donnée *)
WORK : ARRAY 1..81 OF CASE;

CASE = RECORD
         chiffre     : BYTE; (* chiffre present dans la case *)
         nbzero      : BYTE (* nombre de utilises[x]==0 *)
         utilises    : ARRAY 1..9 OF BYTE; (* chiffre utilises par les cases de la même ligne/colonne/bloc *)
         contraintes : ARRAY 1..20 of BYTE (* indices précalculés des autres cases de la même ligne/colonne/bloc *)
      END

(* PLACE LE CHIFFRE "A" (0..9) DANS LA CASE "U" *)
(* TOUT EN MAINTENANT LA COHERENCE DANS LA STRUCTURE *)
PROCEDURE PUTDIGIT(A,U)
    (* fonctions auxiliaires *)
    LOCAL PROCEDURE CLRDGT(U)
        B = WORK[U].chiffre
        IF B!=0 then
            WORK[U].chiffre=0
            FOR i=1..20 DO
                j = WORK[U].contraintes[i]
                DEC(WORK[j].utilises[B])  (* décrémente *)
                IF WORK[j].utilises[B]==0 then
                    INC(WORK[j].nbzero)  (* incrémente *)
                END
            END
        END
    END
    LOCAL PROCEDURE PUTDGT(A,U)
        WORK[U].chiffre = A
        FOR i=1..20 DO
            j = WORK[u].contraintes[i]
            IF WORK[j].utilises[A]==0 then
                DEC(WORK[j].nbzero)
            END
            INC(WORK[j].utilises[A])
        END
    END
    (* === vrai code === *)
    IF A==0 THEN
        CLRDIGIT(U)
    ELSE
        IF WORK[u].chiffre!=0 THEN
            CLRDGIT(U)
        END
        PUTDGT(A,U)
    END
END

(* POINT D'ENTREE DE LA RESOLUTION *)
FUNCTION SOLVE(SUDOKU : ARRAY 1..81 OF BYTE)
    FOR i=1..81 DO
        WORK[i].nbzero = 9
        FOR j=1..9 DO
            WORK[i].utilises[j] = 0
        END
    END
    FOR i=1..81 DO
        PUTDIGIT(SUDOKU[i], i)
    END
    RETURN RECURSE()
END

(* RECHERCHE RECURSIVEMENT UNE SOLUTION *)
FUNCTION BOOLEAN RECURSE()
    LOCAL cpy : ARRAY 1..9 of BIT (* s'optimise dans un bitmask sur 8 bits si on est malin *)
    LOCAL i : BYTE (* espace d'état conservé d'un appel à l'autre = cpy + i = 2 octets seulement *)

    max = 10
    idx = 0
    FOR i=1..81 DO
        IF WORK[i].nbzero<max THEN
            max = WORK[i].nbzero
            idx = i
        END
    END
    IF max==10 THEN
        (* GRILLE PLEINE ! TERMINE *)
        AFFICHE_SUDOKU()
        RETURN TRUE
    END

    FOR i=1..9 DO
        cpy[i] = (WORK[idx].utilises[i]==0)  (* copie locale pour recursion *)
    END
    FOR i=1..9 DO
        IF cpy[i] THEN       (* chiffre 'i' pas utilise *)
            PUTDIGIT(i, idx) (* on place 'i' dans la case vide *)
            ok = RECURSE()   (* on lance la recherche *)
            PUTDIGIT(0, idx) (* on efface le chiffre *)
            IF ok THEN
                RETURN TRUE (* si trouvé, on s'arrête, sinon on continue avec tous les chiffres non utilisés *)
            END
        END
    END
    (* ON A TOUT EPUISE SANS TROUVER *)
    RETURN FALSE
END
(les variables locales sont indiquées par LOCAL, les autres on s'en fiche, globale ou locale importe peu)

J'espère que dans pas longtemps j'aurais un générateur qui l'utilise (et dont le paramètre d'entrée sera le "TEMPS" que mets ce solveur à résoudre. Facile = 1 sec, difficile = 700 secondes.)
Pièces jointes
Sudoku_solv3.zip
(35.36 Kio) Téléchargé 74 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
__sam__
Messages : 7923
Inscription : 18 sept. 2010 12:08
Localisation : Brest et parfois les Flandres

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

Message par __sam__ »

Bon ce soir j'ai un peu optimisé l'ASM avec des "trucs de codeurs" (c'est fou de gagner 60sec en remplaçant un LEA par ABX au bon endroit), et là j'obtiens cette vitesse résolution du Sudoku #17:
dcmoto09.png
dcmoto09.png (3.18 Kio) Consulté 2026 fois
Ca prends moins de 10 mins là où avant on était ~40mins. Donc à la louche la résolution va 4 fois plus vite, ce qui permet au petit Thomson de résoudre probablement les Sudoku les plus durs en moins d'une heure.

J'ai testé certains de ceux qui se prétendent les plus dur sur internet, et je suis déçu. Ils se résolvent vites en fait. Exemple:
Le prétendu &quot;World hardest Sudoku&quot; selon https://www.conceptispuzzles.com/index.aspx?uri=info/article/424
Le prétendu "World hardest Sudoku" selon https://www.conceptispuzzles.com/index.aspx?uri=info/article/424
dcmoto10.png (3.22 Kio) Consulté 2026 fois
Pièces jointes
Sudoku_solve4.zip
(35.63 Kio) Téléchargé 75 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
__sam__
Messages : 7923
Inscription : 18 sept. 2010 12:08
Localisation : Brest et parfois les Flandres

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

Message par __sam__ »

Selon cet autre site le Sudoku les plus dur est celui-ci:
Image
Voyons donc...
dcmoto11.png
dcmoto11.png (3.25 Kio) Consulté 2023 fois
Mouais même pas 1 seconde.

Il y a un truc, soit je me suis planté et j'ai un gros bug qui sort de fausses solutions, soit les sites webs disent des clowneries en matière de difficulté de Sudoku.
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 : 17316
Inscription : 01 mai 2007 18:30
Localisation : Vaucluse
Contact :

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

Message par Daniel »

Je ne serais pas surpris que les sudokus les plus durs pour les humains soient faciles avec ton algorithme, et réciproquement. Pour un humain il est difficile d'explorer systématiquement toute l'arborescence. En revanche ton algorithme ne voit pas à la première analyse des chiffres qu'un humain sait placer immédiatement.

Une autre approche serait peut-être l'auto-apprentissage avec un réseau de neurones. Ça me dépasse un peu, mais c'est probablement une bonne piste.
Daniel
L'obstacle augmente mon ardeur.
__sam__
Messages : 7923
Inscription : 18 sept. 2010 12:08
Localisation : Brest et parfois les Flandres

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

Message par __sam__ »

__sam__ a écrit : 19 août 2021 00:19 Bon ce soir j'ai un peu optimisé l'ASM avec des "trucs de codeurs" (c'est fou de gagner 60sec en remplaçant un LEA par ABX au bon endroit).
Trucs du codeurs, oui c'est plus rapide. Cependant quand je regardais le profiling du code ASM, je me rendais compte que dans cet algorithme, on passait vraiment pas mal de temps à parcourir le Sudoku à la recherche d'une case vide à remplir. Alors au début ca va vite, mais à la fin il y a peu de cases vides et on passe pas mal de temps à sauter par dessus les cases occupées. Or durant la recherche, une case pleine a toutes les chances de rester pleine à la suite. Aussi on passe son temps à sauter par dessus les mêmes cases occupées en permanence, bref à faire et refaire la même chose ce qui est l'anti-pattern d'un code pas optimisé.

J'ai eu un début d'optimisation en maintenant à jour le pointeur sur la 1ere case vide dans PUTDGT/CLRDGT. C'est pas mal car on ne passe plus son temps à lire le début du tableau. Par construction la 1ère case qu'on lit est toujours vide. Super, mais cette gestion était moche (grosse verrue), lourdingue et ne me plaisait pas. En plis elle ne règle pas les autres cases du tableau. Il fallait encore lire et relire sans cesses les cases pleines suivantes récursivement avant de tomber sur la 2e case vide.

:idea: C'est là que je me suis dit, et si on essayait autre chose que des trucs de codeurs, genre des optims de plus haut niveau, comme par exemple maintenir la liste des cases vides dans une liste chainée. Ainsi on pourrait "lister" toutes les cases vides à la recherche de celle ayant le moins de contraintes sans perdre de temps avec les pleines.

Alors c'est ce que j'ai fait, et, à ma grande surprise après quelques galères d'implémentation en ASM (les liste chainées sont moins naturelles en ASM qu'en C ou Pascal), ca s'implémente super facilement et c'est très très rapide (30 cycles en plus de l'algo précédent).

Voyez le temps qu'il me faut à présent pour résoudre le Sudoku #17:
dcmoto01.png
dcmoto01.png (3.26 Kio) Consulté 1915 fois
Oui ca va encore 2x plus vite qu'avant, qui allait 4x plus vite qu'à l'origine. 8)

Le profil actuel (fichier html dans l'archive) montre un équilibrage à 3 fois ~30% du temps dans
  1. l'écriture d'un chiffre dans le sudoku et le calcul du nombre de degrés de liberté pour les cases impactées (lien)
  2. idem avec l'effacement d'un chiffre (lien) et
  3. la recherche de la case ayant le plus de contraintes (c'est par elle qu'on résout le sudoku à chaque niveau car cela réduit le nombre de choix totaux que devra faire l'algorithme.) lien. Ici on pourrait aller encore plus vite en utilisant pas une liste chainée mais un arbre type RED-BLACK qui maintient toujours à son sommet l'élément le plus petit/grands. C'est assez chiant à écrire en C/Pascal, alors j'ose pas imaginer en ASM. Et le gain ne sera peut-être pas là car maintenir la structure de donnée va finir par couter pas mal si on ne fait pas beaucoup d'accès.
En l'état c'est l'algo de résolution le plus rapide que j'ai pu obtenir. Je vais regarder du coté de la génération à présent.. (il y a déjà des trucs dans le source ASM pour les curieux :) )
Pièces jointes
Sudoku_solve5.zip
(116.32 Kio) Téléchargé 71 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
jvernet
Messages : 2454
Inscription : 12 avr. 2007 10:59
Localisation : France 69
Contact :

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

Message par jvernet »

:o

Juste comme ça, comment on charge ça dans DCMOTO ?
__sam__
Messages : 7923
Inscription : 18 sept. 2010 12:08
Localisation : Brest et parfois les Flandres

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

Message par __sam__ »

Il faut utiliser le debugger et charger le fichier *.RAW entre $A000 et $DFFF. Mais là ca n'est pas spectaculaire ca ne fait que résoudre le problème 17. La génération sera plus intéressante. Il y a un paramètre qui permet de choisir la difficulté et qui marche assez bien je pense.
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 : 7923
Inscription : 18 sept. 2010 12:08
Localisation : Brest et parfois les Flandres

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

Message par __sam__ »

__sam__ a écrit : 27 juil. 2021 21:27 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.
Arg :twisted: Ca c'est faux!

Ca fait depuis 3 jours que j'essaye de comprendre pourquoi mon algo de génération bloque jusqu'à ce que je tombe sur une grille d'amorce avec chiffres 1 à 9 placés au pif comme ceci:
dcmoto02.png
dcmoto02.png (1.53 Kio) Consulté 1878 fois
:o Et oui c'est impossible à remplir en suivant les règles du Sudoku ! ( :idea: )

Contrairement à ce que j'ai écrit plus haut placer les chiffres 1 à 9 au pif ne génère pas forcément un truc soluble. Il y a même un contre-exemple plus simple encore avec les chiffres 1 à 8 sur la première ligne et le 9 sur la deuxième ligne là où on a laissé un trou sur la première ligne. Exemple

Code : Tout sélectionner

123 456 78.
... ... ..9
... ... ...

... ... ...
... ... ...
... ... ...

... ... ...
... ... ...
... ... ...
C'est évident, et pourtant je n'avais pas vu cela. Pour que cela fonctionne il ne faut pas mettre les chiffres 1 à 9, mais 1 à 8 , ou plus général: placer 8 chiffres parmi les 9 au hasard dans la grille.

Pff.. j'ai eu été plus clairvoyant par le passé. C'est pas beau de perdre des neurones :? (ca s'appelle vieillir)

_____
( :idea: ) les 3 cases vides sous le ".26"' de la seconde ligne ne peuvent contenir que les chiffres 5 ou 7. On a donc 3 cases à remplir avec deux chiffres. Impossible !
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
Répondre