Salut !

Je viens de mettre a jour ma page sur mes programmes :
http://perso.numericable..fr/~fvirtman/progs/index.html
(En bas, les nouveautés ajoutées dans le chapitre "Projets calculatoires pour les jeux")

Je lance ce topic pour parler des différents jeux (casse tete) dont un résolveur serait sympa a programmer, pour discuter techniques, structures, et optimisations !

j´en profite pour te dire que ton jeu "papy" est vieux de 4-5 ans depuis 2 ans ^^

Lol ! en effet, je viens de corriger ça

Hé Fvirtman tu joue à trackmania ?

Pipadin > ben oui, entre midi et deux je viens de quitter il y a un quart d´heure d´ailleurs
Si tu veux en savoir plus, mail moi ou MSN moi (cf ma carte), pour ne pas pourir le topic en hors sujet

je viens de voir en cours , comment résoudre des carrés magiques si sa intéresse je peux envoyé la doc, l´algo est écrit pour le pascal mais peut facilement etre adapté.
PS: pour les carrés magiques de cotés paires c´est assez hard, tandis que pour les impaires c´est trés trés facile.
adnX59@hotmail.com

tiens, ce topic va m´interresser je crois , alors pour les techniques :

La seule que je connaisse est celle par les arbres mais il existe diverse variante des arbes pour les resolveurs, en ce qui concerne les plus optimisé (j´entends par là, les plus rapide) j´ai entendu parler du BackTracking mais j´ai pas eu le temps de trop regarder encore .

C´est simple l´idée du back tracking, c´est de descendere dans un arbre de coup et a un moment, tu te dis, ´ah bah non. Ce n´était pas ca". alors tu remonte et tu regardes autre chose.

godrik >
Est ce que ça se base sur des heuristiques ?
Sinon, je pense que j´ai utilisé du backtracking malgré moi pour le sudoku par exemple :
je choisis une case libre, je met un chiffre dedans, si ce chiffre rend le sudoku invalide (par exemple je place un 9, et il y a déja un 9 sur la meme ligne), alors je n´explore pas la branche, voir si aucun des chiffres que j´essaie de placer est valide, alors je remonte.

voila, c´est un backtracking.
Ton back tracking peut etre optimal ou heuristique. SI tu es sur que la solution qui t´interesse n´est pas dans le sous arbre que tu es entrain de considerer alors il est optimal. Si tu n´es pas sur, alors tu es dans le monde de l´heuristique.

Rappelons qu´une heuristique ca veut juste dire: "je ne suis pas sur que ce soit le meilleur choix"

ok ok je vois , mais bon ce genre d´algo doit tendance à être lent je pense, déjà car c´est basé sur la technique de recherche d´arbre de plus (je pense aussi) que dans la plus part des cas on passe par les heuristiques ce qui reste assez lourd au niveau des possibilités et recherche.

Le BackTracking peut etre pas mal pour des petits jeux ou il y a pas beaucoup de branche mais si on augmente le nombre de branche de l´arbre, reste il un algo rapide ? ou existe il d´autre algo plus optimal ? (pas forcement basé sur les arbres)

En tous cas merci godrik pour les éclaircissements ;)

Les algorithmes de parcours de toutes les possibilité ont l´avantages d´être générique. Ca marche sur tous les problemes. Ca donne toujours la meilleures solution.

Selon les problemes, ca pourrait meme ne pas etre tres compliqué. Quand tu cherches le plus petit element d´un tableau, tu les regardes tous. Et tu ne peux pas le faire plus vite.

Apres des jeux pour lesquels il faut regarder toutes les solutions il y en a un paquet: sokoban, les n reines, ... Enfin, quand je dis que l´on est obigé, il y a des algorithmes qui font autrement mais qui reste "aussi lourd".
Ces problemes sont connu des théoriciens comme étant NP-complet. Grosso modo, ca veut dire qu´il n´existe pas d´algorithmes polynomial (a comprendre simple) pour le résoudre. Donc le meilleur algorithmes que l´on connaisse pour ces problemes la est en k^{quelque chose de l´instance} (k constant). Apres ce ´quelquechose de l´instance´ peut varier selon les méthodes que l´on utilise. par exemple sur le problemes des n reines, on peut ´facilement´ tomber de 2^(n^2) a 2^(n/2). C´est toujours exponentiel, mais c´est quand meme beaucoup plus petit.

Toutes les méthodes a base d´arbre non naive utilise du backtracking ou des techniques similaire.