Bonsoir,

Je viens a vous car j'ai besoin d'aide pour un programme que je dois faire pour demain, et vu mon niveau assez faible en programmation, je ne sais pas comment faire

Le but du programme est de trouver une solution au N Queen problem ou il faut placer le maximum de reines possible sur une table d'echec ayant NxN pour dimensions sans que les reines puissent d'attaquer. Sauf que ici, on a le droit de placer des pions sur l'échequier au départ, et on doit prendre en compte le placement des pions pour placer nos reines.

C'est comme le problème du N Queen sauf qu'on y ajoute une contrainte au départ qui sont les pions.

L'entrée du programme contient d'abord un nombre n définissant les dimensions de l'echecier ( ex: 5 signifie 5x5 etc..) suivie de n lignes qui définissent l'état initial de l'échecier. Soit la lettre "v" pour vide, soit p signifint qu'il y a un pion sur cette case. La sortie du programme doit etre le nombre maximum de reines qui peuvent etre placées sur l'echecier.

Par exemple, pour l'entrée suivante:

3
eee
eee
eee

La sortie sera: 2

J'ai essayé d'expliquer le mieux possible, je pense que c'est assez clair.

Merci!

Le plus simple et bourrin à mettre en œuvre pour résoudre ce problème et ce genre de problèmes en général est un backtracking récursif. Tu essaies de placer jusqu'à ce que oups ça ne fonctionne plus et tu rollback et explore la configuration suivante.

Je vois pas l'intérêt de "backtracker", au final tu vas juste essayer toutes les possibilités, donc ça avance à rien par rapport à l'algo naïf, c'est juste une manière de l'implémenter.

Ca ressemble plutôt à de la programmation dynamique : Quand tu places une reine, pour placer les suivantes ça revient à résoudre à nouveau ton problème sur un échiquier plus petit

lowenheim, DP marche mal sur ce problem parceque la structure du sous probleme est bizarre. Mais moralement vous dites la meme chose: fais un algo recursif qui essaye toutes les positions.

Oui la solution qu'il faut faire est d'essayer toutes les possibilités, le prof nous l'a dit vu que ce problème s'inscrit dans le cours des NP complete problems.

Par contre vous pouvez m'aider pour trouver une solution en essayant toutes les positions? J'ai pas un super niveau en progra et je sais vraiment pas comment commencer

Hmm d'accord il me semblait que justement on pouvait rajouter des pions sur les diagonales de la reine pour arriver exactement à un sous-problème du notre, mais je dois me planter alors j'y ai pas trop réfléchi

Recursivement. A l'etape i de la recursion, tu place la ieme reine syr le tableaux. Tu n;essaye que les positions ou elle peut etre.

Je peux poster mon code ici pour que vous me dites ce qui va pas svp?