Discussion :

[tbc92]

Pour le taquin cylindrique, j'ai trouvé ça : https://www.thingiverse.com/thing:2221379

En gros, on a une grille comme ça :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
01 02 03 04 05
06 07 08 09 10
11 12 13 14 XX

Sauf que, comme on est sur un cylindre, la colonne (01,06,11) touche la colonne (05,10,XX) ; Ca donne donc plus de mouvements possibles.

Et difficulté supplémentaire, comme on est sur un cylindre, on se retrouve avec d'autres positions 'valides', par exemple :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
04 05 01 02 03
09 10 06 07 08
14 XX 11 12 13

PS : après avoir posté mon message, j'ai regardé le lien, et la vidéo qui va avec. Dans cette vidéo, le taquin est cylindrique, mais le procédé de montage fait qu'on se retrouve avec un jeu de taquin classique. La barre verticale fausse tout. Il faut imaginer le même jeu, sans la barre verticale. En tout cas, c'est comme ça que j'interprète la précision 'taquin cylindrique'.

[Flodelarab]

Oui moi aussi.
Le taquin cylindrique est le taquin classique dont on aurait collé deux bords opposés.
C'est pour cela que je parlais de donut.
C'est bizarre de faire l'expérience de penser dans un sens et pas dans l'autre.
Si les 4 cotés étaient collés à leurs opposés, on aurait un donut.

[anapurna]

salut

ok je vois mieux ... effectivement dans la version du film c'est l’équivalent d'un taquin a plat
dans celui que tu décrit tu n'a toujours qu'une solution ... il y a juste un décalage de colonne par rapport a ta position initial présupposée
je suppose donc que les même règle doivent être applicable au décalage de colonne près

[zekabyle]

Un taquin cylindrique a plusieurs états finaux qui est le nombre de colonnes du damier.

Concernant les permutations possibles, je vois cela :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
 
 
for (int i = 0; i < nbLignes; ++i) {
	for (int j = 0; j < nbColonnes; ++j) {
 
             if (i > 0) NORD  case vide (i-1,j)
             if (j > 0)  OUEST  case vide (i, j-1)
 
             if (i < nbLignes - 1)  SUD  case vide (i+1, j)
             if (j < nbColonnes - 1)  EST  case vide (i, j+1)
 
	}
}

Est-ce que vous voyez d'autres conditions en plus ou à la place pour les permutations d'un taquin cylindrique ?


Merci

[tbc92]

Il y a beaucoup de problèmes. Trop de problèmes. Impossible de partir de ça.

En fait, tu essaies de décrire l'heuristique du taquin avec des boucles i,j ... mais je pense que tu ne connais pas les règles du jeu. Donc tu ne peux pas t'en sortir.

Essaie de décrire en français les règles du jeu, l'objectif du jeu, le déroulement du jeu, avec des phrases claires. Traduire de français en pseudo-code, c'est de la traduction, comme on traduit de français en espagnol ... c'est simple. Mais il faut déjà avoir bien décrit la chose en français.

[zekabyle]

Non non, ce n'est pas l'heuristique que je décris mais plutôt les permutations possibles et je pense que cela ne prend pas le cas d'une rotation quand la case vide est sur un côté.

J'ai un damier avec une case vide et je veux savoir dans quelles cases possibles je peux permuter la case vide. Je suppose que je peux avoir toujours 4 mouvements possibles mais qu'il faut que je gère les rotations.


Par exemple le damier suivant :

2 4 #
5 1 3


le # peut aller à gauche et permuter avec le 4, aller à droite par rotation et permuter avec le 2, aller en haut et permuter avec le 3 et aller en bas et permuter avec le 3.

Ce serait juste pour savoir comment je pourrais gérer ces conditions.

[tbc92]

Et à partir de la position suivante, quels sont les mouvements possibles ?
2 4 #
5 1 3
6 7 8

[zekabyle]

Depuis ce damier :
2 4 #
5 1 3
6 7 8



nous pouvons avoir ces 4 mouvements :

EST
Permuter 2 et #
# 4 2
5 1 3
6 7 8

SUD
Permuter 3 et #
2 4 3
5 1 #
6 7 8


OUEST
Permuter 4 et #
2 # 4
5 1 3
6 7 8


NORD
Permuter 8 et #
2 4 8
5 1 3
6 7 #

[anapurna]

salut

comme le dis tbc92 il est pas simple de comprendre ce que tu veut nous dire si tu ne l’énonce pas clairement

par exemple pour le déplacement d'une pièce qu'elle sont les conditions
1°) il faut que que la colonne adjacent a ton déplacement soit vide
2°) le déplacement ne peut se faire que d'une case dans 4 direction possible

=> ce qui revient a dire
créer une fonction pour savoir si tu peut effectuer le déplacement

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
 
Fonction DEPLACEMENTPOSSIBLE(X,Y) : BOOLEAN 
DEBUT 
  SI PAS(HORLIMITE(X,Y))  ALORS // Pour ton cas il n'y a pas de limite mais on change la valeur x et ou de y si on dépasse le cadre 
  DEBUT 
    SI CASEVIDE(X,Y) ALORS
      RETOURNE VRAI
    SINON 
      RETOURNE FAUX
    FINSI
  SINON 
      RETOURNE FAUX
  FINSI
FIN 
 
FONCTION DEPLACEMENT(X,Y,...) : ...
DEBUT
  Resultat := ...
  ...
  FIN        := DetermineFin(...) 
  SI PAS (FIN) ALORS 
  DEBUT
     SI DEPLACEMENTPOSSIBLE(X+1,Y) ALORS 
       DEPLACEMENT(X+1,Y,...)
     FINSI
     SI DEPLACEMENTPOSSIBLE(X,Y+1) ALORS 
        DEPLACEMENT(X,Y+1,...)
     FINSI
     SI DEPLACEMENTPOSSIBLE(X-1,Y) ALORS 
       DEPLACEMENT(X-1,Y,...)
     FINSI
     SI DEPLACEMENTPOSSIBLE(X,Y-1) ALORS 
      DEPLACEMENT(X,Y-1,...)
     FINSI
  FINSI
  Retourne Resultat
FIN

Voila mes deux cents

[tbc92]

A partir de la situation que je proposais, on peut permuter la case vide avec 2, 4 et 3, mais pas avec 8.
C'est un cylindre ; la colonne de droite et la colonne de gauche se touchent. Mais le haut du cylindre et le bas du cylindre ne se touchent pas.

[zekabyle]

Tu as raison, le haut et le bas ne se touchent pas et donc ne peuvent pas se permuter dans ce cas.