Problèmes des n reines sur un echiquier n *n Résolu/Fermé

Question

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 #include 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; }

Char Snipeur · Answer

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.

enark78 · Answer

je n'ai pas compris ce que tu appelles un conflit.

pipleton · Answer

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

ccm81 · Answer

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

lermite222 · Answer

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+

pipleton · Answer

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

lermite222 · Answer

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.

ccm81 · Answer

re
tu ne comprends pas quoi
- comment on les compte sur le papier ?
- comment on programme l'histoire ?

ccm81 · Answer

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

enark78 · Answer

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).

pipleton · Answer

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?

ccm81 · Answer

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 C  


Function 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

pipleton · Answer

Merci je vais essayer! je vous tiens au courant

pipleton · Answer

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

ccm81 · Answer

re
bon, on y est donc arrivé
tu mets le pb a resolu
bonne journée

Problèmes des n reines sur un echiquier n *n

15 réponses

Discussions similaires