Huit Dames

al berto · 26-10-2020 13:34:14

Bonjour,

J'ai trouvé ce problème sur l'échiquier, j'essaie le traduire:
Poser huit Dames sur l'échiquier de manière à commander (entre en prise?) le plus petit nombre possible de cases.

Comprenez vous ce que j'ai écrit?
ciao.
aldo

yoshi · 26-10-2020 14:43:31

RE,

Lei sa giocare a scacchi ?

de manière à commander (entre en prise?)

Ce ne serait pas plutôt : de manière à contrôler le minimum de cases.
Je nec connaissais pas ce problème.
Je connaissais :
Placer 8 Dames sur l'échiquirer de manière à ce que n'importe laquelle ne puisse être prise par l'une de sept autres...

@+

al berto · 26-10-2020 16:21:57

yoshi a écrit :

RE,
Lei sa giocare a scacchi ?

Tu sai giocare a scacchi? Je suis ton ami. Lei, Voi, c'est à dire Vous.
No. Seulement avec l'ordi. Mais je ne me rapelle pas bien.
Oui, je connais le probléme des huit dames que tu a posté, j'ai un livre qui en parle. Il parle de Nauch, Gauss et ses 92 solutions. Pas toutes!
ciao.
aldo

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"

@+

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.

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

Dernière modification par Bernard-maths (02-02-2022 21:50:18)

Zebulor · 02-02-2022 22:37:52

Bonsoir,
oui Bernard : je crois deviner que yoshi connaît assez bien les échecs

Boody · 05-02-2022 19:26:02

Bonjour forum,

Pas mieux, je trouve aussi 9 cases non en prise.

https://lichess.org/editor/QQQ5/1QQQ4/2 … _w_-_-_0_1

Dernière modification par Boody (05-02-2022 19:27:57)

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

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 · 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

Dernière modification par Bernard-maths (30-12-2023 18:22:15)

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...

@+

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.

10 cases libres

Y'a-t-il d'autres positions (hors symétrie) avec 10 cases libres ?

Bonne année 2024.

Lu

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

Dernière modification par Bernard-maths (03-01-2024 12:51:16)

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

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.

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

@+

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

Dernière modification par Rescassol (03-01-2024 16:03:45)

Forum de mathématiques - Bibm@th.net

#1 26-10-2020 13:34:14

Huit Dames

#2 26-10-2020 14:43:31

Re : Huit Dames

#3 26-10-2020 16:21:57

Re : Huit Dames

#4 26-10-2020 17:42:46

Re : Huit Dames

#5 02-02-2021 20:06:03

Re : Huit Dames

#6 02-02-2022 21:48:37

Re : Huit Dames

#7 02-02-2022 22:37:52

Re : Huit Dames

#8 05-02-2022 19:26:02

Re : Huit Dames

#9 05-02-2022 21:32:43

Re : Huit Dames

#10 30-12-2023 16:04:09

Re : Huit Dames

#11 30-12-2023 18:21:48

Re : Huit Dames

#12 30-12-2023 22:49:32

Re : Huit Dames

#13 03-01-2024 12:19:57

Re : Huit Dames

#14 03-01-2024 12:46:00

Re : Huit Dames

#15 03-01-2024 14:06:42

Re : Huit Dames

#16 03-01-2024 14:13:47

Re : Huit Dames

#17 03-01-2024 14:21:45

Re : Huit Dames

#18 03-01-2024 15:27:43

Re : Huit Dames

Réponse rapide

Pied de page des forums