Je programme un sudoku en java (en fait en C++ aussi).
L´interface est OK, je peux résoudre les grilles automatiqument (algorithme "dancing links" de Knuth) mais j´ai un problème pour générer des grilles de départ (à solution unique).
Quelqu´un aurait une idée ?

marrant, tout le monde utilise cet algo en ce moment pour ça...

Pour générer une grille de départ, tu pourrais remplir quelques cases aléatoirement, puis tu résout intégralement le sudoku si possible. S´il y a plusieurs solution, tu rajoutte des cases dans tes conditions de départ (et vice versa s´il n´y en a pas).

Jusqu´à arriver à une conditions de départ qui ne permet de trouver qu´une seule solution.
A ce moment là, tu peut enlever de ta conditions de départ le plus de case possible mais en permettant quand même de résoudre le sudoku.

Pour évaluer la difficulté du jeu, ce que je fait c´est de compté le nombre d´hypothèse que doit faire le logiciel pour résoudre la grille. Bien sûr c´est pas terrible car les heuristique que j´utilise sont assez mauvaise donc mon programme fait bien plus d´hypothèse que l´humain le plus stupide, mais c´est quand même une approximation de la difficulté.

Je faisais à peu près ça sauf que je n´enlevais pas de cases après avoir trouvé ma grille de départ qui était quasi pleine.

Je pensais aussi à une autre solution. A partir d´une grille de départ quasi vide, je rajoute uniquement des hypothèses qui minimise le nombre de solutions possibles.

J´ai eu beau cherché sur le net mais je n´ai pas trouvé d´heuristique éprouvée pour ce problème.

En ce qui concerne le "dancing links", il est vraiment pas mal. L´heuristique est bidon (trial and error) mais l´implémentation est vraiment rapide. Même en Java, ça tourne en un temps tout à fait acceptable sur ma vieille machine. Je te le conseille.