Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
- Accueil
- » Échecs et maths
- » Huit Dames
- » Répondre
Répondre
Résumé de la discussion (messages les plus récents en premier)
- Rescassol
- 03-01-2024 15:27:43
Bonjour,
Pour le problème classique:
####################################
# Problème des reines sur un échiquier
# Rescassol - 20 Janvier 2018
####################################
####################################
# Importations
####################################
import numpy as np
import itertools as it
from time import perf_counter
####################################
# Fonctions
####################################
def TestReines(A):
n=len(A)
B=np.dot(A,J)
for k in range(-n+1,n):
if sum(np.diag(A,k))>1:
return False
if sum(np.diag(B,k))>1:
return False
return True
####################################
# Script principal de test
####################################
# initialisations
n, cpt = 8, 0 # Pour un échiquier 8X8
J=np.fliplr(np.eye(n,dtype=int))
L=list(it.permutations(range(n)))
# Calculs et affichage des résultats
t=perf_counter()
for P in L:
A=np.zeros((n,n),int)
for k in range(n): # Génération des n! matrices candidates
A[k,P[k]]=1
if TestReines(A): # Les tours sont elles des reines ?
print(A,'\n')
cpt+=1
print('Il y a',cpt,'configurations possibles')
print('Temps mis pour les trouver: ',round(perf_counter()-t,3),'secondes')
Cordialement,
Rescassol
- yoshi
- 03-01-2024 14:21:45
Bonjour,
Bon... Il va donc falloir que je m'y colle vraiment, donc !
Je pars sur une idée :
échiquier libre
1. je mets chaque case à 0 dans une liste de 64 cases de a1 à h8... ou dans une liste de 8 sous-listes de 8 cases, chaque sous-liste représentant une ligne. J'en fais une copie conforme.
2. Je place un dame en a1, je mets toutes les cases de la colonne a, de la ligne 1 et de la diagonale principale "a1-h8", à 1.
et dans la copie, je supprime la première sous-liste et mets chaque premier 0 de sous-liste à 1 ce qui interdit la première colonne aux autres Dames, plus chaque case de la diagonale.
En Python, j'ai le choix soit de parcourir une liste par l'index de chaque élément, soit - solution que je projette d'employer - de demander à Python de se dém... et de parcourir la liste un élément après l'autre (et là, je n'ai pas besoin de savoir s'il y en 4, 20 , 50...) ce qui me permet de laisser des cases vides...
sur la 2e ligne
3. Sur la 2e ligne, donc dans la deuxième sous-liste, la position de la Dame suivante la plus proche est en saut de Cavalier...
Et je joue avec les les 0 et 1 et éventuellement les suppressions.
Ce ne sont que des idées en vrac... Je cherche le moyen le plus rapide de ne tester que les cases libres et donc de raccourcir les traitements de chaque boucle... en faisant en sorte qu'ils soient de moins en moins nombreux à chaque tour...
En attendant, j'ai retrouvé facilement (je ne m'attendais pas à tomber dessus aussi vite) l'algo dont je parlais :
https://zanotti.univ-tln.fr/ALGO/I51/Reines.html
@+
- Glozi
- 03-01-2024 14:13:47
Finalement, mon programme vient de terminer (1373 secondes), et a priori (sauf erreur de codage) il n'y a pas de configuration avec 12 cases libres.
- Glozi
- 03-01-2024 14:06:42
Bonjour,
Quelques solutions différentes avec 11 cases libres.
https://lichess.org/editor/QQQ5/1QQ5/5p … olor=white
https://lichess.org/editor/QQQ5/1QQQ4/5 … olor=white
https://lichess.org/editor/Q1Q5/1Q1Q4/5 … olor=white
https://lichess.org/editor/1QQ5/2QQ4/5p … olor=white
https://lichess.org/editor/1Q1Q4/5ppp/Q … olor=white
Mes préférées
https://lichess.org/editor/1Q4Q1/Q1Q3Q1 … olor=white
https://lichess.org/editor/2QQQ3/6pp/Q3 … olor=white
Il y en a d'autres, il faudrait que je laisse tourner mon programme mais pour le moment je n'ai rien trouvé avec 12 pions ou plus.
Bonne journée
- Bernard-maths
- 03-01-2024 12:46:00
Bonjour à tous !
BRAVO Lu !!!
J'étais resté "bloqué" avec les dames rassemblées ... Bonne idée de les séparer ! Alors ???
Yoshi !!! Ton programme ???
B-m
- Lu
- 03-01-2024 12:19:57
Bonjour,
Je suis tombé par hasard sur ce fil de discussion. J'ai trouvé une solution avec 10 cases libres.
Y'a-t-il d'autres positions (hors symétrie) avec 10 cases libres ?
Bonne année 2024.
Lu
- yoshi
- 30-12-2023 22:49:32
Bonsoir,
Apparemment sur ce que j'en sais, on ne peut faire mieux que 9 cases. Sur Internet, j'avais trouvé différents algorithmes dont un en Javascript qui recensait 92 "solutions", avec des guillemets, parce que je ne suis pas certain que son auteur avait tenu compte des réponses redondantes par symétries, ou se recoupant...
Ça m'avait tout l'air d'une recherche exhaustive (bruteforce)
Il va falloir que je finisse par écrire le mien d'algorithme...
@+
- Bernard-maths
- 30-12-2023 18:21:48
Bonjour Adiamantin !
C'est bien de nous envoyer une tentative !
Si tu vas voir la proposition de Boody en #8, tu verras qu'il y a 9 cases non en prise ... et on cherche mieux ???
Bonnes fêtes aussi,
Bernard-maths
- Adiamantin
- 30-12-2023 16:04:09
Bonjour, (c'est la première que je poste sur ce site, désolé si ce n'est pas bien formulé). Pour répondre au tout premier message qui demandait comment contrôler le moins de cases d'un échiquier avec 8 reines, j'ai réussi à aller jusqu'à 36 sur 64 en mettant les reines en A1 A2 A3, B1 B2 B3, C1 C2
Déjà les Dames en A1 A2 et B1 ne contrôle aucune case, B2 ne contrôle qu'une diagonale et A3 B3 C1 C2 contrôlent une portion d'horizontales et de diagonales
Je ne sais pas comment montrer que c'est le meilleur résultat ou non...
Bonnes fêtes
- Bernard-maths
- 05-02-2022 21:32:43
Bonsoir à tous !
Oui Boody, c'est cette situation que j'ai trouvée !
Qu'en dit la "communauté" ?
Bonsoir, Bernard-maths
- Boody
- 05-02-2022 19:26:02
Bonjour forum,
Pas mieux, je trouve aussi 9 cases non en prise.
- Zebulor
- 02-02-2022 22:37:52
Bonsoir,
oui Bernard : je crois deviner que yoshi connaît assez bien les échecs
- Bernard-maths
- 02-02-2022 21:48:37
Bonsoir à tous !
Voilà 1 an aujourd'hui, et 1h 42' 34", que j'ai proposé une réponse !
Mais personne n'a répondu ! Y-a-t-il encore quelqu'un qui s'intéresse aux échec ???
Bernard-maths
- Bernard-maths
- 02-02-2021 20:06:03
Bonsoir !
Pour le moment, je trouve au mieux 9 cases non en prise, donc 8 cases "enreinées" plus 47 cases en prise ...
B-m.
- yoshi
- 26-10-2020 17:42:46
Salut,
Oui, je sais : c'était volontaire !
Au Lycée, mes professeurs m'avaient appris qu'il s'agissait de la 3e personne de politesse :
(Vostra Signoria) sait-elle jouer aux échecs ?...
Ni "vous", ni "tu"
@+