Une solution SVP!

**ginoovy** · 07/10/2007, 14h00

Bonjours tous le monde.
SVP j'aime avoir votre aide pour cet exercice en C++

Voila:

On considère un échiquier carré de taille N*N. On dispose de N reines. Le problème consiste à placer les N reines de façcon à ce que deux reine quelconque ne s'attaquent pas mutuellement. Rappelons qu'une reine attaque sur les lignes, colonnes et les diagonales. On utilisera un tableau dynamique à deux dimentions d'entiers. Onutilisera les valeurs suivantes:

0: pour indiquer une case libre.
1: pour indiquer une case interdite.
y: pour indiquer une caseoccupée par la reine numéro y (y = 1..n)

Le principe de base de l'algorithme pour placer une reine est le suivant: l'orcequ'on place une reine dans une case libre ( contenet 0), on change sa valeur vers le numéro de reine et on interdit toutes les cases se trouvant sur la même ligne, même colonne et les diagonales ( en changeant leurs valeurs respectives vers 1.
-------
- Formulez le probléme d'une manière récursive (

)
- Un algorithme récursif permettant de placer une reine sur un échiquier.

- Un algorithme récursif permettant de placer toutes les reines sur un échiquer. ( un alogorithme devra chercher au moin une solution possible).

NB. la taille de l'échiquier N et un nombre variable à saisir

Merci bien

**bolhrak** · 07/10/2007, 14h22

Bonjour,

1] Ce forum n'est pas là pour faire tes devoirs
2] Ce problème est un classique déjà traité maintes et maintes fois, une recherche sur Google devrait te donner tous les renseignements que tu cherches
3] Si ce post est là juste pour le sondage, alors désolé pour les 2 remarques précédentes, pas la peine d'en tenir compte.
4] Si tu butes sur certains aspects de la résolution, que ce soit algorithmique ou au niveau du langage, décris nous le pb ici on se fera un plaisir de te répondre. Mais tu n'auras pas de solution toute faite.

Pour le sondage, dans la mesure où c'est un classique on peut plus vriament apprécier sa difficulté

**ginoovy** · 16/10/2007, 12h59

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
 
#include<stdio.h>
#include<conio.h>
#include<stdio.h>
/*---------------déclaration_fonctions----------------*/
void cherche(int col);
void raser(int i, int j);
void supprimer(int i, int j;
void affich_tab(void);
int** allouer_chiquuier(void);
/*---------------variables_globales----------------*/
int **ech, *tab;
const dim=5;
/*---------------fonction_principale----------------*/
void main()
{
    int i,j;
    //clrsrc();
    tab=(int*)malloc(dim*sizeof(int)); /*allocation dyn du tab qui contient les
                                   resultats*/
 
    ech=allouer_echiquier(); /*alloca dyn echiquier*/
 
    for(i=0; i<dim; i++)
        for(j=0; j<dim; j++)
            ech[i][j]=dim;
 
    cherche(0);
    printf("fin programme");
    getch();
}
 
/*---------------definition_fonctions_----------------*/
 
int** allouer_echiquier(void)
{
    int i;
    ech=(int**)malloc(dim*sizeof(int*));
 
    for(i=0; i<dim; i++)
        *(ech+i)=(int*)malloc(dim*sizeof(int));
     return(ech);
}
void cherche(int col)
{
    int i;
 
    if(col=dim-1) 
    {
        for(i=0; i<dim;i++)
            if(ech[i][col]==dim)
            {
                tab[col]=i;
                affich_tab();
            }
    }
 
    else
    {
        for(i=0; i<dim;i++)
        {
            if(ech[i]col]==dim
            {
                tab[col]=i
                raser(i,col)
                recherche (col+1)
            }
            supprimer(i col)
        }
    }
}
 
void raser(int i intj)
{
    int l,c;
 
    for(c=j+1);c<dim;c++)
        if(ech[i][c]>j)
            ech[i][c]=j
 
    for(l=j+1, c=j+1; 1<dim; l++, c++ )
        if(ech[l][c]>j)
            ech[l][c]=j
 
    for (l=i-1,c=j+1; l>=0; l--,c++)
        if(ech[l][c]>j)
            ech[l][c]=j;
}
 
void affich_tab(void)
 
{
    int i;
    printf("solution");
    for(i=0;i<dim;i++)
    printf("(%d%d)",tab[i],i);
    printf("\n");
 
getch();
}
void supprimer (int i, int j)
 
{
    int l,c;
 
    for(c=j+1; c<dim;c++)
        if(ech[i][c]==j)
            ech[i][c]=dim;
 
    for(l=i+1,c=j+1); l<dim; l++,c++)
    if(ech[l][c]==j)
        ech[l][c]=dim;
 
    for(l=i-1,c=j+1;1>=0;l--,c++)
        if(ech[l][c]==j)
            ech[l][c]=dim;
}