Problèmes des n reines sur un echiquier n *n
Résolu
pipleton
Messages postés
27
Statut
Membre
-
ccm81 Messages postés 11033 Statut Membre -
ccm81 Messages postés 11033 Statut Membre -
Bonjour,
Je dois réaliser un échiquier 4 * 4 dans lequel je dois placer une reine par colonne. Ensuite je dois calculer le nombre de conflit présent dans l'échiquier. Je m'explique une reine peut se déplacer en ligne, colonne ou diagonale. Chaque déplacement possible compte pour 1 ( soit le conflit).
Ainsi, l'échiquier (R = reine, 0 = pions) ci dessous possède 5 conflits.
R 0 R 0
0 R 0 R
0 0 0 0
0 0 0 0
J'ai réussi à implémenter l'échiquier ci dessus mais je n'arrive pas a calculer le nombre de conflits. En effet, si je ne compte pas les diagonales j'arrive à 4 ce qui est normal mais lorsque je compte les diagonales j'arrive à 6. En effet, il me compte deux fois la même prise! J'ai bien essayé une condition composé mais rien n'y fait! Par la suite l'échiquier sera généré aléatoirement (mais la ce n'est pas la question!). Pouvez vous m'aider?
Voici l'algorithme
#include <stdio.h>
#include <stdlib.h>
int main()
{
//partie déclarative
int tableau[4][4] = {{1,0,1,0},
{0,1,0,1},
{0,0,0,0},
{0,0,0,0}};// 0=pion, 1 = reine
int i,j,conflit;
//calcul du nombre de prise
conflit = 0;
//pour chaque ligne
for(i=0;i<4;i++){
//pour chaque colonne
for(j=0;j<4;j++){
if(tableau[i][j]==1)
{
if(tableau[i][j+1]==0)
{
conflit = conflit +1;
}
if(tableau[i+1][j+1]==0)
{
conflit = conflit +1;
}
}
}
}
printf("%s %d","H="conflit);
return 0;
}
Je dois réaliser un échiquier 4 * 4 dans lequel je dois placer une reine par colonne. Ensuite je dois calculer le nombre de conflit présent dans l'échiquier. Je m'explique une reine peut se déplacer en ligne, colonne ou diagonale. Chaque déplacement possible compte pour 1 ( soit le conflit).
Ainsi, l'échiquier (R = reine, 0 = pions) ci dessous possède 5 conflits.
R 0 R 0
0 R 0 R
0 0 0 0
0 0 0 0
J'ai réussi à implémenter l'échiquier ci dessus mais je n'arrive pas a calculer le nombre de conflits. En effet, si je ne compte pas les diagonales j'arrive à 4 ce qui est normal mais lorsque je compte les diagonales j'arrive à 6. En effet, il me compte deux fois la même prise! J'ai bien essayé une condition composé mais rien n'y fait! Par la suite l'échiquier sera généré aléatoirement (mais la ce n'est pas la question!). Pouvez vous m'aider?
Voici l'algorithme
#include <stdio.h>
#include <stdlib.h>
int main()
{
//partie déclarative
int tableau[4][4] = {{1,0,1,0},
{0,1,0,1},
{0,0,0,0},
{0,0,0,0}};// 0=pion, 1 = reine
int i,j,conflit;
//calcul du nombre de prise
conflit = 0;
//pour chaque ligne
for(i=0;i<4;i++){
//pour chaque colonne
for(j=0;j<4;j++){
if(tableau[i][j]==1)
{
if(tableau[i][j+1]==0)
{
conflit = conflit +1;
}
if(tableau[i+1][j+1]==0)
{
conflit = conflit +1;
}
}
}
}
printf("%s %d","H="conflit);
return 0;
}
15 réponses
Résumé de la discussion
Échiquier 4x4 avec une reine par colonne et calcul des conflits où chaque déplacement compte pour 1, en incluant les diagonales, ce qui peut entraîner un double comptage.
Plusieurs personnes discutent de méthodes, des explications du raisonnement jusqu’aux algorithmes comptant les attaques en ligne, colonne et diagonale, puis divisant par 2 pour éviter le double comptage.
Des échanges présentent des exemples et résultats variables selon l’ordre de comptage, avec des morceaux de code montrant des tentatives et des remises en cause du calcul diagonale.
D’autres commentaires évoquent des approches pratiques comme des solutions en VBA ou des vérifications par brute force, sans aboutir à une solution commune.
-
Et moi Je ne comprends pas le raisonnement employer pour arriver à ces résultats.
EDIT :
Si ont prend ton dernier exemple...
1 0 1 0
0 1 0 0
0 0 0 1
0 0 0 0
conflit = 3
Moi je verrais..
Conflit 1 > A1/B2
Conflit 2 > C1/B2
Conflit 3 > B2/A1
Conflit 4 > B2/C1
??
L'expérience instruit plus sûrement que le conseil. (André Gide)
Si tu te cognes à un pot et que ça sonne creux, c'est pas forcément le pot qui est vide. ;-)(Confucius)
NOTE : Je ne répond pas aux MP pour les questions techniques.
Ça doit se passer sur le forum pour que tous puisse y participer ou en profiter. -
re
pour comptage à la main, sur l'exemple
1 0 1 0
0 1 0 0
0 0 0 1
0 0 0 0
on note (ligne, colonne) les coordonnées
- reine (1,1) en conflit avec (1,3), et (2,2)
- reine (1,3) en conflit avec (1,1) et (2,2)
- reine (2,2) en conflit avec (1,1) et (1,3)
- reine (3,4) en conflit avec personne
donc 6 conflits orientés
et 3 conflits non orientés-
Mais entre 1/3.. Y a un pion ???
Idem pour d'autre.
Relisant sont premier poste..
Ainsi, l'échiquier (R = reine, 0 = pions) ci dessous possède 5 conflits.
Ça ne correspond pas avec ta démo ?
J'abandonne car s'il ne donne pas une explication claire tout le monde va tourner en rond.
A+ -
-
-
si !
d'ailleurs avec la sienne aussi, sauf que comme il compte les conflits orientés et donc 6+4 = 10 donc 5 conflits non orientés
le hic, c'est qu'on a du mal a savoir si c'est le comptage a la main ou l'algorithme qui lui pose pb
au passage, j'ai envoyé une demande sur "comment mettre les titres sur les axes excel 2010", et comme ça ne répond pas, est ce que tu connais?
-
-
-
mais non je suis pas d'accord si je boucle de 0 à 3 je ne fais que les valeur 0,1,2!!!
Pour mon histoire de conflit, c'est le nombre de prise possible par une reine en gros. Ainsi une reine peut se déplacer, verticalement, horizontalement et en diagonale mais ne peut pas revenir sur ses pas! Ai je été pus clair?
Merci tout de même -
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question -
bonjour a tous les trois
peut être : si pour chaque reine tu compte le nombre de conflits (orientés) , tu devrais trouver le double du total des conflits (non orientés)
bonne suite-
-
-
Je suis tout a fait d'accord avec vous.Je préfererai pour ma part compter les conflits orientés. Pour le premier echiquier je suis passé par un tableau temporaire et cela fonctionne. Par contre si je prends les echiquiers ci dessous je en trouve pas le nombre de conflit voulus! Pouvez vous m'aider?
1 0 1 0
0 1 0 0
0 0 0 1
0 0 0 0
conflit = 3
1 0 1 0
0 0 0 0
0 0 0 1
0 1 0 0
conflit = 1
Merci d'avance
je remets mon code :
#include <stdio.h>
#include <stdlib.h>
int main()
{
//partie déclarative
int tableau[4][4] = {{1,0,1,0},
{0,1,0,1},
{0,0,0,0},
{0,0,0,0}};// 0=pion, 1 = reine
int temp[4][4] = {{0,0,0,0},
{0,0,0,0},
{0,0,0,0},
{0,0,0,0}};// 0=pion, 1 = reine;
int i,j,conflit;
//affichage du tableau
for(i=0;i<4;i++){
for(j=0;j<4;j++){
printf("%d",tableau[i][j]);
}
printf("\n");
}
//calcul du nombre de prise
conflit = 0;
//pour chaque ligne
for(i=0;i<4;i++){
//pour chaque colonne
for(j=0;j<4;j++){
if(tableau[i][j]==1)
{
if(tableau[i][j+1]==0)
{
temp[i+1][j]=2;
conflit ++;
if(tableau[i+1][j+1]==0 && temp[i][j+1]!=2)
{
conflit ++;
}
}
}
}
}
printf("%s%d","H=", conflit);
return 0;
} -
re
je suis d'accord avec tes resultats sur les deux exemples ci-dessus
je ne connais pas le C++
mais une autre idée
si on compte (bestial) comme conflit une reine avec elle même ça nous fait 3 fois plus d'orientés que de non orientés et on n'a plus a s'embeter pour les plages de boucle
bon, c'est intéressant, je vais tenter en VBA -
-
-
Bonjour,
Quand tu "prend" un pion, remplacer la valeur de la case, par exemple par "S" cette case ne serait plus prise en compte.
A+ -
Tout a fait c'est ce que j'ai fait!Mais ça ne marche pas! car pour un echiquier donner suivant on doit trouver un conflit = 3 et un conflit = 1
1 0 1 0
0 1 0 0
0 0 0 1
0 0 0 0
conflit = 3
1 0 1 0
0 0 0 0
0 0 0 1
0 1 0 0
conflit = 1
Je ne comprends pas comment les trouver!
Merci d'avance -
re
tu ne comprends pas quoi
- comment on les compte sur le papier ?
- comment on programme l'histoire ? -
Bizarre mais ok. Enfin pas tout a fait puisque j'ai cru comprendre qu'elles ne pouvaient que descendre donc (1,1) ne devrait pas etre en conflit avec (2,2). De meme pour (1,3) avec (2,2).
-
Si elles peuvent descendre. Si je les laisser comprendre auparavant je m'en excuse. Mais comment peut on faire pour l'algorithme??? Parce que le miens n'a pas l'air bon, pouvez vous m'éclairer mes erreurs et m'aider à résoudre ce problème?
-
re
en VBA , ceci fonctionne (à priori)
- n est le nombre de lignes/colonnes de l'échiquier
- T est le tableau echiquier rempli de "" ou de "R"
- on ne compte que les conflits non orientés , donc en descendant (c'est finalement plus simple et moins bestial)
- à toi de traduire en CFunction NbConflits2(n As Long) As Long Dim nc As Long, li As Long, co As Long, c As Long, l As Long Dim T T = Range("echiquier").Value nc = 0 For li = 1 To n For co = 1 To n If T(li, co) = "R" Then ' conflits dans ligne li For c = co + 1 To n If T(li, c) = "R" Then nc = nc + 1 End If Next c ' conflits dans colonne co For l = li + 1 To n If T(l, co) = "R" Then nc = nc + 1 End If Next l ' conflits dans diagonale1 \ en descendant à droite l = li: c = co While l < n And c < n l = l + 1: c = c + 1 If T(l, c) = "R" Then nc = nc + 1 End If Wend ' conflits dans diagonale2 / en descendant à gauche l = li: c = co While l < n And c > 1 l = l + 1: c = c - 1 If T(l, c) = "R" Then nc = nc + 1 End If Wend End If Next co Next li NbConflits2 = nc End Function
bonne suite -
-
C'est bon j'ai enfin réussi à faire ce que je voulais!Merci de votre aide à tous
Bonne soirée ou plutot bonne nuit -
re
bon, on y est donc arrivé
tu mets le pb a resolu
bonne journée -
Salut.
Je n'ai rien compris à ton histoire de conflit...
ce qui est sur, c'est que tu fais mal ta boucle, tu va chercher les cases voisines, mais celles-ci n'existe pas (d'où peut être ton erreur).
Boucle de 0 à 3 si tu veux être juste et éviter les erreurs de débordement.
