Petit deterrage, car j'aimerais exprimer mon avis (eh oui, je viens d'écrire un tuto sur la question - cf. ma signature) :
Citation : candide
Jamais su ce qu'était la difficulté d'un sudoku, si tu as une explication rationnelle, je suis preneur, faut dire que j'ai jamais vu en le sudoku qu'un problème de brute force ...
Effectivement, il n'existe pas de méthode formelle pour déterminer la difficulté d'un sudoku. Néanmoins, on peut intuitivement établir une certaine hiérarchie. cf. ici.
Citation : candide
Citation : Marc Mongenet
En tout cas j'ai fait un solveur ''brute force'', et sur une grille difficile (trouvée sur Internet), il peut tourner un jour sans trouver de solution. Un algorithme ''brute force'' ne m'apparaît pas comme une solution pratique au sudoku.
Je suis très étonné, je n'ai jamais trouvé de grille y compris dans les diaboliques qui ait résisté plus de 5 secondes sur mon PC de 2001, y compris parmi les grilles qui contiennent le plus petit nombre possible de cases remplies. Mon solveur en plus n'est pas du tout optimisé, le backtracking n'est même pas gourmand. Donc je serais curieux de pouvoir essayer ta grille ou une autre que ton solveur met longtemps à résoudre.
Je viens d'en essayer dans la liste des exceptionnellement difficiles et mon solveur les traite en quelques millisecondes ou centièmes de seconde (donc il faut comprendre exceptionnelement difficile pour un raisonnement humain). Le seul qui résiste vraiment est celui qualifié de "Near worst case" : il tient onze secondes mais il a été construit pour justement être difficile à être résolu par backctraking.
Citation : candide
Citation : Marc Mongenet
Un algorithme ''brute force'' ne m'apparaît pas comme une solution pratique au sudoku.
C'est pas impossible parce que pour faire une exploration complète, si on a vraiment pas de chance, on est obligé d'explorer l'arbre très en profondeur ce qui peut être très couteux et même inaccessible.
Je ne suis pas d'accord : tant que l'on parle d'une grille "classique" (9x9 cases), un backtracking pas trop bourrin peut résoudre n'importe quelle grille extrêmement rapidement (cf. mon tuto)... Il s'agit de faire les bons choix à chaque étape, l'arbre d'exploration sera alors très réduit.
En revanche, si on passe au niveau supérieur (16x16, voire pire 25x25), là le backtracking habituel est clairement hors-jeu. Il faut utiliser des méthodes plus élaborées, comme un algo basé sur les DLX.
Citation : candide
Je ne connais pas d'autres méthodes que de partir d'une grille pleine, de retirer des cases, d'utiliser un solveur et de voir combien il te génère de grilles. Il faut donc que ton solveur soit très rapide sinon la génération sera lente.
Pareil que toi, ca me semble le plus simple. Mais il suffit de tester s'il y a plus d'une solution (donc de terminer sans énumérer toutes les solutions). Et c'est plutôt efficace : un programme utilisant un backtracking "optimisé" génère chez moi 200 grilles en moins de deux secondes...
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.