Discussion :

[Alcatîz]

Nous avons reçu le projet de Ludelphi7, merci à lui.

C'est le second projet reçu, je rappelle que l'inscription au défi n'est effective qu'à la réception des sources.

[darrylsite]

Salut,
Je viens de confirmer mon inscription
En fait, vu le nombre assez important de mes unités, je me damandais si vous accepteriez qu'on joint aux codes une note detaillant la structure du code (des petits diagrammes par exemple).

[Alcatîz]

Salut,
Je viens de confirmer mon inscription

En effet.

En fait, vu le nombre assez important de mes unités, je me damandais si vous accepteriez qu'on joint aux codes une note detaillant la structure du code (des petits diagrammes par exemple).

Bien sûr, une doc bien faite est un plus !

[darrylsite]

Bonjour,
J'ai trouve une grille satanique qui fait raler mon solveur

120000000
000120000
000000100
012000000
000012000
000000012
201000000
000001020
000000001

Meme avec Dancing links, je n'arrive pas à le resoudre, le solveur tourne sans jamais s'arreter, et je ne parle pas du processeur
Alors si quelqu'un arrive à le resoudre, j'aimerais bien qu'il nous montre son chrono.

Sinon, j'ai trouvé tout récemment la methode dancing links, qui utilise les listes doublement chainées pour resoudre les grilles. J'ai trouvé un code que en C que j'ai traduit en pascal. Je ne sais pas si j'ai le droit de le poster ici. Il est à noté que le code est sur le net, et la source ne viens pas de moi.

[darrylsite]

Je poste donc le code du dancing links que j'ai traduit:
Site d'origine :http://cgi.cse.unsw.edu.au/~xche635/dlx_sodoku/
la traduction est compilable sous lazarus/freepascal. le code fonction en console.

Je ne sais pas si c'est la methode est plus lente ou c'est parce que le code n'est pas optimisé, mais il est dix fois plus lent que le mien. Mais le temps de resolution est persque constant queqle soit la grille.

Alors si quelqu'un d'autres idées sur la question, j'aimerais bien le savoir

[mick605]

Bonjour,
J'ai trouve une grille satanique qui fait raler mon solveur

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
120000000
000120000
000000100
012000000
000012000
000000012
201000000
000001020
000000001

Meme avec Dancing links, je n'arrive pas à le resoudre, le solveur tourne sans jamais s'arreter, et je ne parle pas du processeur
Alors si quelqu'un arrive à le resoudre, j'aimerais bien qu'il nous montre son chrono.

Sinon, j'ai trouvé tout récemment la methode dancing links, qui utilise les listes doublement chainées pour resoudre les grilles. J'ai trouvé un code que en C que j'ai traduit en pascal. Je ne sais pas si j'ai le droit de le poster ici. Il est à noté que le code est sur le net, et la source ne viens pas de moi.

Tu m'étonnes ! Cette grille n'a pas de solution ! Je peux en etre sur parce que j'ai testé 4 solveurs différents, et aucun n'a trouvé ... Par contre, pour mon solveur, au bout de 10 sec, il a déja testé toutes les configurations possibles ...

[darrylsite]

Tu m'étonnes ! Cette grille n'a pas de solution ! Je peux en etre sur parce que j'ai testé 4 solveurs différents, et aucun n'a trouvé ... Par contre, pour mon solveur, au bout de 10 sec, il a déja testé toutes les configurations possibles ...

C'est donc ça
Jai trouvé cette grille et je ne me suis pas trop posé de question . Le truc c'est que je n'attends jamais plus de 2 secondes, dès que je vois mon uc à 100% plus de 2 sec, j'arrete la resolution

Que pense tu du dlx?

[mick605]

C'est donc ça
Jai trouvé cette grille et je ne me suis pas trop posé de question . Le truc c'est que je n'attends jamais plus de 2 secondes, dès que je vois mon uc à 100% plus de 2 sec, j'arrete la resolution

Que pense tu du dlx?

Tenez a tous, cadeau :
Pour savoir le nombre de solutions d'une grille :
http://www.top-sudoku.com/

Un forum entièerement dédié au sudoku, je me demande pourquoi je l'ai pas trouvé plus tot :
http://www.setbb.com/phpbb/index.php?mforum=sudoku

A propos du DLX :
A vrai dire, je ne me suis jamais bien penché sur la question ... J'ai souvent cherché a comprendre la technique, mais j'ai laissé tomber plusieurs fois ... Mais ca a l'air d'être une très bonne solution, parce que tout le monde en parle !

[Ludelphi7]

Moi c'est ludodelphi7,
comme le nom l'indique, je programme d'habitude en delphi.
Le projet que j'ai transmis est l'adaptation de mon projet delphi, le chronometre en moins.
A propos, même si c'est un peu tard, quelqu'un peut me donner un chronometre pour lazarus que je puisse voir l'éventuel différence entre delphi et lazarus ?

merci d'avance

[darrylsite]

salut,
Pour des questions concernant la programmation pascal ou lazarus/freepascal, tu obtiendras davantage de reponde en postant directement dans la section dédiée.
Sinon, Lazarus à un composant TTimer que tu pourras utiliser. Tu peux aussi chercher d'autres composants tiers comme epiktimer ou autres. Mais il faut veiller à ce que ces composant soit minimun compatible windows/linux pour respecter le cahier de charge.

[mick605]

Bon, je me suis penché sur les Dancing Links ...

Si j'ai bien compris, c'est simplement un systeme permettant de classer facilement les données, et permettant de supprimer facilement un élément, puis le remettre ...

Pour le sudoku, c'est vrai que ca doit être efficace, du moins pour la partie bruteforce ... Pour la partie logique, par contre, ca devrait pas être d'une grande utilité ... (en tout cas, je parle pour mes méthodes logiques, car je me suis créé un système de stockage assez sympa, donc ca va)

darryl > tu voudrais pas nous poster quelques temps obtenus avec le DLX ? Pour les 7 grilles si possible, pour qu'on puisse comparer avec les anciens temps sur le fofo ...

Si j'ai le temps, je testerai peut être une résolution grâce au DLX ... Ca pourrait m'être utile de savoir me servir de ca ...

[darrylsite]

Je vais ajouter la classe à mon projet et vous donnerais les chronos. Mais ce code n'est pas optimisé, le temps est beaucoup plus lents. Pour pouvoir réellement comparer les chonos il faut retoucher un peu le code.

[mick605]

Ok, fais nous parvenir ces temps, meme non optimisés, pour voir vite fait ...

Bon, sinon, je crois avoir trouvé des super moyens de méthodes logiques grâce a ce DLX ... Une nouvelle méthode de résoudre un sudoku ... Ca pourrait être assez rapide, et aussi super court niveau code ...

Enfin bref, on verra ca après le défi ...

[darrylsite]

Voici les chronos :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
grille 1: 40.354 ms
grille 2: 48.144 ms
grille 3: 33.488 ms
grille 4: 38.313
grille 5: 306.953 ms
grille 6: 1.5 s
grille 7: 74.312 ms

[darrylsite]

Ok, fais nous parvenir ces temps, meme non optimisés, pour voir vite fait ...

Bon, sinon, je crois avoir trouvé des super moyens de méthodes logiques grâce a ce DLX ... Une nouvelle méthode de résoudre un sudoku ... Ca pourrait être assez rapide, et aussi super court niveau code ...

Enfin bref, on verra ca après le défi ...

Une nouvelle methode pour resoudre sudoku J'aimerai bien voir ça.
Moi, j'aimerais plutot coder et ajouter un generateur de grille dans mon rojet; mais j'ai peur qu'on me sanctionne pour non respect du cahier de charge

[mick605]

Oui, c'est vrai que c'est moins rapide qu'avant, mais je suis sur que tu va réussir a très bien l'optimiser ... Donc, tiens nous au courant sur tes chronos de DLX, en tout cas moi, ca m'interesse !

A+

[darrylsite]

C'est vrai que c'est beaucoup plus lent. Avec mon solveur sans dlx pour la grille 1, je fais du 129 microS contre 40 ms en dlx.

[mick605]

Une nouvelle methode pour resoudre sudoku J'aimerai bien voir ça.
Moi, j'aimerais plutot coder et ajouter un generateur de grille dans mon rojet; mais j'ai peur qu'on me sanctionne pour non respect du cahier de charge

Tiens, j'avais même pas vu ce message ... Nos posts se sont croisés ...

Ouais, pour le sudoku, j'aurais bien une idée qui pourrait résoudre toutes ces solutions en une seule méthode de calcul pas spécialement longue :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
Emplacement unique
Candidats doubles, triples, quadruples ...
Paires, triplets, quadruplets, etc. cachés
X-Wing
Swordfish, Jellyfish, etc

Donc je me dis que, comme toutes ces méthodes seront codées en une seule procedure, le code serait assez court donc facilement compréhensible et optimisable ... Enfin, peut être je me trompe, mais bon ...

Pour le générateur, je pense que ca ne peut qu'être un plus, ensuite, il faut trouver un moyen efficace de coder tout ca ^^

[Alcatîz]

Attention pour les retardataires : la date limite du 31 décembre 2009 approche à grands pas !
Passé cette date, plus aucun projet ne sera pris en considération.

[krachik]

Quelques heures avant la clôture et ces mêmes quelques heures avant 2010.