J'ai l'impression que ce que tu cherches, c'est de mesurer la difficulté d'un puzzle, et éventuellement de pouvoir générer des puzzles d'une difficulté donnée. Ça n'est pas évident, mais je ne pense pas que ta piste est très généralisable : ton algorithme va produire une sous-catégorie de solutions très restreinte, qui ne va jamais représenter toute la complexité des situations.
Pour calculer la difficulté, on doit pouvoir se baser sur le nombre et la profondeur des branches qui ne mènent pas à la solution, mais ça reste potentiellement loin du ressenti subjectif des joueurs.
Si j'en crois les applications commerciales existantes, il semble plus facile de gérer la difficulté des puzzles en ajoutant des chiffres pour faciliter la situation de départ, soit dans la grille, soit sur les bords. L'avantage de jouer avec les chiffres sur les bords c'est qu'il est très difficile de se rendre compte que l'on est aidé.
Et pour créer les puzzles, ce que je ferais, c'est simplement de générer une grille complète, et de retirer les chiffres des bords au hasard jusqu'à ne plus avoir de solutions uniques. Ça me semble être en O(n).
[^] # Re: Niveau de difficulté
Posté par arnaudus . En réponse au journal De ×ばつ4 à ×ばつ5 : quand mon générateur de grilles ne finissait plus. Évalué à 4 (+1/-0).
J'ai l'impression que ce que tu cherches, c'est de mesurer la difficulté d'un puzzle, et éventuellement de pouvoir générer des puzzles d'une difficulté donnée. Ça n'est pas évident, mais je ne pense pas que ta piste est très généralisable : ton algorithme va produire une sous-catégorie de solutions très restreinte, qui ne va jamais représenter toute la complexité des situations.
Pour calculer la difficulté, on doit pouvoir se baser sur le nombre et la profondeur des branches qui ne mènent pas à la solution, mais ça reste potentiellement loin du ressenti subjectif des joueurs.
Si j'en crois les applications commerciales existantes, il semble plus facile de gérer la difficulté des puzzles en ajoutant des chiffres pour faciliter la situation de départ, soit dans la grille, soit sur les bords. L'avantage de jouer avec les chiffres sur les bords c'est qu'il est très difficile de se rendre compte que l'on est aidé.
Et pour créer les puzzles, ce que je ferais, c'est simplement de générer une grille complète, et de retirer les chiffres des bords au hasard jusqu'à ne plus avoir de solutions uniques. Ça me semble être en O(n).