Trouver une heuristique

[Durand]

De tout le programme en C qui est fourni, la seule ligne que je trouve vraiment intéressante d'un point de vue algortihmique est celle de la procédure Resolve «... IF (! case_dispo_nbre(nbre,ligne,col)) continue;». En effet, c'est là que ce trouve le cerveau palpitant de l'algorithme.

Comme l'a dit un autre commentaire du forum, le maximum de combinaisons possibles sur une grille est 9!^9 soit en gros 10^50. Sur une machine qui permet d'en essayer 170.000 par secondes il faut 2x10^37 années de calcul pour les épuiser. On a vite compris que la seule chose à faire quand on écrit un programme de résolution de Sudoku est de trouver un moyen de limiter ce nombre. Tout ce qu'on pourra écrire à côté pour limiter le nombre d'appel à Resolve est à un coût nul par rapport au gain. Pour cette raison, le programme C présenté est beaucoup trop lent.

En gros, on a des cases à remplir et des chiffres à poser. Le plaisir du programmeur est de bien choisir la prochaine case à remplir et de bien choisir le prochain chiffre à y essayer. La règle absolue est de couper au maximum le nombre de branches de l'arborescence. Par conséquent on essaiera de prendre d'abord celles qui dés le départ ont le maximum de contraintes, c'est à dire le minimum de choix possibles. C'est ce qu'on appelle une heuristique. J'ai employé deux méthodes.

Mtéhode M1 - Choisir d'abord la case et ensuite le chiffre.
L'onglet sur les techniques de résolution donne une bonne mesure pour choisir la case. On maintient pour chaque case libre l'ensemble des chiffres qui ne peuvent pas s'y trouver (méthode d'inclusion décrite dans ce site) et on prend la case dont le nombre de chiffres possibles est le plus petit. A ce point, comme il y a parfois plusieurs minimums, je les trie en fonction du nombre décroissant de placement de ces chiffres. Ex : Dans une case qui peut recevoir (9, 2, 4) et qu'à ce moment on a déjà 7 fois le 2 sur la grille alors que le 9 et le 4 n'y sont que deux fois, on essayera d'abord de placer le 2.

A celà on ajoute des tests rapides de blocage futur. J'en ai trouvé deux . 1/ Lorsqu'on place le 8eme exemplaire d'un chiffre, il ne reste plus qu'une seule case pour placer le dernier. Au lieu d'attendre que la récursivité aille le visiter on peut d'emblée tester que la case correspondante est libre et économiser dans ce cas des années de calcul lorsqu'elle est occupée. 2/ Lorsqu'on place un chiffre dans une case il faut vérifier qu'il n'y a pas par ailleurs le cas précédent qui se présente. Sinon il y a un échec en perspective. Ce deuxième test s'apparente à la méthode d'exclusion décrite dans ce site.

Cette méthode est en général trés efficace. On trouve souvent la solution du premier coup, sans "backtracking". Pour la grille 7218 il faut 79 essais soit 27 de trop. Pour le Al Escargot il faut 2.844 essais.

Par contre elle est souvent trés mauvaise pour les grilles qui n'ont pas de solution.


Méthode M2 - Choisir d'abord le chiffre et ensuite la case.
Cette fois on essaye de placer les chiffres. On choisit le chiffre le plus utilisé ce qui limite les calculs futurs. On choisit ensuite la case comme précédemment.

Cette méthode est efficace pour trouver les cas d'insolvabilité. Par contre cette méthode est souvent 3,5 fois plus lente que M1 pour trouver une solution et elle échoue le plus souvent à trouver une solution en un temps raisonnable.

Je suis arrivé à la conclusion qu'un bon programme passe par l'exécution de deux processus sur M1 et M2. Le premier qui trouve ou prouve qu'il n'y a pas de solution arrête la partie. Visiblement le site utilise aussi deux méthodes distinctes pour les boutons «Solution de la grille» et «Vérifier/Solvabilité».

La grille suivante, qui n'a pas de solution, n'est pas résolue en moins de 5 minutes par le bouton «Solution de la grille», par contre elle est rapidement vérifiée.

120 000 000
000 210 000
000 000 021

200 000 010
000 021 000
001 000 002

012 000 000
000 102 000
000 000 100
---------------------

N'ayant pas écrit de programme de test du programme de résolution du Sudoku, l'appréciation que je fais du comportement des deux méthodes n'est pas trés scientifique. Est-ce que les auteurs de ce site connaissent une heuristique dont on a pu prouver l'efficacité ou est-ce qu'eux aussi ont programmé à l'intuition? J'aimerais savoir en combien d'essais ils résolvent Al Escargot.

[Julie]

Bonjour et bravo.

Vous avez parfaitement posé et décrit le problème.

Admin va répondre à ce poste.

Pour la Al Escargot avez vous essayé de passer par solution de la grille et liste des coups ?

Julie.

[admin]

Bonjour.

Vaste débat.

1) Le programme proposé en C sur le site n'est qu'un modèle de « récursivité en dur » afférent au sudoku. L'algorithme n'est uniquement que du backtracking ou méthode de retour par marche arrière. Ce code est un simple exemple et un cas d'école. Bien entendu les programmes du site fonctionnent autrement.

2) Vaut-il mieux utiliser la méthode M1 ou la méthode M2 que vous proposées, ou les deux concomitantes réparties sur deux processus ( thread ) ? Je ne sais, mais les deux systèmes me paraissent intéressant.

Les programmes du site n'utilisent pas à proprement parlé ni la M1 ou la M2. Ce qui donna cette impression fut surtout du à une erreur de ma part. En effet certaines fonctionnalités stoppaient les traitements trop long et d'autres fonctionnalités ne le faisaient pas. Merci encore pour votre avertissement.

3) Si votre interrogation est de savoir quelle serait la méthode la plus rapide pour détecter une absence de solution il me semble, après mûres réflexions, que vous avez répondu indirectement à cette question en posant cette maïeutique très pertinente «  J'aimerais savoir en combien d'essais ils résolvent Al Escargot ? » .
Suite à cette question, je me permet de penser qu'un énoncé peut-être considéré comme insoluble si le nombre de test en cours est supérieur à celui d'une Al Escargot !

*) Si on considère cette grille comme étant la plus difficile à résoudre, en particulier à cause des multiples choix multiples qu'elle présente.
*) Si on connaît le nombre maximum de tests qu'elle implique.
*) Si un énoncé dépasse largement ce nombre de tests.

Alors cet énoncé est sans solution !

Le programme du site pour résoudre une Al Escargot dépasse rarement de peu les 1.000 tests, la moyenne étant à peu près de 450. Je me permet alors de considérer qu'à partir de 5000 tests on se trouve en présence d'une grille sans solution.

Après avoir répondu à ces questions, développons :
Le sujet ci dessous ne traitera que des grilles avec des cases à choix multiples, grilles avec ou sans solution.
Il y aurait-il des méthodes plus ou moins rapides qui iraient jusqu'à la conclusion finale qu'une grille soit sans solution, sans s'arrêter à un nombre limite de tests, pour résoudre par exemple des types de grille tel que vous nous l'avez présenté ci-dessus ?
La réponse est oui, mais je pense alors que dans ce cas l'on serait confronté aux probabilités. C'est à dire à un temps moyen de résolution et non pas un temps strict de résolution. Pourquoi ?
Par ce que une grille qui imposerait des choix multiples contraindrait obligatoirement le programme à des essais aléatoires ! En effet même si un programme utilisait toujours le même ordre strict de résolution, ces résolutions passeraient obligatoirement par des chemins faisant intervenir le hasard. Pourquoi ?
Parce ce qu'il faut faire une distinction entre grilles égales, différentes et identiques.
Deux grilles différentes peuvent être identiques. Prenez une Al Escargot, faite la pivoter de 180 °. Les deux grilles sont différentes, mais identiques. Avec le même mode de résolution, le nombre de tests sera différent pour chacune d'elle par ce que le programme passera par des chemins différents.
Pour votre grille j'ai remarqué d'une manière empirique qu'en faisant varier les séquences aléatoires et en limitant le nombre de test à 15.000 pour chaque séquence aléatoire on arrivait à un temps moyen de traitement de deux secondes au lieux des cinq minutes ou plus que vous avez relevées.

Continuons le développement.
Comment détecter relativement rapidement l'absence de solution dans une grille ?
Tout d'abord en étant capable de résoudre brièvement une grille acceptant une ou plusieurs solutions.
Comment un programme peut-il résoudre au plus vite une grille acceptant une ou plusieurs solutions ?
Il me semble en imitant ou en faisant comme un être humain le ferait !
Laissons de côté les langages et les algorithmes que nous connaissons. Voyons simplement les concepts.
Face à une grille difficile imposant des choix multiples un joueur va rechercher et résoudre tout d'abord toutes les cases acceptant une solution unique. Il fera comme Monsieur Jourdain, la plupart du temps il utilisera des schémas visuels, sans savoir que neuf fois sur dix il utilisera une inclusive ou une exclusive. Faute de quoi, étant coincé à un moment donné, le joueur notera tous les candidats marqués dans les cases non résolues et il prendra ensuite une possibilité au hasard parmi une des cases ayant le moins d'alternatives. Puis le joueur continuera sa grille pareillement. Si il tombe dans «cul de sac » il reviendra en arrière avec sa gomme et passera à la possibilité suivante de la dernière case à choix multiple traitée. Que fait notre utilisateur ainsi ? Il opère des retours par marche arrière dit « backtracking » uniquement en cas de nécessité.

Les programmes du site font de même.

Cordialement.
Admin.

[alabarre06]

KD 10 Shoes
Ralph Lauren polo Shirts
The North Face Jackets
Timberland Boots
Adidas NMD Womens
NMD Adidas
Kyrie 4
Ralph Lauren Polo
Canada Goose parka
Nike Kyrie 3
Adidas Yeezy
Pandora Bracelet
KD 10 Shoes
Jimmy Choo Shoes Outlet
James Harden shoes
Pandora Jewelry 70% off Clearance
Coach Outlet Online
Ugg Boots
Tory Burch Outlet
Kyrie 3
Pandora Ring
Pandora Ring
North Face Outlet Online
Vans Shoes
Pandora UK
Ralph Lauren Polo
Valentino Shoes
Pandora Jewelry Official Site
Timberland Boots For Women
Moncler UK
Ralph Lauren Polo
Michael Kors Outlet Online