IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Question sur le jeu du Taquin


Sujet :

Algorithmes et structures de données

  1. #1
    Membre du Club
    Profil pro
    Inscrit en
    Décembre 2005
    Messages
    69
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2005
    Messages : 69
    Points : 47
    Points
    47
    Par défaut Question sur le jeu du Taquin
    pour ceux qui ne connaîtrait pas : http://fr.wikipedia.org/wiki/Taquin

    Est-ce que quelqu'un sait si le fait de changer la dimension du Taquin peut rendre la partie insoluble ?

    En règle général il s'agit d'une dimension 4x4 (ligne x colonnes) mais est-ce que cela marche de la même façon avec 8x15 par exemple ?

  2. #2
    Membre averti Avatar de Rafy
    Profil pro
    Inscrit en
    Juillet 2005
    Messages
    415
    Détails du profil
    Informations personnelles :
    Âge : 40
    Localisation : France

    Informations forums :
    Inscription : Juillet 2005
    Messages : 415
    Points : 417
    Points
    417
    Par défaut
    Je ne vois pas pourquoi ça serai insoluble...
    Sauf si tu arrives à 1 ligne ou 1 colonne, mais ça je ne pense pas que tu avais besoin de moi pour le deviner
    J'en ai déjà vu un grand il devait y avoir environ 10x10... alors 8x15 pourquoi pas !

  3. #3
    Rédacteur
    Avatar de Arnaud F.
    Homme Profil pro
    Développeur COBOL
    Inscrit en
    Août 2005
    Messages
    5 183
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 37
    Localisation : France

    Informations professionnelles :
    Activité : Développeur COBOL
    Secteur : Finance

    Informations forums :
    Inscription : Août 2005
    Messages : 5 183
    Points : 8 873
    Points
    8 873
    Par défaut
    Pour dire vrai, je suis en train de coder le jeu du Taquin en Java

    Avec des dimensions pouvant aller de 2*2 à n*n
    Pour dire vrai, ceux de 2*2 si les pièces ne sont pas dans le bon ordre, ben ils sont insolubles, mais j'ai récemment lu un article sur le net prouvant que si 2 cases etait l'une a coté de l'autre(si ta positonné toutes les autres cases auparavant...), ben que ce jeu la serait insoluble

    Donc pour te répondre, je dirais que peu importe la dimension de ton jeu, y a toujours moyen d'en trouver qui sont irrésolvable

  4. #4
    Rédacteur/Modérateur
    Avatar de Trap D
    Profil pro
    Inscrit en
    Septembre 2003
    Messages
    4 942
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2003
    Messages : 4 942
    Points : 6 498
    Points
    6 498
    Par défaut
    C'est une question de mélange en fait, il y a une condition à respecter pour obtenir une combinaison solvable (c'est le bon mot ? ).
    [edit] c'est soluble qu'il faut écrire
    [/edit]

  5. #5
    Membre du Club
    Profil pro
    Inscrit en
    Décembre 2005
    Messages
    69
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2005
    Messages : 69
    Points : 47
    Points
    47
    Par défaut
    Citation Envoyé par Trap D
    C'est une question de mélange en fait, il y a une condition à respecter pour obtenir une combinaison solvable (c'est le bon mot ? ).
    [edit] c'est soluble qu'il faut écrire
    [/edit]
    à quoi penses-tu ?

    ce ne serait pas tout simplement mélanger en faisant x succession de déplacements possibles dont la direction de chacun de ces déplacements serait aléatoire (c'est à dire comme si on mélangeait "à la main") ?

  6. #6
    Membre du Club
    Profil pro
    Inscrit en
    Décembre 2005
    Messages
    69
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2005
    Messages : 69
    Points : 47
    Points
    47
    Par défaut
    mais j'ai récemment lu un article sur le net prouvant que si 2 cases etait l'une a coté de l'autre(si ta positonné toutes les autres cases auparavant...), ben que ce jeu la serait insoluble
    hmm ? j'ai pas compris ce que tu voulais dire...

  7. #7
    Rédacteur/Modérateur
    Avatar de Trap D
    Profil pro
    Inscrit en
    Septembre 2003
    Messages
    4 942
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2003
    Messages : 4 942
    Points : 6 498
    Points
    6 498
    Par défaut
    Je sais, mais je n'arrive pas à retrouver la référence, qu'il y a un test des cellules pour savoir si le taquin est soluble, ou pas. Je l'avais codé en C mais il faut que je me replonge dedans pour expliquer le calcul.
    E relisant le code, en très gros, je crois qu' il faut calculer pour chaque casedu taquin mélangé le nombre de cases situées après celle-ci qui ont un nombre plus petit que la caseconsidérée. On additionne toutes ces sommes, si cette somme est paire, le taquin est soluble sinon il est insoluble.
    Edit : ça correspond au post du dessus.

  8. #8
    Rédacteur
    Avatar de Arnaud F.
    Homme Profil pro
    Développeur COBOL
    Inscrit en
    Août 2005
    Messages
    5 183
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 37
    Localisation : France

    Informations professionnelles :
    Activité : Développeur COBOL
    Secteur : Finance

    Informations forums :
    Inscription : Août 2005
    Messages : 5 183
    Points : 8 873
    Points
    8 873
    Par défaut
    Citation Envoyé par DevloNewb'
    à quoi penses-tu ?

    ce ne serait pas tout simplement mélanger en faisant x succession de déplacements possibles dont la direction de chacun de ces déplacements serait aléatoire (c'est à dire comme si on mélangeait "à la main") ?
    Pour te répondre, mon Taquin, je mélange comme si je le mélangeais " a la main" ouai, c-a-d que ma case vide se déplace normalement dans mon jeu, je ne fais pas de déplacement aléatoire

  9. #9
    Inactif   Avatar de Médiat
    Inscrit en
    Décembre 2003
    Messages
    1 946
    Détails du profil
    Informations forums :
    Inscription : Décembre 2003
    Messages : 1 946
    Points : 2 227
    Points
    2 227
    Par défaut
    Citation Envoyé par Trap D
    Je sais, mais je n'arrive pas à retrouver la référence, qu'il y a un test des cellules pour savoir si le taquin est soluble, ou pas. Je l'avais codé en C mais il faut que je me replonge dedans pour expliquer le calcul.
    E relisant le code, en très gros, je crois qu' il faut calculer pour chaque casedu taquin mélangé le nombre de cases situées après celle-ci qui ont un nombre plus petit que la caseconsidérée. On additionne toutes ces sommes, si cette somme est paire, le taquin est soluble sinon il est insoluble.
    De mémoire la solvabilité du taquin est liée à la signature de la permutation que représente la position de départ, par rapport à la position d'arrivée (en donnant le N° 0 à la case vide) + le nombre de déplacement de la case vide...

  10. #10
    Rédacteur/Modérateur
    Avatar de Trap D
    Profil pro
    Inscrit en
    Septembre 2003
    Messages
    4 942
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2003
    Messages : 4 942
    Points : 6 498
    Points
    6 498
    Par défaut
    C'est celà Mediat, mais je n'ai pas le vocabulaire.
    Dans mon calcul, la case vide se trouve en bas à droite.

  11. #11
    Membre habitué Avatar de spirit_epock
    Profil pro
    Inscrit en
    Mars 2006
    Messages
    153
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mars 2006
    Messages : 153
    Points : 173
    Points
    173
    Par défaut
    Le but est de le rendre insoluble alors que de base on chercher à trouver la ou les solutions. Tu cherche à être un piégeur....

    Pour le rendre insoluble tu parts du raisonnement par l'absurde sachant que tu sais comment le rendre soluble.

    et le tour est joué...

  12. #12
    Nouveau Candidat au Club
    Inscrit en
    Février 2010
    Messages
    1
    Détails du profil
    Informations forums :
    Inscription : Février 2010
    Messages : 1
    Points : 1
    Points
    1
    Par défaut taquin
    Citation Envoyé par DevloNewb' Voir le message
    pour ceux qui ne connaîtrait pas : http://fr.wikipedia.org/wiki/Taquin

    Est-ce que quelqu'un sait si le fait de changer la dimension du Taquin peut rendre la partie insoluble ?

    En règle général il s'agit d'une dimension 4x4 (ligne x colonnes) mais est-ce que cela marche de la même façon avec 8x15 par exemple ?

  13. #13
    Membre chevronné

    Profil pro
    Inscrit en
    Juin 2002
    Messages
    1 390
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juin 2002
    Messages : 1 390
    Points : 1 777
    Points
    1 777
    Par défaut
    Salut !

    Si on suppose qu'il existe un seul cas impossible à résoudre alors il en existe une multitude !
    Et on en arrive très vite à la conclusion qu'il n'y a pas de cas impossible à résoudre.

    A plus !

  14. #14
    Inactif  
    Avatar de Mac LAK
    Profil pro
    Inscrit en
    Octobre 2004
    Messages
    3 893
    Détails du profil
    Informations personnelles :
    Âge : 50
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations forums :
    Inscription : Octobre 2004
    Messages : 3 893
    Points : 4 846
    Points
    4 846
    Par défaut
    Citation Envoyé par DevloNewb' Voir le message
    Est-ce que quelqu'un sait si le fait de changer la dimension du Taquin peut rendre la partie insoluble ?
    Si tu mélanges les pièces n'importe comment, tu peux arriver à des taquins insolubles.

    Par contre, si tu pars d'un taquin résolu que tu mélanges comme si tu le faisais "à la main" (comme Arnaud F.), alors tu es bien entendu certain d'en obtenir un qui a une solution... Et ceci, peu importe ses dimensions.

  15. #15
    Membre actif
    Inscrit en
    Décembre 2003
    Messages
    272
    Détails du profil
    Informations forums :
    Inscription : Décembre 2003
    Messages : 272
    Points : 284
    Points
    284
    Par défaut
    Citation Envoyé par Médiat Voir le message
    De mémoire la solvabilité du taquin est liée à la signature de la permutation que représente la position de départ, par rapport à la position d'arrivée (en donnant le N° 0 à la case vide) + le nombre de déplacement de la case vide...
    C'est tout à fait ça :
    Tu as un invariant qui est 0/1 selon la signature de la permutation (case vide comprise) + nombre de déplacements de la case vide modulo 2.
    Si l'invariant de ta configuration est celui de la solution, ta configuration est soluble.

Discussions similaires

  1. Question sur un jeu en reseau
    Par jonny_the_dog dans le forum Qt
    Réponses: 1
    Dernier message: 26/11/2008, 23h29
  2. [Jeu]Question sur le jeu du trinôme
    Par Kevin12 dans le forum La taverne du Club : Humour et divers
    Réponses: 6
    Dernier message: 04/04/2008, 17h49
  3. Question sur Architecture d'un jeu vidéo 3D
    Par Polygon dans le forum Développement 2D, 3D et Jeux
    Réponses: 2
    Dernier message: 28/10/2007, 12h43
  4. Jeu d'instructions et petites questions sur l'asm
    Par SimpleMe dans le forum Assembleur
    Réponses: 6
    Dernier message: 16/03/2007, 18h42
  5. [2D] Questions sur le jeu Slayers Online
    Par Extra-Nitro dans le forum Développement 2D, 3D et Jeux
    Réponses: 5
    Dernier message: 04/02/2006, 19h32

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo