Discussion :

[Myrne]

Bonjour,
J'ai décidé de m'initier à la programmation par contraintes et j'ai voulu essayer de réaliser un programme qui trouverait une solution au problème des reines, par backtracking.

Pour ceux qui ne connaitraient pas, le problème des reines consiste à placer N reines sur un équiquier de taille NxN sans qu'aucune ne soit menacée par les autres.

J'ai tenté de résoudre ce problème avec un échiquier de taille 8x8, mais mon programme semble tourner en rond sans me donner de réponse et je ne comprends pas pourquoi.


Mon programme:

ligneok : Vérification qu'il n'y a aucune reine sur la ligne correspondant à la case étudiée:

Code :

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

1
2
3
4
5
6
7
function ok=ligneok(placement,position)
 
if sum(placement==position)>=1
    ok=false;
else
    ok=true;
end

Diagok : Vérification qu'il n'y a aucune reine sur les diagonales associées à la case étudiée:

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
function ok=diagok(placement,p)
 
n=length(placement);
grille=zeros(n+1);
 
for i=1:n
    grille (placement(i),i)=1;
end
grille(p,n+1)=1;
 
 
for i=1:n
    %diagonale NO-SE
    if (i-placement(i)==n+1-p)
        ok=false;
        return
    end
    %diagonale SO-NE
    if (i+placement(i)==n+1+p)
        ok=false;
        return
    end
end
 
ok=true;

Affichage du résultat:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
function affichage(placement)
 
n=length(placement);
disp('solution :')
 
grille=zeros(n);
for i=1:n
    grille (placement(i),i)=1;
end
for i=1:n
    fprintf(1,'%i\t',grille(i,:));
    fprintf(1,'\n')
end

Algorithme de backtrack:

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
 
function ok=positionvalide(placement,colonne)
 
    %fin de l'equiquier atteinte.
    if colonne==9
        affichage(placement);
        ok = true;
        return;
    end
 
    %cas général
    for position=1:9
        if ligneok(placement,position) && diagok(placement,position)
            placement=[placement position]
%             pause()
            if positionvalide(placement, colonne+1)
                ok=true;
                return;
            end
        end
    end
    placement=placement(1:end-1);
    ok=false;
    return

Main.m

Code :

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

1
2
3
4
colonne=1;  %initialisation
placement=[];
 
positionvalide(placement,colonne);

dans l'algo de backtrack, j'ai volontairement laissé l'affichage de la ligne "placement=[placement position]" afin de voir l'évolution de la recherche, et je vois mon code tourner en rond avant de s'arrêter:

placement =
1 3 5 7 2 4
placement =
1 3 5 7 2 4 6
placement =
1 3 5 7 2 4 6
placement =
1 3 5 7 2 4
placement =
1 3 5 7 2 4 6
placement =
1 3 5 7 2 4 6

Si quelqu'un savait me dire pourquoi mon programme tourne en rond alors que normalement avec la boucle "for" il ne devrait pas pouvoir tester plusieurs fois la même branche, cela m'arrangerait beaucoup.

Mon programme n'étant quasiment pas commenté, n'hésitez pas à me poser des questions si vous ne saisissez pas ce que j'ai voulu faire.

Merci d'avance !

[Franck Dernoncourt]

Il y avait un problème dans l'algorithme de backtrack, voici la version corrigée :

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
function ok=positionvalide(placement,colonne)
 
    %fin de l'equiquier atteinte.
    if colonne==9
        disp('ok');
        placement
        ok = true;
        return;
    end
 
    %cas général
    for position=1:8
        if ligneok(placement,position) && diagok(placement,position)
            placement_temp = [placement position];
            if positionvalide(placement_temp, colonne+1)
                ok=true;
                return;
            end
        end
    end
    placement=placement(1:end-1);
    ok=false;
    return

[Franck Dernoncourt]

Note de coding style pour ligneok, mieux vaut écrire cela :

Code :

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

1
2
function ok=ligneok(placement,position)
ok=not(sum(placement==position)>=1);

[Jerome Briot]

Code :

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

1
2
function ok=ligneok(placement,position)
ok=not(sum(placement==position)>=1);

Code :

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

1
2
function ok=ligneok(placement,position)
ok = sum(placement==position)<1;

ou :

Code :

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

1
2
function ok=ligneok(placement,position)
ok = ~any(placement==position);

ou

Code :

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

1
2
function ok=ligneok(placement,position)
ok = all(placement~=position);

[Franck Dernoncourt]

ah oui, je n'avais même pas lu la condition, c'est juste le branchement qui m'avait fait tilter

[Myrne]

Merci pour ces commentaires, en effet ça fonctionne maintenant.
Mais j'ai du mal à comprendre pourquoi :/

Je m'étais planté sur le nombre de lignes, ça je comprends tout à fait, mais c'est le rôle de placement_temp que je ne suis pas sûr de comprendre.

Si j'ai bien suivi, mettons que n reines soient placées.

Ce que faisait mon programme:
Il vérifie pour la n+1eme reine que le placement est possible, s'il ne l'est pas, il supprime cette n+1eme reine de la variable position, ce qui fait que ça tournait en rond.

Ce que fait la version corrigée par Franck:
Il vérifie pour la n+1eme reine que le placement est possible, et s'il ne l'est pas il supprime la n-eme reine, ce qui fait que l'on passera bien à la branche suivante.

J'ai bon ?

[Franck Dernoncourt]

Le problème était que ton backtrack était trop tardif : regarde cette vversion, tu comprendras mieux. (simple déplacement de la ligne placement=placement(1:end-1); par rapport à ta version). J'avais utilisé placement_temp par simplicité.

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
function ok=positionvalide(placement,colonne)
 
    %fin de l'equiquier atteinte.
    if colonne==9
        placement
        ok = true;
        return;
    end
 
    %cas général
    for position=1:8
        if ligneok(placement,position) && diagok(placement,position)
            placement=[placement position];
%             pause()
            if positionvalide(placement, colonne+1)
                ok=true;
                return;
            end
            placement=placement(1:end-1);
        end
    end
 
    ok=false;
    return

[Myrne]

OK je comprends mieux ! Merci pour ton aide !