[Énigme] Tetravex

 Niveau énigmesPartager :
			        
[Énigme] Tetravex
Posté par 
Alishisap  05-01-18 à 13:34
Bonjour à tous,

voici un puzzle largement inspiré du jeu Tetravex proposé sur certains systèmes Linux (au moins le mien !), développé par Lars Rydlinge.

Voici une grille de 36 cases contenant quatre chiffres chacune ainsi qu'un caractère alphanumérique d'identification en haut à gauche (pour ceux qui n'arrivent pas à lire, de gauche à droite et de haut en bas se trouvent les 26 lettres de l'alphabet suivis des chiffres de 0 à 9).

Le but est d'échanger les cases de cette grille (sans effectuer de rotation) afin d'obtenir une nouvelle grille, toujours de 6 par 6, de sorte à ce que lorsque deux cases se touchent, leur chiffre en contact soient identiques.

Par exemple, sur la grille originale, on voit que les cases V et 1 respectent cette propriété (9 en contact), de même que les cases G et H (3 en contact) mais ce n'est pas le cas pour les cases A et B car leur chiffre en contact sont différents (6 et 9).

Vous donnerez votre grille-réponse en donnant simplement le caractère d'identification de chaque case, dans l'ordre, de la nouvelle grille. Voici un exemple de réponse (bien évidemment faux) :

8 U Q D W E

5 F 4 3 I O

T 2 S Y L 7

0 B X 9 K 6

M 1 P C V N

J A G H R Z

Si plusieurs réponses sont possibles, une seule suffira.

Bonne chance ! 
 Posté par 
LittleFoxre : [Énigme] Tetravex  05-01-18 à 15:00
 Cliquez pour afficher

Il n'y a qu'une réponse que voici :

YQT2BF
COJI3M
5XUEW4
1G9VZR
LHD06A
8NSK7P

Calculée avec le code que voici (pour une raison inconnue il renvoie 6 fois la solution ne python 3 mais une fois en python 2):

def getPath(N):
    path = []
    for start in list(zip([0]*N,range(N))) + list(zip(range(1,N), [N-1]*(N-1))):
        x,y = start
        while 0 <= x < N and 0 <= y < N:
            path.append((x,y))
            x += 1
            y -= 1
    return path

G = [   '8867', '7920', '9729', '0911', '6401', '0652',
        '5831', '6360', '8746', '8818', '1034', '0166',
        '0521', '6684', '9558', '2641', '9659', '5186',
        '4161', '9385', '3136', '9039', '1504', '5583',
        '8079', '9055', '1306', '9715', '5277', '6250',
        '4214', '8275', '6538', '4382', '3626', '1399']

def solve(G,N):
    A = [[None]*N for _ in range(N)]
    for i,c in enumerate('ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789'):
        G[i] = G[i]+c
    path = getPath(N)
    G = set(G)
    def put(A,N,p,c):
        x,y = p
        if A[x][y] == c:
            return
        assert(A[x][y] == None)
        assert(y == 0 or A[x][y-1] == None or c[0] == A[x][y-1][3])
        assert(x == 0 or A[x-1][y] == None or c[1] == A[x-1][y][2])
        assert(x==N-1 or A[x+1][y] == None or c[2] == A[x+1][y][1])
        assert(y==N-1 or A[x][y+1] == None or c[3] == A[x][y+1][0])
        A[x][y] = c
    def reset(A,N,p):
        x,y = p
        A[x][y] = None
    def subsolve(p):
        if p < 0:
            yield A
            return
        for c in G:
            G.remove(c)
            try :
                put(A,N,path[p],c)
                for s in subsolve(p-1):
                    yield s
                reset(A,N,path[p])
            except AssertionError:
                pass 
            G.add(c)
    for s in subsolve(len(path)-1):
        show(s)

def show(A):
    s = ''
    for r in A:
        s += ' '.join(r) + '\n'
    print(s)
    
solve(G,6)    

 Posté par 
LittleFoxre : [Énigme] Tetravex  05-01-18 à 15:00
Merci pour le puzzle 
 Posté par 
Alishisapre : [Énigme] Tetravex  05-01-18 à 15:09
Bonjour LittleFox et merci pour ta participation ! 

 Cliquez pour afficher
Malheureusement ta réponse est fausse, par exemple tes deux premières cases Y et Q ne vérifient pas la priorité (7 et 6 en contact).
 Posté par 
dpire : [Énigme] Tetravex  06-01-18 à 10:18
Bonjour,

J'ai tenté à la main,mais rapidement on voit les limites du jeu.

Je vais essayer par les combinaisons.

A mon avis très compliqué.
 Posté par 
Alishisapre : [Énigme] Tetravex  06-01-18 à 15:05
Bonjour,

je reconnais, pour avoir testé, qu'à la main c'est très difficile. Il y a énormément de possibilités et de maigres indices (quoique je pense qu'avec beaucoup de patience et sans connaître à l'avance la réponse, ça doit être faisable).

En ce cas, pour permettre aux gens de participer sans que ça soit trop casse-tête, je propose, pour ceux qui n'arrivent pas à le résoudre entièrement, cette variante :

Essayez d'insérer le plus de cases possibles dans la grille 6x6 respectant la propriété. Attention, toutes les cases doivent être connectées (c'est-à-dire qu'il ne doit pas y avoir d'îlots).
 Posté par 
dpire : [Énigme] Tetravex  06-01-18 à 16:19
Je n'ai jamais dépassé  13 cases +quelques appendices....

Si tu connais la solution, il serait bon comme au sudoku de nous positionner

un minimum de cases sures .

Sinon seul un programme déroulant finira pas trouver ....
 Posté par 
veledare : [Énigme] Tetravex  06-01-18 à 18:55
bonjour,

Alishisap

 Cliquez pour afficher
j'ai essayé ce matin(à la main bien sûr sinon je ne sais pas faire) mais sans succès,j' ai commencé  par  chercher  les cases candidates à la première ligne mais il y a beaucoup de cas,je recommencerai car j'aime bien ce genre de recherche

merci pour cet exercice  pas facile
 Posté par 
Alishisapre : [Énigme] Tetravex  06-01-18 à 19:17
dpi :

oui, je connais la solution. 

Bravo, 13 cases c'est bien. 

Je m'abstiendrai pour l'heure de donner des cases sûres car après quelques recherches à la main, je sais qu'on peut, à l'aide de raisonnements logiques, de l'astuce et indépendamment de la connaissance a priori de la réponse, trouver au moins 4 cases certaines (c'est évidemment bien insuffisant pour résoudre toute la grille, mais je me dis qu'on peut en trouver d'autres).

Pour l'heure, j'attends de voir comment les membres réagissent. 

Après, il est bien sûr possible de le faire informatiquement, mais l'esprit était plutôt de le faire à la main (ce qui n'enlève pas l'adresse d'un tel programme qui résoudrait correctement ce puzzle  ).

veleda :

 Cliquez pour afficher
Courage ! 
 Posté par 
javatasmaniere : [Énigme] Tetravex  06-01-18 à 23:18
Bonjour

 Cliquez pour afficher

Merci à l'ordinateur qui a trimé 12 minutes

Une seule solution

Et la vision globale (chaque repère est encadré par ses 4 chiffres)

 Posté par 
Alishisapre : [Énigme] Tetravex  07-01-18 à 00:34
Bonsoir javatasmanie et merci d'avoir participé. 

 Cliquez pour afficher
Bravo ! 

Tu es le premier à avoir trouvé la bonne réponse (une petite coquille semble s'être malencontreusement glissée dans le programme de LittleFox). 

Vous êtes en tout cas deux à affirmer qu'il n'y a qu'une réponse possible. 
 Posté par 
vhamre : [Énigme] Tetravex  07-01-18 à 01:39
Bonne nuit

 Cliquez pour afficher
Une seule réponse possible
YC51L8
QOXGHN
TJU9DS
2IEV0K
B3WZ67
FM4RAP   programme compilé en VB.net durée d'exécution autour de 1 seconde

 Posté par 
vhamre : [Énigme] Tetravex  07-01-18 à 01:41
mille excuses, une { au lieu de [ n'a pas blanké....Mauvaise vue !

**** lafol > c'est réparé 
 Posté par 
vhamre : [Énigme] Tetravex  07-01-18 à 02:02
 Cliquez pour afficher
quelques statistiques pour me racheter :

on peut mettre côte à cote horizontalement 141 couples

on peut mettre côte à cote horizontalement 532 trios

il y a 172 carrés de 3 par 3 possibles

qui se réduisent à 14 assemblages possibles de 3 horizontalement par 6 verticalement

Si l'on pense pouvoir résoudre par bandes de 6 éléments assemblés horizontalement

il y a 24690 bandes possibles...
 Posté par 
dpire : [Énigme] Tetravex  07-01-18 à 09:49
Bonjour,

A la main je suis arrivé à cela.
Je vais voir avec les blanks où j'ai dérivé.....
 Cliquez pour afficher

 Posté par 
javatasmaniere : [Énigme] Tetravex  07-01-18 à 09:54
salut vlam

 Cliquez pour afficher

résolu par bandes verticales, 

puis recherche de couples compatibles de bandes verticales, 

puis assemblage de ces couples en séries de 6 avec exclusions pour cause de carrés dupliqués

Calcul du nombre de suites verticales de longueur 6 valides : 27297,

liste déterminée en 00:00:00.176

Listes des 588 bandes compatibles déterminée en 00:10:32.52

Nombre de solutions trouvées : 1 en 00:01:14.15

 Posté par 
Alishisapre : [Énigme] Tetravex  07-01-18 à 10:20
Bonjour vham et merci d'avoir participé. 

 Cliquez pour afficher
Bravo à toi aussi ! 

Et merci pour ces statistiques intéressantes ! Et d'avoir (ainsi que javatasmanie) donner une démarche de ton programme. 

dpi :

 Cliquez pour afficher
Et bien c'est franchement pas mal du tout ! Si tu as envie d'un indice : tout ton carré 3 par 3 en bas à gauche est correct. 
 Posté par 
dpire : [Énigme] Tetravex  07-01-18 à 10:37
Félicitations à vham...

Mon idée de départ vient de l'unicité de 4601 qui impose soit IE soit PE

Ensuite on remarque l'unicité  de  9702 qui impose 2 à gauche de I.

Ensuite on teste au mieux...ma dérive vient de 9 au lieu de 0  après K
 Posté par 
dpire : [Énigme] Tetravex  07-01-18 à 10:38
Après V pardon!
 Posté par 
LittleFoxre : [Énigme] Tetravex  09-01-18 à 10:58
Aaaaah ma réponse est la même que javatasmanie et vham. Juste transposée. Je me suis trompé dans mes coordonées lors de l'impression du résultat 
 Posté par 
vhamre : [Énigme] Tetravex  09-01-18 à 23:00
Bonsoir,

--> Littlefox

j'ai sagement programmé en VB.net

j'aimerais suivre votre programme Python

Quelques commentaires et le cheminement de l'algorithme m'y aiderait surement.

Merci par avance
 Posté par 
Alishisapre : [Énigme] Tetravex  10-01-18 à 10:41
LittleFox : oui, j'avais remarqué que c'était la solution transposée, je m'étais douté que tu t'en mordrais les doigts. 

Compliments pour ton habile programme ! 
 Posté par 
LittleFoxre : [Énigme] Tetravex  10-01-18 à 18:11
@vham

Je pars d'un grille vide de 6x6 (A) et d'un ensemble de cases à mettre dedans (G).

J'essaie de remplir la grille en partant du coin en haut à gauche puis en suivant des diagonales de façon à avoir le maximum de contraintes le plus tôt possible (getPath()).

subsolve(p) signifie qu'il reste p cases à insérer dans la grille et donc que G ne contient plus que p cases. Pour chacune de ces cases j'essaie de l'insérer au Pème emplacement  de getPath (put(A,N,p,c)). Si ça marche j'avance à la case de la grille suivante (appel récursif à subsolve). S'il n'y a plus de case à mettre alors c'est que j'ai trouvé une solution et je l'imprime. Dans tout les cas je reviens en arrière, enlève la case de la grille (reset) et remet la case courante dans l'ensemble des case G. Je fais ainsi jusqu'à avoir testé toutes les possibilités. 

Ce programme n'est pas très intelligent, c'est du test et backtracking en essayant de voir que la combinaison est impossible le plus tôt possible.
 Posté par 
vhamre : [Énigme] Tetravex  11-01-18 à 18:05
Bonjour,

Merci Littlefox

J'étais réticent à écrire une fonction récursive qui serait appelée 36 fois,

transposée en VB.net elle donne le résultat encore plus rapidement que le programme que j'ai écrit en premier
  Posté par 
LittleFoxre : [Énigme] Tetravex  11-01-18 à 18:42

Oui, en python non plus les récursions de son pas conseillées : les stackframe sont larges et prennent du temps à être empilée et inversement.

D'ailleurs il y a une limite software en python qui est par défaut à 1000 récursions de profondeur (on peut modifier cette limite). 

On en est loin avec nos 36 récursions .