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

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre confirmé
    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
    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 chevronné Avatar de Rafy
    Profil pro
    Inscrit en
    Juillet 2005
    Messages
    415
    Détails du profil
    Informations personnelles :
    Âge : 41
    Localisation : France

    Informations forums :
    Inscription : Juillet 2005
    Messages : 415
    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 : 38
    Localisation : France

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

    Informations forums :
    Inscription : Août 2005
    Messages : 5 183
    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
    C'est par l'adresse que vaut le bûcheron, bien plus que par la force. Homère

    Installation de Code::Blocks sous Debian à partir de Nightly Builds

  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
    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]
    "La haine seule fait des choix" - Koan Zen
    "Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
    "Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
    Faites du Prolog, ça vous changera les idées !
    Ma page Prolog
    Mes codes sources commentés

    Mon avatar : La Madeleine à la veilleuse de Georges de La Tour

  5. #5
    Membre confirmé
    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
    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
    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
    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.
    "La haine seule fait des choix" - Koan Zen
    "Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
    "Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
    Faites du Prolog, ça vous changera les idées !
    Ma page Prolog
    Mes codes sources commentés

    Mon avatar : La Madeleine à la veilleuse de Georges de La Tour

  7. #7
    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 : 38
    Localisation : France

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

    Informations forums :
    Inscription : Août 2005
    Messages : 5 183
    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
    C'est par l'adresse que vaut le bûcheron, bien plus que par la force. Homère

    Installation de Code::Blocks sous Debian à partir de Nightly Builds

  8. #8
    Membre confirmé
    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
    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...

  9. #9
    Invité de passage
    Inscrit en
    Février 2010
    Messages
    1
    Détails du profil
    Informations forums :
    Inscription : Février 2010
    Messages : 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 ?

  10. #10
    Membre Expert

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

    Informations forums :
    Inscription : Juin 2002
    Messages : 1 412
    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 !

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

    Informations forums :
    Inscription : Octobre 2004
    Messages : 3 893
    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.
    Mac LAK.
    ___________________________________________________
    Ne prenez pas la vie trop au sérieux, de toutes façons, vous n'en sortirez pas vivant.

    Sources et composants Delphi sur mon site, L'antre du Lak.
    Pas de question technique par MP : posez-la dans un nouveau sujet, sur le forum adéquat.

    Rejoignez-nous sur : Serveur de fichiers [NAS] Le Tableau de bord projets Le groupe de travail ICMO

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