Jeu des 8 reines

Soyez le premier à donner votre avis sur cette source.

Vue 8 442 fois - Téléchargée 12 154 fois

Description

Bon, à la base, c'est comment placer 8 reines sur un échiquier de tel façon qu'aucune reine n'en mangent d'autres.
En voilà une solution pour un échiquier de côté n avec n reines.

Evidemment, plus c'est gros, plus c'est long...
l'aperçu présente la solution pour 30 reines (environ 3 Min de calcul sur un 2 GHz / 768 Mo Ram)

Le code est archi simple, c'est pour les gens qui ne comprenne pas trop l'utilité de la récursivité

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

cs_Nono40
Messages postés
1000
Date d'inscription
mercredi 3 avril 2002
Statut
Membre
Dernière intervention
12 septembre 2006
1 -
Ce qui aurait été cool, c'est de mettre le code qui fonctionne dans le zip...

D'autre part essaye de soigner l'indentation, car c'est très dur à relire ton programme...

Voici la procédure corrigiée pour ceux qui la souhaitent :
function place(h,c:integer):boolean;
var
i,k:integer;
ok:boolean;
begin
result:=false;
// on place la reine
d[c]:=h;
// si on est à la dernière colonne, c'est bon
If c=n Then
begin
result:=true;
Solution:=True;
Exit;
end
Else
Begin
// sinon, on essaie de placer une reine sur la colonne suivante
For i:=1 To n do
begin
ok:=True;
k:=1;
While (k<=c)And OK Do
Begin
// (il y a forcément personne sur la colonne)
// y-a-t'il quelqu'un sur la même ligne ?
if d[k] = i Then ok:=False Else
// y-a-t'il quelqu'un sur une diagonale ?
if (c + 1 - k) = (i - d[k]) Then ok:=False Else
// y-a-t'il quelqu'un sur l'autre diagonale ?
if (k - c - 1) = (i - d[k]) Then ok:=False;
// on stop si on a fini le parcour ou si une autre reine est présente
inc(k);
End;
// si c'est ok, on place la reine et on continue
if ok Then
if place(i, c + 1) then
Begin
Result:=True;
exit;
End;
end;
End;
end;
Comme le dis nono40 , on aurait préféré le bon code !!

Merci à toi nono pour avoir corrigé cette procedure.
Mais l'ennui, c'est qu'il y a des problèmes :
- le tableau d n'est plus déclaré avec ta methode.
- Solution est un boolean je suppose. c'est le même ou un autre que OK ???
- Même en déclarant d et Solution, le programme ne marche pas : il met toutes les dames dans une même diagonale...

Au fait, je ne suis pas sûr que cela soit possible de metre 8 dames sur un echiquier car il faut au maximum 1 dame par ligne et par colonne. Avec la dame qui prend en diagonale, il y a forcément un moment (la 8eme dame precisément) ou il ne restera qu'une colonne et qu'une ligne pour la placer sans se faire prendre en ligne ni en colonne. Le probleme, c'est que sur cette unique case, une dame est forcément présente dans une diagoanle et celle-ci, elle ne la ratera pas !!!

Bref, c'est pas gagné.

PS : nono si chez toi ca marche, tu pourrais poster une source avec le prog complet qui fonctionne : je suis curieux de voir comment tu t'es pris.

@ ++ Florent
cs_Nono40
Messages postés
1000
Date d'inscription
mercredi 3 avril 2002
Statut
Membre
Dernière intervention
12 septembre 2006
1 -
La déclaration des variables modifiée :
var
n:integer;
d:tdam;
Solution:Boolean;

Et la procédure OnClick ( seul le début est modifié ) :
procedure TForm1.Button1Click(Sender: TObject);
var
i,j:integer;
begin
n:=spinedit1.Value;
//on essaye de placer la première reine sur une des cases de la première colonne
Solution:=False;
For i:=1 To (n+1) Div 2 Do If PLace(i,1) Then Break;
If Not Solution Then
Begin
ShowMessage('Pas de solution');
Exit;
End;

image1.Canvas.Brush.Color:=clwhite;
[...]


Il y a bien une solution pour 8 cases.
cs_barbichette
Messages postés
243
Date d'inscription
lundi 30 octobre 2000
Statut
Membre
Dernière intervention
15 juillet 2013
-
je reviens après 4 ans... pour ajouter un algorithme très rapide et très simple pour trouver une solution à se casse-tête.

Pour plus d'information sur cet algorithme, consultez la page de wikipédia :
http://fr.wikipedia.org/wiki/Huit_dames

procedure TForm1.Button1Click(Sender: TObject);
var
n,i,j:integer;
reste:integer;
place:array of integer;
begin
n:=spinedit1.Value;
if n<4 then exit;
setlength(place,n);
reste:=n mod 12;
case reste of
3,9:
begin
for i:=1 to n div 2-1 do place[i-1]:=i*2+2;
for i:=2 to (n-1) div 2 do place[n div 2+i-2]:=i*2+1;
place[n div 2-1]:=2;
place[n-2]:=1;
place[n-1]:=3;
end;
2:
begin
for i:=0 to n div 2-1 do place[i]:=i*2+2;
for i:=3 to (n-1) div 2 do place[n div 2+i-1]:=i*2+1;
place[n div 2+0]:=3;
place[n div 2+1]:=1;
place[n-1]:=5;
end;
8:
begin
for i:=0 to n div 2-1 do place[i]:=i*2+2;
for i:=0 to (n-1) div 2 do
if i and 1=0 then place[n div 2+i]:=i*2+3
else place[n div 2+i]:=i*2-1;
end;
else
for i:=0 to n div 2-1 do place[i]:=i*2+2;
for i:=0 to (n-1) div 2 do place[n div 2+i]:=i*2+1;
end;

image1.Canvas.Brush.Color:=clwhite;
for j:=0 to n-1 do
for i:=0 to n-1 do
image1.Canvas.Rectangle(image1.Width*i div n,image1.Height*j div n,image1.Width*(i+1) div n,image1.Height*(j+1) div n);

image1.Canvas.Brush.Color:=clred;
for i:=1 to n do
image1.Canvas.Rectangle(image1.Width*(i-1) div n,image1.Height*(place[i-1]-1) div n,image1.Width*i div n,image1.Height*place[i-1] div n);
end;

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.