Salut!
Je suis à la recherche de documentation en vue d'un TIPE sur le problème des dames aux échecs, et pour le moment je n'ai pas trouvé grand chose.
Merci d'avance pour votre aide :++:
Probleme des dames
19 messages
- Page 1 sur 1
par beagle » 08 Mar 2010, 19:11
comme dit sur wiki,
on peut faire une approche grace aux données sur les carrés magiques
pandiagonaux ,
magiques sur colonnes rangées et toutes les diagonales,
leurs méthodes de construction permet déjà de comprendre que le problème des n dames sur échiquier nxn sera bien différent pour n pair et n impair
on peut faire une approche grace aux données sur les carrés magiques
pandiagonaux ,
magiques sur colonnes rangées et toutes les diagonales,
leurs méthodes de construction permet déjà de comprendre que le problème des n dames sur échiquier nxn sera bien différent pour n pair et n impair
L'important est de savoir quoi faire lorsqu'il n' y a rien à faire.
par Le_chat » 08 Mar 2010, 19:22
Merci de ta réponse!!!
Je pense que je vais changer de sujet de tipe, j'ai deja fait un truc sur les carrés magiques et j'ai trouvé ça ennuyant
Je pense que je vais changer de sujet de tipe, j'ai deja fait un truc sur les carrés magiques et j'ai trouvé ça ennuyant
par beagle » 08 Mar 2010, 21:13
Zut, désolé de t'avoir dégouté, ce ne sont pas les mèmes contraintes tout de mème, cela doit moins partir dans tous les sens.
J'ai juste regardé le problème des dames et cela m'a rappelé ces carrés magiques diaboliques, mais contrairement à toi, cela date de ma jeunesse, j'avais beaucoup investi le sujet et cela me plaisait bien,
bon je n'étais pas encombré de connaissances mathématiques non plus,...
J'ai juste regardé le problème des dames et cela m'a rappelé ces carrés magiques diaboliques, mais contrairement à toi, cela date de ma jeunesse, j'avais beaucoup investi le sujet et cela me plaisait bien,
bon je n'étais pas encombré de connaissances mathématiques non plus,...
L'important est de savoir quoi faire lorsqu'il n' y a rien à faire.
par beagle » 09 Mar 2010, 11:09
J'ai regardé les solutions wiki pour le 8x8,
je redis que les structures, organisations géométriques,
vecteurs, symétries,...
sont des structures que l'on retrouve dans les carrés magiques.
Ce qui ne signifie en rien qu'il faille connaitre les carrés magiques,
cela signigie que l'expérience acquise dans un domaine se retrouve dans des problèmes cousins,
mais ce n'est pas la mème problématique du tout.
Si j'avais une grande expérience des vecteurs, matrices,
je t'aurais dit cela me rappelle tel ou tel boulot ...
derrière le chaos, la magie du wouah mais comment ça peut marcher,
se cachent certaines structures.Dans le cas présent, je ne suis pas capable de dire pourquoi cette structure marche plutot que telle autre, mais c'est marrrant de voir une "organisation", là où le premier regard voit les irrégularités chaotiques.
je redis que les structures, organisations géométriques,
vecteurs, symétries,...
sont des structures que l'on retrouve dans les carrés magiques.
Ce qui ne signifie en rien qu'il faille connaitre les carrés magiques,
cela signigie que l'expérience acquise dans un domaine se retrouve dans des problèmes cousins,
mais ce n'est pas la mème problématique du tout.
Si j'avais une grande expérience des vecteurs, matrices,
je t'aurais dit cela me rappelle tel ou tel boulot ...
derrière le chaos, la magie du wouah mais comment ça peut marcher,
se cachent certaines structures.Dans le cas présent, je ne suis pas capable de dire pourquoi cette structure marche plutot que telle autre, mais c'est marrrant de voir une "organisation", là où le premier regard voit les irrégularités chaotiques.
L'important est de savoir quoi faire lorsqu'il n' y a rien à faire.
par fatal_error » 09 Mar 2010, 12:14
salut,
pour le coup des dames, ca peut aussi etre marrant (tout est relatif...) d'un point de vu informatique.
Une des idées, c'est par exemple de définir tes règles (jme retiens) du style
je peux pas poser une dame car une autre est présente dans la même ligne de l'échiquier.
Et de faire un petit moteur d'inférence (derriere le nom barbare se cache juste un algo qui enchaine les regles apres les autres) pour rechercher la ou les solutions. Mais t'as de la chance, i zexistent déjà et t'as pas a t'en occuper. Tu peux par exemple utiliser le langage prolog qui s'en charge. La prise en main est un peu lourde (2h a coups de tuto), mais apres ca va 'presque' tout seul...
M'enfin si ca doit etre sur des math...oublie :we:
pour le coup des dames, ca peut aussi etre marrant (tout est relatif...) d'un point de vu informatique.
Une des idées, c'est par exemple de définir tes règles (jme retiens) du style
je peux pas poser une dame car une autre est présente dans la même ligne de l'échiquier.
Et de faire un petit moteur d'inférence (derriere le nom barbare se cache juste un algo qui enchaine les regles apres les autres) pour rechercher la ou les solutions. Mais t'as de la chance, i zexistent déjà et t'as pas a t'en occuper. Tu peux par exemple utiliser le langage prolog qui s'en charge. La prise en main est un peu lourde (2h a coups de tuto), mais apres ca va 'presque' tout seul...
M'enfin si ca doit etre sur des math...oublie :we:
la vie est une fête 
par Le_chat » 09 Mar 2010, 17:27
Okay merci pour vos réponses, ça confirme l'idée que je m'en faisais.
par beagle » 11 Mar 2010, 08:48
je voudrais savoir si la théorie des graphes permet un angle d'attaque intéressant pour ce genre de problème.
L'important est de savoir quoi faire lorsqu'il n' y a rien à faire.
par beagle » 11 Mar 2010, 10:53
Bonjour beagle,
comme personne ne répond, pour te faire patienter, je t'ai trouvé cela sur le net:
"En effet la théorie des graphes permet de résoudre ce probleme.
Il s'agit de considérer un graphe avec un sommet par case et une liaison entre deux cases si deux reines sur ces cases peuvent se prendre.
Ensuite il faut trouver les sous graphes stables maximal (c'est a dire les ensembles de sommets tels qu'aucun de ces sommets ne soient reliée)
"
comme personne ne répond, pour te faire patienter, je t'ai trouvé cela sur le net:
"En effet la théorie des graphes permet de résoudre ce probleme.
Il s'agit de considérer un graphe avec un sommet par case et une liaison entre deux cases si deux reines sur ces cases peuvent se prendre.
Ensuite il faut trouver les sous graphes stables maximal (c'est a dire les ensembles de sommets tels qu'aucun de ces sommets ne soient reliée)
"
L'important est de savoir quoi faire lorsqu'il n' y a rien à faire.
par beagle » 11 Mar 2010, 10:56
merci beagle,
beagle te remercie.
beagle te remercie.
L'important est de savoir quoi faire lorsqu'il n' y a rien à faire.
par beagle » 12 Mar 2010, 09:00
J'avais vu sur wiki le problème des n dames,
mais c'est en cherchant si la théorie des graphes dont j'ignore tout,
pouvait aider que je suis tombé sur le problème:
de coloration des dames
de coloration des graphes de dames.
j'ai trouvé de nombreuses refs dont de cet auteur,Michel Vasquez,
voici comment c'est présenté:
"Coloration des Graphes de Reines - Michel VASQUEZ - Ecole des Mines Alès - Site de Nîmes
Le problème de coloration de graphes de reines consiste à recouvrir un échiquier de dimension n avec n × n reines de telle sorte que deux reines de couleur identique ne s'attaquent pas. Jusqu'en 2003, le nombre chromatique de ces graphes, X(n), pour n supérieur à 9 et multiple de 2 ou 3, n'est pas connu.
Dans un premier temps je détaillerai un algorithme exact et complet de recherche de n ensembles indépendants (ou stables) qui recouvrent les n × n sommets (cases) de l'échiquier. Cet algorithme résout les instances n = 10 et n = 12 prouvant que X(10)=11 et X(12)=12. Il trouve également un recouvrement de l'échiquier 14 × 14 avec 14 stables ce qui prouve que X(14)=14. Les éléments principaux de cet algorithme sont : d'une part un pré-calcul des stables ayant un sommet sur chacune des cases de la première rangée de l'échiquier et, d'autre part, un élagage significatif de l'arbre de recherche par la prise en compte d'une contrainte sur la taille des cliques du sous-graphe des sommets non colorés.
Dans un deuxième temps, je présenterai une version incomplète de cet algorithme qui postule certaines caractéristiques géométriques que peuvent avoir les colorations minimales de ces graphes. Nous obtenons ainsi les résultats suivants : X(n)=n, pour n appartenant à {12,14,15,16,18,20,21,22,24,26,28,30,32}.
Enfin, à partir d'arithmétique modulaire je démontrerai qu'il existe une infinité de valeurs de n multiples de 2 et/ou 3 telles que X(n)=n.
La question "X(n) est il égal à n pour tout n > 10 ?" reste ouverte et l'on ne sait toujours pas si X(27) est égal à 27 ou à 28."
Et je ne comprends pas la notion de X(n)
cela désigne quoi?
J'avais cru comprendre que X(n)=n signifiait la possibilité de mettre n dames de n couleurs coloriant l'échiquier nxn,
mais alors X(10)=11 déjà je ne comprends plus.
C'est quoi le définition de X(n)?
mais c'est en cherchant si la théorie des graphes dont j'ignore tout,
pouvait aider que je suis tombé sur le problème:
de coloration des dames
de coloration des graphes de dames.
j'ai trouvé de nombreuses refs dont de cet auteur,Michel Vasquez,
voici comment c'est présenté:
"Coloration des Graphes de Reines - Michel VASQUEZ - Ecole des Mines Alès - Site de Nîmes
Le problème de coloration de graphes de reines consiste à recouvrir un échiquier de dimension n avec n × n reines de telle sorte que deux reines de couleur identique ne s'attaquent pas. Jusqu'en 2003, le nombre chromatique de ces graphes, X(n), pour n supérieur à 9 et multiple de 2 ou 3, n'est pas connu.
Dans un premier temps je détaillerai un algorithme exact et complet de recherche de n ensembles indépendants (ou stables) qui recouvrent les n × n sommets (cases) de l'échiquier. Cet algorithme résout les instances n = 10 et n = 12 prouvant que X(10)=11 et X(12)=12. Il trouve également un recouvrement de l'échiquier 14 × 14 avec 14 stables ce qui prouve que X(14)=14. Les éléments principaux de cet algorithme sont : d'une part un pré-calcul des stables ayant un sommet sur chacune des cases de la première rangée de l'échiquier et, d'autre part, un élagage significatif de l'arbre de recherche par la prise en compte d'une contrainte sur la taille des cliques du sous-graphe des sommets non colorés.
Dans un deuxième temps, je présenterai une version incomplète de cet algorithme qui postule certaines caractéristiques géométriques que peuvent avoir les colorations minimales de ces graphes. Nous obtenons ainsi les résultats suivants : X(n)=n, pour n appartenant à {12,14,15,16,18,20,21,22,24,26,28,30,32}.
Enfin, à partir d'arithmétique modulaire je démontrerai qu'il existe une infinité de valeurs de n multiples de 2 et/ou 3 telles que X(n)=n.
La question "X(n) est il égal à n pour tout n > 10 ?" reste ouverte et l'on ne sait toujours pas si X(27) est égal à 27 ou à 28."
Et je ne comprends pas la notion de X(n)
cela désigne quoi?
J'avais cru comprendre que X(n)=n signifiait la possibilité de mettre n dames de n couleurs coloriant l'échiquier nxn,
mais alors X(10)=11 déjà je ne comprends plus.
C'est quoi le définition de X(n)?
L'important est de savoir quoi faire lorsqu'il n' y a rien à faire.
par Ben314 » 12 Mar 2010, 09:49
Si je comprend tout bien (problème de coloration d'un graphe), tu as un échiquier de taille n et tu cherche à disposer dessus n² dames (i.e. une dans chaque case) de m couleurs différentes de façon que deux dames de même couleur ne soit pas en "prise" l'une de l'autre.
Le plus petit m tel qu'une solution existe est noté X(n).
Comme sur une même ligne, toutes les reines doivent être de couleur différente, il est clair que X(n) est toujours supérieur ou égal à n. La question est de savoir s'il est égal à n, c'est à dire si il existe une solution avec seulement n couleurs différentes.
Quand il écrit X(10)=11, cela signifie qu'il n'y a pas de solutions sur un échiquier 10x10 avec seulement 10 couleurs, il faut au moins 11 couleurs.
Par exemple, une question qui me vient à l'esprit et (peut-être) plus simple que de chercher les n tels que X(n)=n serait : "est il évident que X(n)<=n+1" , c'est à dire qu'avec n+1 couleur, il y a toujours une soluce ?
[pour dire (encore) une connerie, par exemple, il est clair que X(n)<=n² !!!!!]
Le plus petit m tel qu'une solution existe est noté X(n).
Comme sur une même ligne, toutes les reines doivent être de couleur différente, il est clair que X(n) est toujours supérieur ou égal à n. La question est de savoir s'il est égal à n, c'est à dire si il existe une solution avec seulement n couleurs différentes.
Quand il écrit X(10)=11, cela signifie qu'il n'y a pas de solutions sur un échiquier 10x10 avec seulement 10 couleurs, il faut au moins 11 couleurs.
Par exemple, une question qui me vient à l'esprit et (peut-être) plus simple que de chercher les n tels que X(n)=n serait : "est il évident que X(n)<=n+1" , c'est à dire qu'avec n+1 couleur, il y a toujours une soluce ?
[pour dire (encore) une connerie, par exemple, il est clair que X(n)<=n² !!!!!]
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius
par beagle » 12 Mar 2010, 10:22
super, merci Ben!
J'étais parti, du fait du problème initial des n dames,
j'étais parti à réfléchir à l'envers,
c'est à dire combien de n dames différentes pouvaient remplir au maximum l'échiquier nxn,
donc je voyais depuis le départ, soit les n dames y arrivaient,
soit moins de n dames,
par exemple avec le 8x8 qui comporte peu de solutions, pouvaient-on remplir l'échiquier, me semblait pas évident que oui,
donc en reprenant le problème en sens inverse, OK, je rajoute des couleurs si blocage.Mais alors une couleur n'est plus représentée n fois.
Merci encore.
J'étais parti, du fait du problème initial des n dames,
j'étais parti à réfléchir à l'envers,
c'est à dire combien de n dames différentes pouvaient remplir au maximum l'échiquier nxn,
donc je voyais depuis le départ, soit les n dames y arrivaient,
soit moins de n dames,
par exemple avec le 8x8 qui comporte peu de solutions, pouvaient-on remplir l'échiquier, me semblait pas évident que oui,
donc en reprenant le problème en sens inverse, OK, je rajoute des couleurs si blocage.Mais alors une couleur n'est plus représentée n fois.
Merci encore.
L'important est de savoir quoi faire lorsqu'il n' y a rien à faire.
par Ben314 » 12 Mar 2010, 10:33
J'y connais pas gras à la théorie des graphes, mais je sais que les problèmes de coloriage y sont trés fréquents : étant donné un graphe, combien de couleurs faut il au minimum pour colorier tout les sommets sans que deux sommets reliés par une arrête soit de la même couleur ? (ce nombre est appalé "nombre chromatique" du graphe : tu peut aller voir là )
Le plus connu est évidement le problème de coloriage d'une "carte de géographie" où sommet=pays ; arrête=frontière commune entre les deux pays. (nombre chromatique inférieur ou égal à 4)
Le plus connu est évidement le problème de coloriage d'une "carte de géographie" où sommet=pays ; arrête=frontière commune entre les deux pays. (nombre chromatique inférieur ou égal à 4)
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius
par Benjamin » 12 Mar 2010, 12:55
Ben314 a écrit:Comme sur une même ligne, toutes les reines doivent être de couleur différente, il est clair que X(n) est toujours supérieur ou égal à n.
Je ne suis pas d'accord.
Les n² dames étant toutes placées, d'après les règles des échecs on ne peux pas sauter par-dessus une pièce pour en prendre une autre. Si j'ai bien compris le problème, pour moi il est équivalent à sur un échiquier, aucune case ne doit être entouré de cases de même couleur. Ce qui n'oblige pas toutes les reines d'une même ligne d'être de couleurs différentes. Exemple pour le cas n=3 (R=Rouge, V=Vert, B=Bleur, N=Noir) :
R V B
B N R
R V B
Et on voit que X(3)=4. Il est facile de voir que X(2)=4 d'ailleurs donc nécessairement, X(3)>=4.
Ou alors, je n'ai rien compris au problème (toujours possible).
par Benjamin » 12 Mar 2010, 13:03
Je confirme, j'avais rien compris puisqu'avec mes règles c'est trivial j'ai l'impression. X(N) vaut toujours 4...
J'ai compris en fait, il faut enlever toutes les autres dames pour voir si deux dames de même couleurs sont en prise. Dans ce cas, je suis d'accord avec toi Ben (il ne peut pas y avoir de dames de même couleurs sur une même ligne, colonne ou diagonale). Et ma solution donnée pour n=3 ne fonctionne pas.
J'ai compris en fait, il faut enlever toutes les autres dames pour voir si deux dames de même couleurs sont en prise. Dans ce cas, je suis d'accord avec toi Ben (il ne peut pas y avoir de dames de même couleurs sur une même ligne, colonne ou diagonale). Et ma solution donnée pour n=3 ne fonctionne pas.
par Benjamin » 12 Mar 2010, 13:08
Pour n=3, je crois qu'il n'y a pas de solutions à moins de 5 couleurs :
R V B
J N R
V B J
R V B
J N R
V B J
par beagle » 12 Mar 2010, 13:09
Bonjour Benjamin,sur le plan échiquéen, tu as complètement raison,
et en plus cela se prète assez bien également à une étude des graphes-couleurs, commes les pays, etc...
Sur le plan du problème tel "qu'énoncé"où?, tel que "résolu"? dans la littérature, je pense que tu ne peux pas avoir deux dames mème couleur sur une mème rangée, colonne, diagonale.
J'ai une ref au boulot sortie hier soir où le gars a fait un algorithme pour 12 et 14 et donne des solutions avec des couleurs, mais je crois aussi avec des lettres, et il me semble que sa première colonne est ABCDEFGHIJKLMN,
je le mets en lien d'ici peu.
et en plus cela se prète assez bien également à une étude des graphes-couleurs, commes les pays, etc...
Sur le plan du problème tel "qu'énoncé"où?, tel que "résolu"? dans la littérature, je pense que tu ne peux pas avoir deux dames mème couleur sur une mème rangée, colonne, diagonale.
J'ai une ref au boulot sortie hier soir où le gars a fait un algorithme pour 12 et 14 et donne des solutions avec des couleurs, mais je crois aussi avec des lettres, et il me semble que sa première colonne est ABCDEFGHIJKLMN,
je le mets en lien d'ici peu.
L'important est de savoir quoi faire lorsqu'il n' y a rien à faire.
par beagle » 12 Mar 2010, 13:32
ref pour 12 et 14 avec les couleurs:
http://janaudy.com/n2q/
http://janaudy.com/n2q/
L'important est de savoir quoi faire lorsqu'il n' y a rien à faire.
19 messages
- Page 1 sur 1
Qui est en ligne
Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 7 invités
Tu pars déja ?
Fais toi aider gratuitement sur Maths-forum !
Créé un compte en 1 minute et pose ta question dans le forum ;-)
Identification
Pas encore inscrit ?
Ou identifiez-vous :