Discussion :

[DevloNewb']

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 ?

[Rafy]

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 !

[Arnaud F.]

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

[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]

[DevloNewb']

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") ?

[DevloNewb']

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

[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.
Edit : ça correspond au post du dessus.

[Arnaud F.]

à 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

[Médiat]

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

[Trap D]

C'est celà Mediat, mais je n'ai pas le vocabulaire.
Dans mon calcul, la case vide se trouve en bas à droite.

[spirit_epock]

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

[myriam nasri]

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 ?

[henderson]

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 !

[Mac LAK]

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.

[Ulmo]

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.