Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

Répondre

Veuillez composer votre message et l'envoyer
Nom (obligatoire)

E-mail (obligatoire)

Message (obligatoire)

Programme anti-spam : Afin de lutter contre le spam, nous vous demandons de bien vouloir répondre à la question suivante. Après inscription sur le site, vous n'aurez plus à répondre à ces questions.

Quel est le résultat de l'opération suivante (donner le résultat en chiffres)?
soixante trois plus trente quatre
Système anti-bot

Faites glisser le curseur de gauche à droite pour activer le bouton de confirmation.

Attention : Vous devez activer Javascript dans votre navigateur pour utiliser le système anti-bot.

Retour

Résumé de la discussion (messages les plus récents en premier)

Rescassol
03-01-2024 14: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 13: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 13: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.

Bernard-maths
03-01-2024 11: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 11: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

yoshi
30-12-2023 21: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 17: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 15: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 20: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 18:26:02

Bonjour forum,

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

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

Zebulor
02-02-2022 21:37:52

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

Bernard-maths
02-02-2022 20: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 19: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 16: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"

@+

Pied de page des forums