générer grille de sudoku sans disjoncteur

eh oui, c'est ma lubie du moment :mrgreen:

quelqu'un a-t-il tenté d'écrire en js un algo fiable pour générer des grilles complétées sans avoir besoin d'un break à un moment ou à un autre?

je bloque question logique (trop peu de neurones) sur un moyen de prévoir qu'une case ne pourra être pourvue d'un chiffre unique quand viendra son tour;

le principe que j'utilise:

9 tableaux représentant les lignes
9 tableaux représentant les colonnes
9 tableaux représentant les blocs

à chaque case à pourvoir, je fais un test pour vérifier dans les trois tableaux dont la case fait partie les valeurs encore disponibles et j'affecte une de ces valeurs au hasard à la case;

hum... ce hasard est bien fragile...

Comment faire pour que "la meilleure valeur soit choisie"? (celle qui ne provoquera pas une impasse en cours de génération);

merci :)

Tiens, voila l'algorithme à utiliser:
http://en.wikipedia.org/wiki/Dancing_Links

Bon, j'avoue que ta méthode semble plus naturelle (on peut même l'appeller backtracking algorithm, ça fait plus sérieux). Mais on ne peut pas tellement l'améliorer: tu fais un choix à chaque fois que tu peux, si tu n'as qu'une solution, tu continues, et si tu n'as plus aucune solution (pour la case courante), tu reviens à ton dernier choix, et tu le changes...

Ca marche, mais c'est lent. Sinon, tu as l'algorithme ci-dessus. Si tu arrives à decrypter un peu, j'essayerais de le faire faire à mes eleves... (un peu de sadisme de temps en temps).

pfff :cry:

les explications en lien ( http://en.wikipedia.org/wiki/Sudoku ) ne sont guère plus transparentes!
les x et les y, moi je veux bien mais je reste un peu sur ma faim;

je continue mes recherches sur le web d'un script js opérationnel;

merci pour le backtracking algorithm :lol:

pour le temps de génération, j'ai l'impression que j'obtiens des choses correctes (==> voir faq) vu que c'est toujours au même endroit que ça coince et que je fais un break quand l'indicateur d'essais monte un peu trop; d'ailleurs, j'ignore aussi au bout de combien d'essais je peux estimer que la case est impossible à pourvoir!
et puis quand ça passe, c'est carrément direct: les grilles générées n'ont eu à subir presque aucun retour en arrière 8O

truc de fou, ce jeu pour des pas matheux...