SUDOKU solution

Mon programme SUDOKU solution et SUDOKU solution guidée est disponible maintenant sur mon site, dans la rubrique "Panoramic". N'hésitez pas à l'essayer - il a des possibilités sympa !

Pour toutes remarques concernant ce programme, utilisez svp ce fil de discussion !

Tu vas bien trop vite, on a du mal à suivre !

Dans le premier programme (mais celui d'hier !) je me suis amusé à paramétrer l'emplacement et la dimension de la grille, pour pouvoir utiliser une police plus grande (taille 16) de façon à voir mieux les chiffres (mes yeux ne sont plus ce qu'ils étaient !). Et c'est plus facile de changer un paramètre (taille des carrés) pour faire des essais.
Ca donne ça (juste par curiosité):

Bonne idée ! Je vais y penser pour la suite !

pour l'exemple, j'ai juste fait quelque chose comme ça:

Code:

tp% = 30: : lf% = 140: car% = 40: ' top, left grille et taille carrés
for lig%=1 to 9
    for col%=1 to 9
        obj% = (lig%-1)*9 + col%
        edit obj%
        left obj%,lf%+col%*car%
        top obj%,tp%+lig%*car%
        width obj%,car%-10
        height obj%, car%-10
        font_size obj%, 16
    next col%
next lig%

x1% = lf%+car%-10
y1% = tp%+car%-10
x2% = lf%+10*car%
y2% = tp%+10*car%
2D_line lf%+car%-10, tp%+car%-10, lf%+10*car%, tp%+car%-10
2D_Rectangle x1%, y1%, x2%, y2%
2D_Line x1%, y1%+3*car%+5, x2%, y1%+3*car%+5
2D_Line x1%, y1%+6*car%+5, x2%, y1%+6*car%+5
2D_Line x1%+3*car%+5, y1%, x1%+3*car%+5, y2%
2D_Line x1%+6*car%+5, y1%, x1%+6*car%+5, y2%

et j'ai rajouté un espace devant l'affichage des chiffres, pour les centrer.

J'ai vu ce que ça donne. J'intègre cela dans les deux programmes et je les remets en ligne. Merci pour ton aide !

Ca y est - les deux programmes sont adaptés selon ta suggestion. C'est beaucoup plus joli comme ça . Merci beaucoup !

Il n'y a vraiment pas de quoi, ce n'était qu'un détail par rapport à tout le reste !

PS une babiole, le 2D_Line en ligne 30 (avant le 2D_Rectangle) est inutile, c'est un reste des essais...

N'empêche (je me répète), c'est un beau programme.

J'ai vu, pour la ligne 30. Je l'ai enlevée dans SUDOKU solution ET dans SUDOKU solution guidée.

Dans ce dernier programme, j'ai eu un problème bizarre d'effacement partiel du cadre gauche vertical, lié à la création des boutons de la barre verticale des nombres. J'ai déplacé le dessin du cadre juste avant l'instruction "end", et tout est rentré dans l'ordre. C'est cette version qui est en ligne maintenant.

Je l'ai vu, et j'ai déjà eu ce problème d'effacement de cadre il y a quelque mois (pour des options), au niveau des captions des options, comme si panoramic complétait les captions avec des espaces, j'ai corrigé en agrandissant le cadre.

Dans ton cas, il semble que panoramic crée d'abord les objets à gauche, de manière invisible (sauf l'effacement) en rencontrant le TOP, puis les met en position définitive quand il rencontre le LEFT. Et ça perturbe ce qui est déjà créé.
C'est mon hypothèse, mais ça y ressemble...

Comme ces paramètres de position et de taille ne sont pas obligatoires, ça doit se faire dans l'ordre suivant pour les créations d'objets:
- définition de l'objet: il est créé en position 0
- rencontre de TOP ou LEFT: déplacement de l'objet en conséquence
- WIDTH ou HEIGHT: pareil

Si tu commences par faire un PRINT au début, puis que tu définis un PICTURE par exemple, ce PRINT sera effacé de la largeur implicite d'un PICTURE (105 pixels je crois) en 0,0 puis le picture sera créé à l'emplacement demandé, mais la partie du print restera effacée.
Il faut définir d'abord le picture, puis faire le print ensuite.
Un peu embêtant, mais bon...
Sauf avis contraire, ça ne perturbe que les PRINT ou les LINE, mais non les objets ?

Là-dessus, bonne nuit !

Oui, cela concerne print et tous les 2d_line, 2d-rectangle, 2d_poly_to. Ton analyse est la bonne; probablement, le canvas de la form 0 est affecté, et toutes ces instructions dessinent directement sur le canvas de la form 0 (soit le 2d_target_is et print_target_is par défaut. Un peu ennuyeux, mais visiblement, on peut y remédier en plaçant les print et 2d_xxx après la définition des objets.

Ce qui aurait été sans doute mieux, et qui aurait évité bien des lignes de code, ça aurait été de définir un objet en une seule fois avec ses paramètres, par exemple:
PICTURE numéro, left, top, largeur, hauteur
avec éventuellement des valeurs implicites pour les paramètres en mettant -1, quitte à redéfinir entièrement l'objet si on veut le redimensionner ou le déplacer.
Et au moins il aurait été créé au bon endroit du premier coup.

J'i utilisé la technique suggérée par Cosmos70 avec des picture. C'est encore plus jloi comma ça, d'autant que même dans la configuration précédente, le cadre a tendance à s'effacer par moments. Il faudra que je creuse cela pour signaler ce bug, car le canvas de la form 0 ne doit pas bouger si l'on ne fait ni print ni 2d_xxx.

J'en ai profité pour ajouter une fonction majeure à SUDOKU solution guidée. On peut maintenant générer ses propres grilles, en spécifiant le nombre de cases qui doit être prérempli ! Ce nombre est 32 par défaut; il faudra que je voie à l'usage: ce chiffre est peut-être un peu élevé. Avec 26, cela donne des résultats acceptables. Une grille générée doit ensuite être "chargée" pour la rendre exploitable. Si l'on reçoit le message "Cette grille n'a pas de solution", il faut en générer une autre. Je n'ai pas encore trouvé la formule magique qui génère une grille à une seule solution du premier coup. Je continue à chercher...

Effectivement, si tu te mets à générer des grilles ce serait vraiment une avancée majeure, parce que j'ai cru comprendre que ce n'était pas de la tarte !

Je viens d'essayer la génération de grilles, et je tombe sur des incohérences, par exemple:

Si on numérote les colonnes de A à I et les rangées de 1 à 9 on s'aperçoit qu'on ne peut mettre le 3ème 9 dans la colonne B (plus de place).
De même, dans la case E4 on devrait pouvoir mettre un 9 ET un 3...
J'ai eu d'autres exemples avec d'autres grilles.
Décidément, je continue à penser que c'est beaucoup plus difficile que ça en a l'air de générer des grilles.

Pour résoudre ce genre d'incohérences, j'ai fait une modif qui est en ligne depuis 11:01 ce matin; le fichier SUDOKU.30.zip doit faire 8261 octets. Télécharge à nouveau et réessaye avec cette version - ce problème doit être résolu. Cela ne garantit encore en rien une grille soluble, mais j'ai éliminé ces premières incohérences évidentes.

Pourtant j'avais bien dû télécharger la dernière version, aujourdhui en deuxième partie d'après-midi.
Mais bon, je vais réessayer.

EDIT à première vue c'est pareil, j'ai bien la dernière version, 1er essai:
le 3 impossible à mettre dans la dernière colonne...
(je précise que dans les exemples que je donne il n'y a que les chiffres générés par le programme).

J'ai remis une nouvelle version en ligne. Pas de changement profond, mais une nette amélioration du système d'aide avec un affinage du coloriage des cellules "possibles" et des "possibilités" pour une cellule donnée.

Quant au problème signalé par toi, JL35, le programme contient une séquence spéciale justement pour éviter cela: ce sont les lignes 500 à 582. Mais je vois d'où vient le problème: lors de l'installation du premier "3", le programme détecte des cellules libres disponibles dans de carré du bas en_dehors de la colonne concernée, et il en est évidemment de même lors de l'installation du deuxième "3".

Conclusion: je complèterai mon code par une détection du même nombre dans une autre ligne/colonne d'un autre carré afin de maîtriser ce cas. Cela viendra prochainement.

En attendant, la fonction "Charger" aurait refusé cette grille. Je sais, intellectuellement, je n'est pas joli, mais ce sera bientôt corrigé.

Petit bonus: dans le zip mis en ligne ce soir, il y a 3 grilles valides générées par ce programme. On peut les charger par la fonction "Ouvrir". Ces grilles sont solubles à l'aide ce ce programme.

Mes remarques se veulent constructives, et ça n'empêche pas que je suis admiratif de la rigueur du travail que tu fais.

C'est bien ainsi que je l'entends, et cela me motive pour aller de l'avant.

EDIT
===

En regardant mon programme, je constate que j'ai déjà tenu compte de cet aspect. Ce sont les lignes 543 et 569 qui s'en chargent: je détecte à ces endroits si une cellule candidate est déjà couverte par le rayonnement d'un nombre identique dans un autre groupe.

Donc, le problème vient d'ailleurs. C'est le remplissage des cellules par le 8, le 5 ou le 7 après l'installation des "3" qui ont conduit à cette situation. Je mets au point une stratégie pour y remédier.

Désolé Klaus, mais sur une bonne douzaine de grilles générées, je n'en ai pas eu une seule qui ne conduisait pas à une anomalie tôt ou tard.
par exemple:

mais parfois c'est moins immédiat, seulement vers la fin qu'on tombe sur une impossibilité.
Bon, eh bien...

Dans la dernière mise en ligne, j'ai ajoute quelques grilles valides générées avec ce programme. Je reconnais que la génération est loin d'être au point. J'ai découvert une méthode plus sûre et je suis en train de coder l'algorithme. Il y aura bientôt de nouvelles.

En attendant, on peut saisir n'importe quelle grille et la sauvegarder et/ou la résoudre, ce qui était le but initial du programme. Mais la génération complète viendra. Ceci dit, essaie de générer avec moins de 28 cases remplies - la fréquence des grilles valides augmente.

Je ne suis pas inquiet, mais je sais que c'est un sacré boulot, pour avoir tenté, et n'avoir pas réussi.

Ca y est - j'ai mis en ligne une version avec un générateur première génération qui semble marcher. Il n'est pas complètement aléatoire comme je le souhaitais, mais génère tout de même des grilles tout à fait différentes à chaque passage.

Plus un laisse de cases remplies, plus un a une chance d'avoir une solution unique. Le programme de toute façon n'utilise qu'une seule solution: celle qui a permis de générer la grille en effaçant certaines cases.

Mais il faut aussi l'utiliser pour résoudre des grilles fournies par des tiers; une fois saisies, on peut les enregistrer ("Sauver") et reprendre, et un peut sauvegarder des étapes intermédiaires...

Bon... y'a plus qu'à le passer à la moulinette...

Effectivement, de cette façon, en générant d'abord une grille complète puis en effaçant aléatoirement un certain nombre (en fonction de la difficulté désirée) de cases, on ne risque plus d'incohérence.
Mais, et il me semble que c'est le problème que j'avais eu, est-ce qu'il n'y a pas des règles à respecter dans le choix des cases à effacer, sous peine de tomber sur des grilles insolubles, ou ambiguës (plusieurs solutions) ?

PS j'ai trouvé ça: http://davidbau.com/archives/2006/09/04/sudoku_generator.html notamment la partie 'Sudoku Generation Algorithm'.

PS2 ce serait bien d'effacer 'Génération en cours...' une fois la génération terminée.

Exemple d'une grille qu'on ne peut pas terminer (2 solutions possibles):

colonne 2 = 8, 5, 2, 9, 1, 6, 7, 4, 3 ou bien 8, 5, 6, 9, 1, 2, 7, 4, 3
bon, je sais, je pinaille...

Non, tu ne pinailles pas. C'est un échange enrichissant le le programme en profitera. Je suis content d'être tombé sur un fan de Sudoku !

J'effacerai bien sûr le message de génération. Quant au problème des solutions multiples, je l'avais signalé, et j n'ai pas encore trouvé le moyen de les éliminer. Ton lien est très intéressant et je vais en explorer tous les coins.

En effet, d'après ce que j'ai vu sur d'autres forums, il y a des stratégies pour éliminer les solutions multiples. Mais dans presque tous les cas, on dit "s'il y a plus d'une solution, alors replacer le dernier chiffre effacé et recommencer avec un autre" et des phrases de même teneur. Or, mon problème est justement de détecter s'il y a plusieurs solution; j'en connais une: c'est la configuration de départ, mais est-ce qu'il peut y en avoir plusieurs après un effacement de chiffre, je ne le sais pas encore le détecter. Mais ça viendra...

Quant à ton exemple, c'est typiquement le cas d'un "carré" de possibilités pour un nombre, sans lien avec les autres cellules. Dans ce cas, on peut effectivement choisir l'une ou l'autre configuration, et la solution sera bonne. Je sais, dans ce cas, il n'aurait pas fallu effacer ces cellules. C'est une piste à suivre pour affiner la procédure; pour le moment, j'efface simplement de façon aléatoire, mais c'est seulement une première tentative.