Discussion :

[george369]

Bonjour,

voici le problème à résoudre au moyen d'un programme.
On a un carré de côté 10, et dans le coin supérieur gauche on place le nombre 1.
Ensuite on a le droit de se déplacer à partir de cette case au moyen des déplacements suivants :
-> 3 cases en horizontal ou vertical
OU
-> 2 cases en diagonale.

Ainsi, à partir du 1 je peux aller 3 cases vers la droite, 3 cases vers le bas ou alors 2 cases vers le coin inférieur droit. On place alors le 2, et ainsi de suite...

Le but est de trouver une solution pour cette énigme au moyen d'un ordinateur (elle existe, il y en a au moins 2).

J'ai essayé un algorithme de force brute. Cependant selon mes estimations, celui-ci mettrait plus d'un siècle à s'exécuter.

Auriez-vous une idée, ou auriez-vous déjà entendu parler de ce genre de problème ?

[Twindruff]

C'est un problème de recherche de chemin dans un graphe, très classique, pour commencer tu peux lire une présentation sur wikipedia.

[JolyLoic]

Tel que j'ai compris le problème, le but est de passer par toutes les cases, et le problème devient alors la recherche d'un chemin hamiltonien, ce qui est NP-complet dans le cas général...