Bonjour,
je suis débutant en CamL (et en informatique en général), et je cherche à m'entraîner avec quelques problèmes amusants. Celui que je considère ici est le tour du cavalier. Le but est d'accéder une et une seule fois (à savoir, au moins une fois, et pas deux fois) sur chaque case d'un échiquier de taille n*m (n est le nombre de lignes, et m celui de colonnes), avec un cavalier. Un cavalier est une pièce qui se déplace en L. Dans l'absolu, il a 8 déplacements possibles (cliquer ici pour plus d'informations).
J'impose de plus que la dernière case soit en communion avec la première, i.e. qu'on puisse accéder à la dernière case depuis la première, afin que ça forme une boucle (un "tour", d'où le nom du sujet).
J'ai déjà un peu (beaucoup)réfléchi à l'algorithme et à la programmation, mais je vais pas tout vous écrire d'un coup, sinon vous allez avoir peur et vous allez pas m'aider :-).
Je vous donne néanmoins mes idées générales :
- je numérote les case de l'échiquier de 1 à p=n*m (je commence en bas à gauche, et je numérote de gauche à droite, et en montant d'une ligne et en recommençant à gauche dès que je suis arrivé à la fin d'une ligne. Exemple pour n=2 et m=3 :
456
123
)
- j'utilise la méthode du programme intelligent, qui revient en arrière si la configuration envisagée n'aboutit pas, et essaye une autre voie.
- je crois qu'on peut montrer mathématiquement qu'il vaut mieux choisir en premier les cases qui ont le moins de cases accessibles, je vais donc inclure cela dans ma programmation (cela devrait alourdir les calculs mais réduire grandement le nombre de cas à étudier, et donc peut-être au final gagner du temps, bien que je n'aie fait aucun calcul de complexité temporelle à ce niveau-là).
Voilà pour l'idée générale de mon programme.
Je vais de suite écrire mes premières procédures, mais dans un autre post.
Je suis bien sûr ouvert à toutes remarques concernant l'algorithme, mais, à moins d'une grande opposition de votre part, c'est celui que j'adopterai, car j'y ai déjà pas mal réfléchi et ai écrit déjà pas mal de lignes de code, que j'aimerai partager avec vous, pour que vous les corrigiez si besoin.
Merci d'avance de vous intéresser à mon sujet.
Partager