Astuce 8Reines en C
Andrea1457
-
arthurik Messages postés 166 Date d'inscription Statut Membre Dernière intervention -
arthurik Messages postés 166 Date d'inscription Statut Membre Dernière intervention -
Bonjour,
SVP avez vous un indice pour realiser un prog qui calcule les possibilités pour le probleme des 8 reines ??
Je voudrais juste savoir c'est quoi la logique qu'il faut suivre pour placer les 8 dames corrctement sans choisir les positions a l'aléatoire puis verifier
Merciii pour votre aide c 1 projet en C
SVP avez vous un indice pour realiser un prog qui calcule les possibilités pour le probleme des 8 reines ??
Je voudrais juste savoir c'est quoi la logique qu'il faut suivre pour placer les 8 dames corrctement sans choisir les positions a l'aléatoire puis verifier
Merciii pour votre aide c 1 projet en C
A voir également:
- Astuce 8Reines en C
- Astuce clavier iphone - Guide
- Astuce whatsapp écriture - Guide
- Telecharger mp3 youtube astuce - Guide
- Astuce gta 6 - Guide
- Wii sport tennis astuce ✓ - Forum Wii
4 réponses
Salut,
Aléatoirement, cela ne sera pas acceptable à cause de la composante temps.
Par contre, tu peux tester en mettant la dame en case A1, puis une autre en B3 (B2 est impossible à cause de la première dame). Etc.
Dis autrement, tu parcours toutes les possibilités pour chacune des lignes, et avant de poser la dame, tu regardes si elle peut s'y mettre, si oui, tu passes à la ligne suivante, sinon, tu testes une autre possibilité pour la ligne courante.
Maintenant que tu vois le principe, l'algorithme devrait venir tout seul ;-))).
Aléatoirement, cela ne sera pas acceptable à cause de la composante temps.
Par contre, tu peux tester en mettant la dame en case A1, puis une autre en B3 (B2 est impossible à cause de la première dame). Etc.
Dis autrement, tu parcours toutes les possibilités pour chacune des lignes, et avant de poser la dame, tu regardes si elle peut s'y mettre, si oui, tu passes à la ligne suivante, sinon, tu testes une autre possibilité pour la ligne courante.
Maintenant que tu vois le principe, l'algorithme devrait venir tout seul ;-))).
Salut, déja pour placer 8 dames, il faut savoir que il faut mettre comme les cases dans lesquelles les cavalier s'attaques, c'est à dire la différence horizontale doit etre 2 celle de verticale : 1, ou bien horizontale doit etre 1 celle de verticale 2.
Il faut savoir que la première dame peut avoir une possibilité de se placer dans 64 cases, elle aura occupé une colonne et une ligne, ausi une diagonale. Si tu sait exactement ou se place ta dame tu peut en deduire le nombre de cases restantes, et tu fait ça pour les 7 autres dames, apres tu fait la meme chose pour une case de départ.
Conseil: il faut au début prendre des variables pour chaque dame, exemple cases libres (non attaquées par une autre dame) ça te fait une part de possibilté nombre de possibilité vu que à la fin on aura une positio sempblable pou les dames, sauf on aura déplace par exemple 4 eme colonne en 3eme, et si rechange on doit revenir à la meme position.
Il faut savoir que la première dame peut avoir une possibilité de se placer dans 64 cases, elle aura occupé une colonne et une ligne, ausi une diagonale. Si tu sait exactement ou se place ta dame tu peut en deduire le nombre de cases restantes, et tu fait ça pour les 7 autres dames, apres tu fait la meme chose pour une case de départ.
Conseil: il faut au début prendre des variables pour chaque dame, exemple cases libres (non attaquées par une autre dame) ça te fait une part de possibilté nombre de possibilité vu que à la fin on aura une positio sempblable pou les dames, sauf on aura déplace par exemple 4 eme colonne en 3eme, et si rechange on doit revenir à la meme position.
Cela est la façon intelligente de faire, c'est-à-dire ce que ferait un humain pour trouver une solution.
La machine n'a pas cette faculté à moins d'implanter un module d'IA.
Pour résoudre ce problème, la solution classique est de tout tester toutes les solutions jusqu'à en trouver une qui marche. Après, il est bien sûr possible d'améliorer via des heuristiques. Mais vu le nombre de combinaisons différentes (8^8), cela n'apportera rien.
La machine n'a pas cette faculté à moins d'implanter un module d'IA.
Pour résoudre ce problème, la solution classique est de tout tester toutes les solutions jusqu'à en trouver une qui marche. Après, il est bien sûr possible d'améliorer via des heuristiques. Mais vu le nombre de combinaisons différentes (8^8), cela n'apportera rien.
Il faut aussi savoir que les machines sont là pour nous aider à faire des calculs, mais à nous aussi trouver des logiques. Il faut partir d'un exemple simple. Imaginons que ça soit des tours, on ne peut pas dire que c'est aussi difficile que pour les dames. Et bien les dames sont les tours et les foux au meme temps.
Effectivement, pour les problèmes de classe NP, il est important de bien réfléchir sur la logique du problème (cf. problème du voyageur de commerce). L'usage de réseau de neurones de type Boltzmann est à considérer.
Mais ici, il s'agit d'un problème de classe P. Dans ce cas où la complexité de l'algorithme est polynomiale, le brute-force est à tester de prime abord. Si cela met trop de temps, tu ajoutes des heuristiques jusqu'à trouver un temps convenable (mais ici pas besoin car 8 puissance 8 ne vaut rien pour une machine). C'est d'ailleurs cette solution qui est utilisée pour les IA dans les jeux d'échecs.
Mais ici, il s'agit d'un problème de classe P. Dans ce cas où la complexité de l'algorithme est polynomiale, le brute-force est à tester de prime abord. Si cela met trop de temps, tu ajoutes des heuristiques jusqu'à trouver un temps convenable (mais ici pas besoin car 8 puissance 8 ne vaut rien pour une machine). C'est d'ailleurs cette solution qui est utilisée pour les IA dans les jeux d'échecs.
