échiquier
bonjour les mathématiciens
je vous écris car j'ai un ami qui m'a posé une énigme et j'avoue que je n'arrive pas à la résoudre!
voici l'énigme : Sachant que huit dames sont placées sur un échiquier,quel est le nombre maximal de cases non controlées par une dame ?
j'ai essayé de le résoudre avec mon échiquier mais j'avoue ne pas y arriver!
quelqu'un aurait une idée?
je vous écris car j'ai un ami qui m'a posé une énigme et j'avoue que je n'arrive pas à la résoudre!
voici l'énigme : Sachant que huit dames sont placées sur un échiquier,quel est le nombre maximal de cases non controlées par une dame ?
j'ai essayé de le résoudre avec mon échiquier mais j'avoue ne pas y arriver!
quelqu'un aurait une idée?
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
or, je crois que 8 est justement le nb maximal de dame qu'on peut placer sur un echiquier sans que l'une d'elle n'en menace une autre. ce qui est logique vu qu'il n'y a que 8 lignes/colonnes.
Il n'est pas dit que les dames ne sont pas en prise.
Cordialement
NB : Avec des tours, c'est facile, on les met dans un coin, mais les dames contrôlent en diagonale..
en tout cas merci de votre réponse!
ce n'est pas l'enigme classique du jeu des 8 dames!
C'est une autre énigme!
du coup la réponse de jobherzt est -elle encore valable?
ceci dit, en fait, etant donné qu'une dame couvre une ligne te une colonne, placer 8 dames n'importe comment courvira toujours tout l'echiqiuer.
je ne trouve pas d'autre solution que la réponse 0!
\[
\begin{array}{cccccccc}
. & D & . & . & . & . & D & . \\
D & . & . & . & . & . & . & D \\
. & . & . & . & . & . & . & . \\
. & . & . & . & . & . & . & . \\
. & . & . & . & . & . & . & . \\
. & . & . & . & . & . & . & . \\
D & . & . & . & . & . & . & D \\
. & D & . & . & . & . & D & .
\end{array}
\]
\begin{array}{cccccccc}
X & . & . & . & . & . & X & X \\
. & . & o & o & o & . & . & . \\
. & . & . & o & . & . & . & . \\
. & o & . & . & . & o & . & . \\
. & o & . & . & . & o & . & . \\
. & . & . & o & . & . & . & . \\
X & . & . & . & . & . & X & . \\
X & . & . & . & . & . & X & X
\end{array}
\] Les $X$ représentent les dames, et les $o$ les cases libres.
je ne garantis pas que ce soit le maximum mais voici une solution à 10 cases libres. Aucune des 10 Dames noires n'est en prise d'une Dame blanche.
On peut faire de légères modifications et en obtenir d'autres. Par exemple, déplacer la Dg8 en a6 (les D d3 et e2 vont alors en g4 et g5).
Peut-on obtenir 11 ?
Aldo.
j'étais certain que 10 était le maximum mais je viens de trouver une position à 11 cases libres.
Objectif 12 ?
Aldo.
Ce problème est déroutant... je ne sais par quel bout le prendre.
Reste la solution de la force brute : tester pour chacune des 178462987637760 configurations le nombre de cases libres et prendre le max. Je n'ai pas le temps d'écrire ce bout de code mais je veux bien le faire samedi matin si personne ne l'a fait (ou plus vraisemblablement n'a résolu le problème autrement) d'ici là.
record:=0;
conv:=a->((a mod 8)+1, 1+(a-(a mod 8))/8); (*Convertit un nombre entre 0 et 63 en des coordonnées (x,y) sur l'échiquier *)
for a[1] from 0 to 56 do
for a[2] from a[1]+1 to 57 do (* a = position de la dame i *)
for a[3] from a[2]+1 to 58 do
for a[4] from a[3]+1 to 59 do
for a[5] from a[4]+1 to 60 do
for a[6] from a[5]+1 to 61 do
for a[7] from a[6]+1 to 62 do
for a[8] from a[7]+1 to 63 do
nb:=0:
for x from 1 to 8 do (*Une fois les dames placées, on cherche les*)
for y from 1 to 8 do (*cases libres*)
test:=1:
for i from 1 to 8 do
(xi,yi):=conv(a):
if x=xi then test:=0 end if:
if y=yi then test:=0 end if:
if abs(x-xi) = abs(y-yi) then test:=0 end if:
end do:
if test=1 then nb:=nb+1 end if: (*on les compte dans nb*)
end do:
end do:
if nb>record then print(nb,seq([conv(a[j])],j=1..8)): record:=nb: end if:
end do (*Si nb est plus grand que le record précédent*)
end do (*record = nb et on affiche nb ainsi que les coordonnées des dames *)
end do
end do
end do
end do
end do
end do;
Il tourne depuis hier soir, et le meilleur trouvé est 11, avec la même configuration (à rotation près) qu'Aldo. Va-t-il en trouver 12 ?
P.S : Maple n'étant pas très rapide, j'essaierai de porter ce code en C pour que ça aille plus vite, si j'en ai le temps et la motivation (parce que mes souvenirs en C datent un peu).
P.P.S : Bien sûr, si vous voulez exécuter ce programme, vous pouvez, mais vous devez virer les commentaires, sinon, ça marche pas.
#include < stdio.h>
typedef int ligne[8];
int main(void){
int r, s, i, record, nb, test;
ligne a, x, y;
record = 0;
for (a[0] = 0; a[0] < 57; a[0] ++) {
for (a[1] = a[0] + 1; a[1] < 58; a[1] ++) {
for (a[2] = a[1]+1; a[2] < 59; a[2] ++) {
for (a[3] = a[2]+1; a[3] < 60; a[3] ++) {
for (a[4] = a[3]+1; a[4] < 61; a[4] ++) {
for (a[5] = a[4]+1; a[5] < 62; a[5] ++) {
for (a[6] = a[5]+1; a[6] < 63; a[6] ++) {
for (a[7] = a[6]+1; a[7] < 64; a[7] ++) {
nb = 0;
for (r = 1; r < 9; r ++) {
for (s = 1; s < 9; s ++) {
test = 1;
for (i = 0; i < 8; i ++) {
x = 1 + a - 8*(a/8);
y = 1 + a/8;
if (r == x) test = 0;
if (s == y) test = 0;
if (abs (r - x) == abs (s - y)) test = 0;
}
if (test == 1) nb ++;
}
}
if (nb > record) {
record = nb;
printf ("\n \n %d , (%d,%d) , (%d,%d) , (%d,%d) , (%d,%d) , (%d,%d) , (%d, %d) , (%d,%d) , (%d,%d)",
record, x[0],y[0], x[1],y[1], x[2],y[2], x[3],y[3], x[4],y[4], x[5],y[5], x[6],y[6], x[7],y[7]);
}
}
}
}
}
}
}
}
}
}
(après vérification le $\frac{1}{8}$ est en fait un $\frac{1}{8!}$, ce qui est tout de même plus convenable...)
Ça correspond bien à ce que tu dis, et si la machine traite disons $10^9$ configurations par seconde, le programme doit se terminer en quelque chose de l'ordre de $2*10^5$ secondes, soit dans les 55 heures. Bref, je pense que le programme de Guego s'est terminé correctement (je vais essayer d'en faire tourner un aussi pour recouper, mais maintenant que quelqu'un a donné la solution j'ai moins de motiv' donc... some day).