Astuce 8Reines en C
Fermé
Andrea1457
-
6 déc. 2009 à 16:01
arthurik Messages postés 166 Date d'inscription dimanche 27 décembre 2009 Statut Membre Dernière intervention 22 juin 2015 - 29 déc. 2009 à 01:56
arthurik Messages postés 166 Date d'inscription dimanche 27 décembre 2009 Statut Membre Dernière intervention 22 juin 2015 - 29 déc. 2009 à 01:56
A voir également:
- Astuce 8Reines en C
- Astuce clavier iphone - Guide
- Astuce whatsapp écriture - Accueil - Messagerie instantanée
- Écrire en gras, en italique ou en barré sur WhatsApp - Guide
- Wii sport tennis astuce ✓ - Forum Wii
- Astuce roulette casino forum ✓ - Forum Réseaux sociaux
4 réponses
fiddy
Messages postés
11069
Date d'inscription
samedi 5 mai 2007
Statut
Contributeur
Dernière intervention
23 avril 2022
1 844
6 déc. 2009 à 16:07
6 déc. 2009 à 16:07
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 ;-))).
arthurik
Messages postés
166
Date d'inscription
dimanche 27 décembre 2009
Statut
Membre
Dernière intervention
22 juin 2015
14
28 déc. 2009 à 23:45
28 déc. 2009 à 23:45
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.
fiddy
Messages postés
11069
Date d'inscription
samedi 5 mai 2007
Statut
Contributeur
Dernière intervention
23 avril 2022
1 844
29 déc. 2009 à 00:29
29 déc. 2009 à 00:29
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.
arthurik
Messages postés
166
Date d'inscription
dimanche 27 décembre 2009
Statut
Membre
Dernière intervention
22 juin 2015
14
29 déc. 2009 à 00:40
29 déc. 2009 à 00:40
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.
fiddy
Messages postés
11069
Date d'inscription
samedi 5 mai 2007
Statut
Contributeur
Dernière intervention
23 avril 2022
1 844
29 déc. 2009 à 01:04
29 déc. 2009 à 01:04
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.
arthurik
Messages postés
166
Date d'inscription
dimanche 27 décembre 2009
Statut
Membre
Dernière intervention
22 juin 2015
14
29 déc. 2009 à 01:56
29 déc. 2009 à 01:56
T'as raison sauf j'essaie de montrer quelque chemins par lesquels il y a un moyen de s'approcher du but. En ce qui concerne la complexité je n'en ai guère parlé. Et aussi j'avoue que je suis d'accord avec toi. Mais je pense la question qui a été posée n'est pas du tout ça.
