[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__ »

hlide a écrit : 12 juil. 2021 19:52 __sam__, tes algorithmes sont en mesure de résoudre les Sudoku de difficulté "expert" ?
Ben oui.. le denier, celui avec 17 indices fait parti des plus durs je crois (il n'y a pas de sudoku à 16 indices il me semble)... Il prends 4ms à peu près avec luajit.

Code : Tout sélectionner

$ ./LuaJIT/src/luajit sudoku.lua
input:  1
[ , , , , , , , ,1]
[2,1, , , , ,9, ,4]
[4, ,3,5, , ,6, , ]
[9, , ,2, ,4,5, , ]
[ , ,2,7, ,5,8, , ]
[ , ,1,6, ,8, , ,3]
[ , ,4, , ,7,3, ,9]
[7, ,9, , , , ,6,8]
[1, , , , , , , , ]
solution:
[6,8,5,9,4,2,7,3,1]
[2,1,7,3,8,6,9,5,4]
[4,9,3,5,7,1,6,8,2]
[9,6,8,2,3,4,5,1,7]
[3,4,2,7,1,5,8,9,6]
[5,7,1,6,9,8,2,4,3]
[8,5,4,1,6,7,3,2,9]
[7,2,9,4,5,3,1,6,8]
[1,3,6,8,2,9,4,7,5]
depth:  52
time:   0.013   sec

input:  2
[ ,6, ,2,3, , , , ]
[ , ,8, , ,4, , , ]
[3, ,5, , ,8, ,4,7]
[ , ,2, , , , , ,1]
[5, , , ,6, , , ,9]
[9, , , , , ,7, , ]
[7,4, ,9, , ,5, ,6]
[ , , ,4, , ,9, , ]
[ , , , ,8,3, ,7, ]
solution:
[4,6,1,2,3,7,8,9,5]
[6,9,8,7,5,4,1,3,2]
[3,2,5,1,9,8,6,4,7]
[8,7,2,5,4,9,3,6,1]
[5,3,7,8,6,1,4,2,9]
[9,1,4,3,2,6,7,5,8]
[7,4,3,9,1,2,5,8,6]
[2,8,6,4,7,5,9,1,3]
[1,5,9,6,8,3,2,7,4]
depth:  55
time:   0.01    sec

input:  3
[ , ,3,8,5, , ,9, ]
[ , , , , , ,1, , ]
[6, , , , , , ,2,7]
[ , , ,1, , ,9, , ]
[ ,6, ,5, ,7, ,8, ]
[ , ,8, , ,3, , , ]
[1,5, , , , , , ,3]
[ , ,2, , , , , , ]
[ ,9, , ,8,5,4, , ]
solution:
[4,7,3,8,5,1,6,9,2]
[7,2,5,4,9,6,1,3,8]
[6,8,9,3,1,4,5,2,7]
[8,3,7,1,6,2,9,4,5]
[9,6,1,5,3,7,2,8,4]
[2,1,8,9,4,3,7,5,6]
[1,5,4,7,2,9,8,6,3]
[5,4,2,6,7,8,3,1,9]
[3,9,6,2,8,5,4,7,1]
depth:  58
time:   0.012   sec

input:  4
[ ,7,5, , ,6,8, , ]
[ , , , , , , , ,3]
[3, , ,5,1, ,6, , ]
[ ,2, , , , , , , ]
[ ,5,4,8, ,1,2,9, ]
[ , , , , , , ,5, ]
[ , ,2, ,5,9, , ,6]
[7, , , , , , , , ]
[ , ,3,1, , ,9,8, ]
solution:
[4,7,5,3,9,6,8,1,2]
[5,6,1,9,7,8,4,2,3]
[3,8,7,5,1,2,6,4,9]
[1,2,9,7,4,3,5,6,8]
[6,5,4,8,3,1,2,9,7]
[9,3,8,6,2,4,7,5,1]
[8,1,2,4,5,9,3,7,6]
[7,9,6,2,8,5,1,3,4]
[2,4,3,1,6,7,9,8,5]
depth:  56
time:   0.002   sec

input:  5
[6, ,5, , , , ,4, ]
[ , , , , ,2, ,7,6]
[ , , ,7, , ,3, , ]
[ , , ,6,2, , ,8, ]
[ ,8,7, ,5, ,6,2, ]
[ , , , ,8,4, , , ]
[ , ,1, , ,5, , , ]
[5,2, ,8, , , , , ]
[ ,6, , , , ,9, ,5]
solution:
[6,7,5,1,3,8,2,4,9]
[1,3,8,5,9,2,4,7,6]
[2,1,9,7,4,6,3,5,8]
[3,9,4,6,2,7,5,8,1]
[4,8,7,9,5,1,6,2,3]
[7,5,6,3,8,4,1,9,2]
[9,4,1,2,6,5,8,3,7]
[5,2,3,8,1,9,7,6,4]
[8,6,2,4,7,3,9,1,5]
depth:  56
time:   0.003   sec

input:  6
[ , , ,3,6, ,1, , ]
[ , , , ,8, , , , ]
[9,4,1,5, ,2, , , ]
[ ,5, , , ,8, , ,7]
[ ,6, , ,2, , ,9, ]
[8, , ,9, , , ,5, ]
[ , , ,1, ,6,9,7,8]
[ , , , ,4, , , , ]
[ , ,8, ,9,7, , , ]
solution:
[5,8,7,3,6,4,1,2,9]
[1,2,6,7,8,9,5,3,4]
[9,4,1,5,7,2,6,8,3]
[6,5,9,2,1,8,3,4,7]
[4,6,5,8,2,3,7,9,1]
[8,7,2,9,3,1,4,5,6]
[2,3,4,1,5,6,9,7,8]
[7,9,3,6,4,5,8,1,2]
[3,1,8,4,9,7,2,6,5]
depth:  55
time:   0.022   sec

input:  7
[9,7, , , , , , , ]
[3, ,5, , ,2,9,4, ]
[ , , , ,9,5, , , ]
[ , , ,2, , , , ,5]
[ , ,4, ,8, ,2, , ]
[5, , , , ,9, , , ]
[ , , ,6,7, , , , ]
[ ,8,2,9, , ,7, ,3]
[ , , , , , , ,8,1]
solution:
[9,7,1,8,2,6,5,3,4]
[3,1,5,7,6,2,9,4,8]
[1,4,7,3,9,5,8,2,6]
[6,3,9,2,1,8,4,7,5]
[7,6,4,1,8,3,2,5,9]
[5,2,8,4,3,9,6,1,7]
[8,5,3,6,7,4,1,9,2]
[4,8,2,9,5,1,7,6,3]
[2,9,6,5,4,7,3,8,1]
depth:  57
time:   0.016   sec

input:  8
[ , , , , ,3, , ,9]
[ ,4,8, , ,6, ,7,2]
[1, , , , , ,4, , ]
[7, ,9,4,3, , , , ]
[ , , , ,2, , , , ]
[ , , , ,6,7,2, ,1]
[ , ,2, , , , , ,7]
[9,3, ,7, , ,6,1, ]
[4, , ,6, , , , , ]
solution:
[2,5,4,1,7,3,8,6,9]
[3,4,8,5,9,6,1,7,2]
[1,7,6,2,8,9,4,3,5]
[7,2,9,4,3,1,5,8,6]
[6,8,1,3,2,5,7,9,4]
[5,9,3,8,6,7,2,4,1]
[8,6,2,9,1,4,3,5,7]
[9,3,5,7,4,2,6,1,8]
[4,1,7,6,5,8,9,2,3]
depth:  55
time:   0.002   sec

input:  9
[ , , ,1, , , , ,3]
[ , , , , ,5,8, , ]
[ ,1, , , ,7,6,9,4]
[ , , , ,5,8, , , ]
[ ,5,4,9, ,2,3,8, ]
[ , , ,7,1, , , , ]
[6,7,8,3, , , ,2, ]
[ , ,3,5, , , , , ]
[9, , , , ,1, , , ]
solution:
[7,8,6,1,9,4,2,5,3]
[4,2,1,6,7,5,8,3,9]
[5,1,2,8,3,7,6,9,4]
[3,9,7,2,5,8,4,1,6]
[1,5,4,9,6,2,3,8,7]
[2,6,9,7,1,3,5,4,8]
[6,7,8,3,4,9,1,2,5]
[8,4,3,5,2,6,9,7,1]
[9,3,5,4,8,1,7,6,2]
depth:  54
time:   0.004   sec

input:  10
[ , , , , , ,6, ,8]
[5,6,9,3, , , , , ]
[ , ,7,6, , , , , ]
[1, , , , , ,5, , ]
[ ,8, ,9,7,5, ,2, ]
[ ,5, , , , , , ,4]
[ , , , , ,7,2, , ]
[ , , , , ,4,7,5,3]
[9, ,3, , , , , , ]
solution:
[7,3,1,5,4,2,6,9,8]
[5,6,9,3,2,1,4,8,7]
[2,4,7,6,8,9,3,1,5]
[1,9,6,4,3,8,5,7,2]
[3,8,4,9,7,5,1,2,6]
[8,5,2,7,1,3,9,6,4]
[4,1,5,8,6,7,2,3,9]
[6,2,8,1,9,4,7,5,3]
[9,7,3,2,5,6,8,4,1]
depth:  57
time:   0.003   sec

input:  11
[ ,8, , , , ,1, ,3]
[7, ,9, , , ,8,2,4]
[ , ,5, , , , , ,7]
[ ,2, ,8, ,9, , , ]
[ , , ,4, ,1, , , ]
[ , , ,2, ,6, ,8, ]
[2, , , , , ,5, , ]
[4,5,1, , , ,3, ,2]
[8, ,7, , , , ,6, ]
solution:
[6,8,2,7,9,4,1,5,3]
[7,1,9,5,6,3,8,2,4]
[9,4,5,1,8,2,6,3,7]
[1,2,3,8,5,9,7,4,6]
[5,6,8,4,3,1,2,7,9]
[3,7,4,2,1,6,9,8,5]
[2,3,6,9,4,7,5,1,8]
[4,5,1,6,7,8,3,9,2]
[8,9,7,3,2,5,4,6,1]
depth:  54
time:   0.034   sec

input:  12
[ , ,6, , ,7,5,9, ]
[ , , , , , , ,2, ]
[ , , , ,6,3,1, , ]
[ ,9,5,8,7, , , ,2]
[ , , , ,4, , , , ]
[1, , , ,3,5,9,6, ]
[ , ,7,3,8, , , , ]
[ ,4, , , , , , , ]
[ ,5,9,7, , ,6, , ]
solution:
[8,3,6,2,1,7,5,9,4]
[3,6,1,9,5,4,7,2,8]
[7,2,4,5,6,3,1,8,9]
[6,9,5,8,7,1,4,3,2]
[2,7,3,1,4,9,8,5,6]
[1,8,2,4,3,5,9,6,7]
[9,1,7,3,8,6,2,4,5]
[5,4,8,6,9,2,3,7,1]
[4,5,9,7,2,8,6,1,3]
depth:  55
time:   0.003   sec

input:  13
[ , ,3, , ,9, ,6, ]
[7, ,8, , , ,4, ,9]
[5, , , , , ,2, , ]
[ , ,1,2, , , , , ]
[ , , ,8, ,5, , , ]
[ , , , , ,6,1, , ]
[ , ,5, , , , , ,4]
[8, ,4, , , ,3, ,7]
[ ,2, ,5, , ,9, , ]
solution:
[2,4,3,1,8,9,7,6,5]
[7,6,8,3,5,2,4,1,9]
[5,8,6,7,9,4,2,3,1]
[4,7,1,2,6,3,5,9,8]
[9,1,2,8,4,5,6,7,3]
[3,5,9,4,7,6,1,8,2]
[6,3,5,9,1,7,8,2,4]
[8,9,4,6,2,1,3,5,7]
[1,2,7,5,3,8,9,4,6]
depth:  58
time:   0.005   sec

input:  14
[ , , ,7,8, , , , ]
[ ,7, , , , ,2, , ]
[ ,1, ,5, , ,4,9,7]
[8, , , ,1,2,5, , ]
[5, , , , , , , ,6]
[ , ,6,3,5, , , ,4]
[4,3,2, , ,5, ,6, ]
[ , ,1, , , , ,5, ]
[ , , , ,3,9, , , ]
solution:
[3,2,4,7,8,6,9,1,5]
[1,7,5,9,6,4,2,3,8]
[6,1,3,5,2,8,4,9,7]
[8,6,9,4,1,2,5,7,3]
[5,4,7,8,9,1,3,2,6]
[2,9,6,3,5,7,1,8,4]
[4,3,2,1,7,5,8,6,9]
[9,8,1,6,4,3,7,5,2]
[7,5,8,2,3,9,6,4,1]
depth:  54
time:   0.011   sec

input:  15
[5, , , , ,7, , , ]
[ , , , , ,8,7, ,3]
[3,7, , ,1, , , ,2]
[2, , , , , ,5, , ]
[ , ,5,3,6,2,4, , ]
[ , ,1, , , , , ,8]
[6, , , ,9, , ,4,5]
[1, ,4,5, , , , , ]
[ , , ,2, , , , ,9]
solution:
[5,6,9,1,3,7,2,8,4]
[4,1,6,9,2,8,7,5,3]
[3,7,8,4,1,5,6,9,2]
[2,4,3,8,7,9,5,1,6]
[9,8,5,3,6,2,4,7,1]
[7,9,1,6,5,4,3,2,8]
[6,3,2,7,9,1,8,4,5]
[1,2,4,5,8,3,9,6,7]
[8,5,7,2,4,6,1,3,9]
depth:  55
time:   0.015   sec

input:  16
[ , , , ,5, ,6, , ]
[1, ,3, , , ,7, , ]
[4,5, ,3, , , , , ]
[ ,2, , , ,5, ,6, ]
[ ,4,9, ,2, ,1,8, ]
[ ,3, ,1, , , ,9, ]
[ , , , , ,8, ,1,6]
[ , ,5, , , ,9, ,3]
[ , ,6, ,3, , , , ]
solution:
[7,9,2,8,5,1,6,3,4]
[1,6,3,5,8,2,7,4,9]
[4,5,7,3,6,9,8,2,1]
[8,2,1,9,4,5,3,6,7]
[6,4,9,7,2,3,1,8,5]
[5,3,8,1,7,6,4,9,2]
[3,7,4,2,9,8,5,1,6]
[2,8,5,6,1,4,9,7,3]
[9,1,6,4,3,7,2,5,8]
depth:  55
time:   0.003   sec

input:  17
[ , , , , , , ,1, ]
[ , , , , ,2, , ,3]
[ , , ,4, , , , , ]
[ , , , , , ,5, , ]
[4, ,1,6, , , , , ]
[ , ,7,1, , , , , ]
[ ,5, , , , ,2, , ]
[ , , , ,8, , ,4, ]
[ ,3, ,9,1, , , , ]
solution:
[5,4,9,2,3,7,6,1,8]
[1,8,4,5,6,2,9,7,3]
[8,7,6,4,2,9,3,5,1]
[9,1,8,3,7,4,5,6,2]
[4,2,1,6,5,8,7,3,9]
[3,6,7,1,9,5,8,2,4]
[7,5,3,8,4,1,2,9,6]
[6,9,2,7,8,3,1,4,5]
[2,3,5,9,1,6,4,8,7]
depth:  65
time:   0.004   sec

total time:     0.165   sec
Mais je ne sais pas ce qu'on appelle dur ou pas... Le sudoku le plus dur au monde présenté ici
Image
a été résolu chez moi en 5ms... Alors soit j'ai un bug dans l'algo de recherche, soit ce qui est dur pour les humains ne l'est pas forcément pour un algo (triez 10 000 fiches par ordres alphabétiques pour voir), soit les notion de "hardest sudoku" c'est du pipeau total.
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
Zebulon
Messages : 2788
Inscription : 02 nov. 2020 14:03

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

Message par Zebulon »

Ta seconde hypothèse est la bonne Sam. Si l'humain veut tenter de résoudre un sudoku en force brut, il lui faudra plusieurs crayons, plusieurs gommes, et il n'y aura tout simplement plus de papier à gommer. Sans compter le temps que cela lui prendrait. Je ne connaissais pas l'étendue des techniques documentées dans le lien partagé par hlide mais tel un monsieur Jourdain je dois en appliquer quelques unes sans le savoir. L'expert doit toutes les connaître. C'est un peu comme la résolution du Rubik's Cube sans enlever le mérite aux pros je trouve que cela perd de sa magie quand on sait que tout n'est que technique.
Avatar de l’utilisateur
hlide
Messages : 3469
Inscription : 29 nov. 2017 10:23

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

Message par hlide »

Donc l'algorithme "brut" peut en venir à bout sans les techniques en question. Juste que pour un humain, ça lui prendra long sans en appliquer les techniques car il y aura des échecs et des retours arrières à la manière de la découverte d'un labyrinthe... le marquage peut aider mais les échecs successifs peuvent fatiguer l'humain. Et entre nous, c'est l'application de ces techniques qui rend plus exaltante la résolution.

En fait, je me demandais comment on pouvait arriver à un bon compromis sur la classification de la difficulté via un tel algorithme.
Dernière modification par hlide le 12 juil. 2021 22:31, modifié 1 fois.
Daniel
Messages : 17316
Inscription : 01 mai 2007 18:30
Localisation : Vaucluse
Contact :

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

Message par Daniel »

Les algorithmes utilisés par les humains pour résoudre les sudokus sont très différents de ceux utilisés généralement par les programmes.

Il est "surhumain" d'explorer toutes les branches de l'arborescence, alors l'humain procède différemment. Pour ma part je commence par placer tous les chiffres "évidents" (pour lesquels il n'y a pas de choix possible en fonction du contenu de leur ligne, leur colonne et leur carré). Ensuite c'est un peu plus compliqué, mais ça tient un peu des recettes de cuisine.

Dans les sudokus réputés difficiles pour les humains, les recettes de cuisine ne s'appliquent plus, il faut explorer l'arborescence. C'est difficile pour un humain, mais pour un programme qui explore toute l'arborescence dans tous les cas, ces sudokus "difficiles" ne le sont pas beaucoup plus que les faciles. Ils peuvent être seulement un peu plus longs à trouver.

Il y a peut-être des algorithmes pour éviter la "force brute" et trouver plus vite le résultat. Je vais poser la question à un spécialiste de ce genre de problème et je vous en dirai plus dans quelques semaines.
Daniel
L'obstacle augmente mon ardeur.
Zebulon
Messages : 2788
Inscription : 02 nov. 2020 14:03

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

Message par Zebulon »

Sam j'ai un doute... dans tes exemples les grilles sont bien présentées telles qu'écrites sur le papier ? J'ai l'impression que la règle d'unicité des valeurs 1 à 9 par sous-carré n'est pas toujours respectée.

On résout même les Sudoku en Prolog https://pcaboche.developpez.com/article ... lp/sudoku/ c'est bô. Et le plus dingue c'est que la grille du Sudoku le plus dur du monde est résolue instantanément alors que ta grille 17 prend 25 secondes sur mon Athlon II X4 640.
Dernière modification par Zebulon le 12 juil. 2021 23:18, modifié 1 fois.
Avatar de l’utilisateur
hlide
Messages : 3469
Inscription : 29 nov. 2017 10:23

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

Message par hlide »

La classification apparemment retenue, je l'ai déjà donnée :
En ce qui concerne Le Sudoku, les règles de classification suivantes ont été adoptées :
• facile : la déduction de chaque chiffre est directe ; aucune technique avancée n'est nécessaire
• moyen : soit la déduction est directe, soit il faut utiliser la technique du ...
• difficile : il faut utiliser la technique du ... ou la technique du ...
• expert : c'est seulement à l'aide de la technique du ... que vous pourrez résoudre cette catégorie de puzzles
Si l'algorithme avait la possibilité d'appliquer des techniques, on pourrait effectivement parvenir à classifier la grille.

En fait, je me demande si la classification exclut tout simplement le fait que l'humain ait recours à la "récursion" (i.e, il teste une valeur jusqu'à ce qu'un échec ait lieu ou finalement résous le Sudoko en définitif par hasard).
Avatar de l’utilisateur
hlide
Messages : 3469
Inscription : 29 nov. 2017 10:23

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

Message par hlide »

@__sam__:

je viens de vérifier le résultat du 17 :

Code : Tout sélectionner

[5,4,9|...]
[1,8,4|...]
[8,7,6|...]
Pas de 2 et de 3, deux 4 et deux 8 dans le bloc 1 !
Zebulon
Messages : 2788
Inscription : 02 nov. 2020 14:03

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

Message par Zebulon »

Le programme Prolog trouve ceci pour la grille 17:

Code : Tout sélectionner

?- sudokuExemple1(Vars).

===================
|7,4,5|3,6,8|9,1,2|
|8,1,9|5,7,2|4,6,3|
|3,6,2|4,9,1|8,5,7|
===================
|6,9,3|8,2,4|5,7,1|
|4,2,1|6,5,7|3,9,8|
|5,8,7|1,3,9|6,2,4|
===================
|1,5,8|7,4,6|2,3,9|
|9,7,6|2,8,3|1,4,5|
|2,3,4|9,1,5|7,8,6|
===================
|
Vars = [7, 4, 5, 3, 6, 8, 9, 1, 2|...] ;
false.
Et ceci pour le Sudoku le plus dur du monde:

Code : Tout sélectionner

?- sudokuExemple2(Vars).

===================
|1,4,5|3,2,7|6,9,8|
|8,3,9|6,5,4|1,2,7|
|6,7,2|9,1,8|5,4,3|
===================
|4,9,6|1,8,5|3,7,2|
|2,1,8|4,7,3|9,5,6|
|7,5,3|2,9,6|4,8,1|
===================
|3,6,7|5,4,2|8,1,9|
|9,8,4|7,6,1|2,3,5|
|5,2,1|8,3,9|7,6,4|
===================
|
Vars = [1, 4, 5, 3, 2, 7, 6, 9, 8|...] ;
false.
Mais nous sommes incorrigibles car le sujet de départ, c'est de résoudre en tant qu'humain une grille sur MO ou TO. :wink:
Avatar de l’utilisateur
hlide
Messages : 3469
Inscription : 29 nov. 2017 10:23

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

Message par hlide »

Zebulon a écrit : 12 juil. 2021 23:00 On résout même les Sudoku en Prolog https://pcaboche.developpez.com/article ... lp/sudoku/ c'est bô. Et le plus dingue c'est que la grille du Sudoku le plus dur du monde est résolue instantanément alors que ta grille 17 prend 25 secondes sur mon Athlon II X4 640.
Excellent !
giphy.gif
giphy.gif (1.39 Mio) Consulté 2001 fois
__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__ »

hlide a écrit : 12 juil. 2021 23:18 @__sam__:

je viens de vérifier le résultat du 17 :
...
Pas de 2 et de 3, deux 4 et deux 8 dans le bloc 1 !
Bon c'est clair l'algo est buggé :( Pourtant la règle des blocs est belle et bien présente: le bout de code suivant retire les valeurs déjà présente dans le bloc qui contient (x,y)

Code : Tout sélectionner

..
	local gx = math.ceil(x/3)*3
	local gy = math.ceil(y/3)*3
	for i=gx-2,gx do 
		for j=gy-2,gy-2 do <== Oh la boulette !!!!
			if chk(i,j) then return num,pos end
		end 
	end
	return num,pos
end
Ah okok, ya un bug avec "for j=gy-2,gy-2"... Cela n'itère pas trop cette boucle et au final la contrainte est largement ignorée. C'est une modif que je venais de faire, le 1er code (lien au dessus) n'a pas ce bug. :oops:

Quand on corrige (j=gy-2,gy) il vient

Code : Tout sélectionner

input:  17
[ , , , , , , ,1, ]
[ , , , , ,2, , ,3]
[ , , ,4, , , , , ]
[ , , , , , ,5, , ]
[4, ,1,6, , , , , ]
[ , ,7,1, , , , , ]
[ ,5, , , , ,2, , ]
[ , , , ,8, , ,4, ]
[ ,3, ,9,1, , , , ]
solution:
[7,4,5,3,6,8,9,1,2]
[8,1,9,5,7,2,4,6,3]
[3,6,2,4,9,1,8,5,7]
[6,9,3,8,2,4,5,7,1]
[4,2,1,6,5,7,3,9,8]
[5,8,7,1,3,9,6,2,4]
[1,5,8,7,4,6,2,3,9]
[9,7,6,2,8,3,1,4,5]
[2,3,4,9,1,5,7,8,6]
depth:  65
time:   8.163   sec
C'est la même solution que Zebulon obtenue en 8 sec sur un: "Intel(R) Core(TM) i7-2640M CPU @ 2.80GHz 2.80 GHz"
soit un cpu un chouia (15%) plus rapide que l'Athlon.

Note: J'aime bien le Prolog aussi. C'est sympa à utiliser (je l'ai croisé et utilisé plusieurs fois dans mon travail de recherche.. c'était une autre vie.)

[EDIT] Je viens d'améliorer l'implémentation de findPossibilites3() qui évite de recalculer les stats à chaque étape, mais les maintient en cours de route. A présent j'obtiens

Code : Tout sélectionner

solution:
[7,4,5,3,6,8,9,1,2]
[8,1,9,5,7,2,4,6,3]
[3,6,2,4,9,1,8,5,7]
[6,9,3,8,2,4,5,7,1]
[4,2,1,6,5,7,3,9,8]
[5,8,7,1,3,9,6,2,4]
[1,5,8,7,4,6,2,3,9]
[9,7,6,2,8,3,1,4,5]
[2,3,4,9,1,5,7,8,6]
depth:  65
time:   4.793   sec
soit l'algo le plus rapide de tous, et de loin 8)
Dernière modification par __sam__ le 13 juil. 2021 10:36, modifié 1 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 »

J'ai un vieil algorithme écrit en 2007 par un professionnel.
La grille 17 est résolue instantanément, mais ce n'est pas surprenant car le programme est compilé.

Code : Tout sélectionner

/////////////////////////////////////////////////////////////////////////////
//
// sudosolver.c
//
// Rémi Coulom
//
// December, 2007
//
/////////////////////////////////////////////////////////////////////////////
int tExclusion[81][20];
int tPopCount[1024];

/////////////////////////////////////////////////////////////////////////////
// Initialize useful arrays
/////////////////////////////////////////////////////////////////////////////
void Initialize()
{
 //
 // tExclusion
 //
 {
 int i;
 for (i = 81; --i >= 0;)
 {
  int x = i % 9;
  int y = i / 9;

  int Index = 0;

  {
   int xx;
   for (xx = 9; --xx >= 0;)
    if (xx / 3 != x / 3)
     tExclusion[i][Index++] = xx + y * 9;
  }

  {
   int yy;
   for (yy = 9; --yy >= 0;)
    if (yy / 3 != y / 3)
     tExclusion[i][Index++] = x + yy * 9;
  }

  {
   int xx;
   for (xx = 9; --xx >= 0;)
   {
    int yy;
    for (yy = 9; --yy >= 0;)
     if (xx / 3 == x / 3)
      if (yy / 3 == y / 3)
       if (xx != x || yy != y)
        tExclusion[i][Index++] = xx + yy * 9;
   }
  }
 }
 }

 //
 // tPopCount
 //
 {
  int i;
  for (i = 1024; --i >= 0;)
  {
   int PopCount = 0;
   int ii = i;
   while (ii)
   {
    if (ii & 1)
     PopCount++;
    ii >>= 1;
   }
   tPopCount[i] = PopCount;
  }
 }
}

/////////////////////////////////////////////////////////////////////////////
// Solve function: returns 1 (solved) or 0 (not solved)
/////////////////////////////////////////////////////////////////////////////
int Solve(char tDigit[])
{
 //
 // Compute exclusion mask
 //
 int tMask[81];

 {
 int i;
 for (i = 81; --i >= 0;)
  tMask[i] = 1023;
 }

 {
 int i;
 for (i = 81; --i >= 0;)
  if (tDigit[i])
  {
   int j;
   for (j = 20; --j >= 0;)
    tMask[tExclusion[i][j]] &= ~(1 << tDigit[i]);
  }
 }

 //
 // Find empty square with min number of possibilities
 //
 int MinIndex = 0;
 int MinPopCount = 11;
 {
 int i;
 for (i = 81; --i >= 0;)
  if (tDigit[i] == 0)
  {
   int PopCount = tPopCount[tMask[i]];
   if (PopCount < MinPopCount)
   {
    if (PopCount == 0)
     return 0;
    MinIndex = i;
    MinPopCount = PopCount;
   }
  }
 }

 //
 // No empty square: problem solved !
 //
 if (MinPopCount == 11)
  return 1;

 //
 // Try every possibility on that square, and solve recursively
 //
 {
 int i;
 for (i = 1; i < 10; i++)
  if (tMask[MinIndex] & (1 << i))
  {
   tDigit[MinIndex] = (char)i;
   int fSolved = Solve(tDigit);
   if (fSolved)
    return 1;
   tDigit[MinIndex] = 0;
  }
 }

 //
 // No possibility works
 //
 return 0;
}

#include <iostream>
/////////////////////////////////////////////////////////////////////////////
// Print
/////////////////////////////////////////////////////////////////////////////
void Print(const char *tDigit, std::ostream &out)
{
 for (int i = 0; i < 9; i++)
 {
  for (int j = 0; j < 9; j++)
   out << int(tDigit[j + i * 9]) << ' ';
  out << '\n';
 }
 out << '\n';
}

/////////////////////////////////////////////////////////////////////////////
// main function
/////////////////////////////////////////////////////////////////////////////
int main()
{
 Initialize();

 char tDigit[] =
 {
  0,2,6,3,0,0,8,0,0,
  0,0,0,1,0,0,9,0,0,
  0,1,0,0,0,6,0,0,0,
  0,0,8,9,0,3,0,5,1,
  0,0,0,0,0,0,0,0,0,
  1,7,0,5,0,8,4,0,0,
  0,0,0,6,0,0,0,2,0,
  0,0,5,0,0,9,0,0,0,
  0,0,2,0,0,4,1,3,0,
 };

 Print(tDigit, std::cout);

 if (Solve(tDigit))
  Print(tDigit, std::cout);
 else
  std::cout << "No solution\n";

 int i;
 std::cin >> i;

 return 0;
}
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__ »

Oui c'est pas surprenant que le compilé aille très vite. En décortiquant l'algo je me rends compte que c'est le même que mon algo 1) [trouver les cases vides ayant le moins de possibilité] avec pas mal de precalc histoire d'aller encore plus vite: tableau de comptage du nombre de bits allumés dans un entier 9 bits (popCount), tExclusion[case][20] qui indique pour chaque case les indices des autres cases la contraignant (pour chacune des 81 cases, il y a toujours exactement 8+6+6=20 cases qui la contraignent), etc. L'état courant des possibilités est stocké dans tMask[81] ce qui mange pas mal de place. En fait de ce tableau seule le mask (tMask[MinIndex]) et les coordonnées de la case courante (MinIndex) ont vraiment besoin d'être sauvegardés entre deux appels récursifs (en se débrouillant bien on peut faire tenir ca dans 2 octets si on était "court" en usage de la pile.)

Cela démontre que si les sudoku sont très difficiles pour l'humain, c'est un jeu trivial à attaquer à la force brute sur les ordinateurs actuels. Maintenant est-ce que cela sera toujours vrai sur les 8 bits qui sont au bas mot 1000 à 10 000 fois plus lents. Il faudrait essayer les compilo C "du marché", pour voir ce qu'ils font (mais perso je pense que de l'ASM humain ira forcément plus vite, et est plus fun à coder.)

PS: coucou au fiston ;)
Dernière modification par __sam__ le 13 juil. 2021 11:07, 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 : 17316
Inscription : 01 mai 2007 18:30
Localisation : Vaucluse
Contact :

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

Message par Daniel »

__sam__ a écrit : 13 juil. 2021 10:44 PS: coucou au fiston ;)
Il n'a pas abandonné l'idée d'un réseau de neurones sur MO5 pour son jeu de GO : http://dcmoto.free.fr/programmes/crazy6809/index.html
Le mois dernier il a même acheté un MO5 sur leboncoin pour tester, et je lui ai envoyé un SDDRIVE pour stocker ses programmes.
C'est long car il est très occupé par ailleurs. Il embauche : https://www.kayufu.com/

Je vais discuter avec lui de l'évaluation de la difficulté d'un problème de Sudoku.
J'arriverai peut-être à le convaincre de programmer un générateur de problèmes sur MO5.
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 : 13 juil. 2021 11:04 J'arriverai peut-être à le convaincre de programmer un générateur de problèmes sur MO5.
La génération est un problème un peu plus compliqué que la résolution (et pour cause: elle utilise massivement l'algo de résolution pour vérifier qu'en supprimant un chiffre d'une grille pleine on conserve l'uncité de la solution).
https://www.101computing.net/sudoku-gen ... algorithm/
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
Zebulon
Messages : 2788
Inscription : 02 nov. 2020 14:03

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

Message par Zebulon »

Le code est très propre bravo. :wink: Le mieux que je pourrais faire dans un premier temps sur 8 bit c'est de le porter en Turbo Pascal sur CPC.
Répondre