Jeu permutation roues

[sanson87]

Bonjour,

Je vous soumets ce casse-tête trouvé chez un ami pour lequel je me demande s'il existe un algorithme de résolution efficace, c'est à dire non basé sur la force brute et en temps non exponentiel (en fonction du nombre de roues).
Le jeu se compose de 6 roues superposées de rayon dégressif, et sur chaque roue il y a 6 nombres entiers répartis autour. Le but est de trouver la permutation des 6 roues permettant d'aligner les 6 colonnes de nombres de sorte que la somme des nombres sur chaque colonne soit égale à 100, dans ce style:

https://youtu.be/TcYytJOleAM

Je joins les nombres sur chaque roue pour info:

{1,4,25,29,6,35}
{0,10,18,5,34,33},
{24,2,26,8,21,19}
{11,16,28,13,32,0}
{14,23,7,27,17,12}
{9,15,20,22,31,3}

1 ligne correspond à une roue, on n'a le droit qu'à des permutations circulaires sur chaque roue du coup.
Est-ce que ce problème peut être rapproché d'un problème classique connu et pour lequel on sait s'il existe un algorithme de résolution efficace (c'est à dire pas exponentiel en fonction du nombre de roues) ?

Merci

[pascal16]

les lignes 3 et 5 ont un faible écart-type
en essayant de réduire l'écart-type par somme de deux lignes sur les autres lignes, on peut sans doute limiter le nombre de calculs, mais c'est statistique, c'est pas garanti, il faudra plusieurs essais.

[nodgim]

Oui, plusieurs essais, environ 6 ^ 6 = 46656. -1 puisque celui présenté ne marche pas.

Cet objet est similaire à un véritable cadenas à code chiffres.

Vu comme ça, il ne semble pas possible de trouver une suite convergente.

[Ben314]

Salut,
J'ai pas trop regardé l'exemple en détail, mais, à mon avis :
- Si on n'a pas d'hypothèse particulières sur les nombres situées sur les différentes roues (ça peut être des réels quelconques), j'aurais tendance à penser qu'il va être assez difficile de produire un algorithme général non exponentiel par rapport au nombre de roues.
- Si on a des hypothèses sur les nombres situés sur les roues, par exemple que ce sont des nombres entiers distincts alors, il y a peut-être moyen d'améliorer l'algorithme.

En tout cas, le problème me semble intéressant, principalement avec les hypothèse du 2).

[beagle]

Ils ne se sont pas cassés la tète avec
pour la fabrication
c'est un carré magique dont on a déjà une dimension on connait les rangées (ou les colonnes)
et on cherche juste à trouver les colonnes, sachant que l'ordre est imposé (il n' y a pas permutations des nombres dans une rangée, ils sont déjà cote à cote imposés).

Donc, sachant qu'il n' y a pas un algo qui donne l'ensemble des carrés magiques,
je vois mal un algo décoder l'ensemble des casse tète.
En matière de carrés magiques on ne construit pas un ordre pair comme un impair,
un 4n comme un simple pair, un impair premier d'un impair non premier aide a savoir ce que l'on peut faire.

Donc si le gars te donne un casse tète tiré d'un carré magique d'ordre impair,
le gars ne se fait ch.er et va prendre une méthode de construction classique,
ben si c'est un regulier, je ne fais aucun calcul pour trouver le bon ordre.

Ici on est en 6x6 c'est le plus "bordelique" et les structures faudrait que je revois cela pour dire que l'on a pas tout à essayer, mais prioritairement tel avec tel…

Bref je vois mal un algo général pour tout n.
apres des astuces pour simplifier les calculs je n'y connais rien en informatique , mais bien sur cela doit se faire probablement...

[sanson87]

Salut,
J'ai pas trop regardé l'exemple en détail, mais, à mon avis :
- Si on n'a pas d'hypothèse particulières sur les nombres situées sur les différentes roues (ça peut être des réels quelconques), j'aurais tendance à penser qu'il va être assez difficile de produire un algorithme général non exponentiel par rapport au nombre de roues.
- Si on a des hypothèses sur les nombres situés sur les roues, par exemple que ce sont des nombres entiers distincts alors, il y a peut-être moyen d'améliorer l'algorithme.

En tout cas, le problème me semble intéressant, principalement avec les hypothèse du 2).

Merci, la seule hypothèse est que ce sont des nombres entiers positifs, ils ne sont pas nécessairement distincts.

[beagle]

"Merci, la seule hypothèse est que ce sont des nombres entiers positifs, ils ne sont pas nécessairement distincts."

j'ai répondu pour un cas particulier, celui des carrés magiques,
alors si le cas est encore plus généraliste et où on peut mettre n'importe quoi, la réponse doit ètre la même
pas de "truc" véritable.

S'agissant du carré magique 6x6 mis en exemple, en replongeant dans la structure des 6x6 "réguliers", il m'a semblé regulier de prime abord, ben avec un minimum d'essai il est remonté.

[sanson87]

"Merci, la seule hypothèse est que ce sont des nombres entiers positifs, ils ne sont pas nécessairement distincts."

j'ai répondu pour un cas particulier, celui des carrés magiques,
alors si le cas est encore plus généraliste et où on peut mettre n'importe quoi, la réponse doit ètre la même
pas de "truc" véritable.

S'agissant du carré magique 6x6 mis en exemple, en replongeant dans la structure des 6x6 "réguliers", il m'a semblé regulier de prime abord, ben avec un minimum d'essai il est remonté.

Tu as raison je n'avais même pas remarqué que la somme de chaque roue est égale à 100.
Je ne sais pas exactement si ça aide vraiment à trouver un algorithme en temps polynomial.
En tout cas si le problème est np-difficile ça doit pouvoir se prouver aussi.

[sanson87]

Donc, sachant qu'il n' y a pas un algo qui donne l'ensemble des carrés magiques,
je vois mal un algo décoder l'ensemble des casse tète.

Le problème de génération de l'ensemble des carrés magiques de taille nxn ne me parait pas équivalent à celui-ci, donc je ne suis pas entièrement convaincu qu'on puisse encore en déduire qu'il n'existe pas d'algorithme en temps polynomial pour ce casse-tête.

[beagle]

Pour l'exemple que tu as donné on doit pouvoir limiter sérieusement les recherches par rapport a force brute,
pour le cas général je n'y connais rien en algomachin, à mes yeux c'est un truc qui fait mal? ou qui fait moins mal aux maths ?

[Ben314]

Je pense comme sanson87 : générer un carré semi-magique ou être capable de le reconstituer en connaissant les lignes à permutation circulaire prés, ça ne me semble pas être le même problème.

Sinon, un truc possible comme algo., c'est un "parcours de graphe", c'est à dire de commencer par choisir au hasard une position des différentes roues, de calculer les sommes sur chaque alignement et la différence qu'elles ont avec le résultat escompté, puis de prendre la somme des valeur absolue des écarts (ou la somme des carrés) qui sert d'indicateur de "la distance" à laquelle on est de la solution.
(*) Si ça fait zéro, ben c'est gagné, sinon, on regarde si on arrive à faire baisser cette distance en ne tournant qu'une seule roue (ou alors en ne tournant que deux roues : ça reste raisonnable en terme de temps) :
- Si oui, on le fait et on retourne en (*).
- Si non, on est dans une impasse : on retire une autre position de départ au hasard et on recommence tout.

Dans la pratique, ça m'amuserais de voir si ça donne la solution ou pas (et en combien d'essais...)
Quand j'aurais du temps, j'essayerais ça...

[pascal16]

dans un temps toujours NP, mais en accélérant le processus
-> on passe dans Z/2Z, chaque série de 6 nombres est alors 1 seul nombre binaire 6 bits, la somme doit finir par six fois le chiffre 0 en binaire.
-> un rotation est alors : un décalage à gauche binaire+récupération du bit 5 à remettre en 0 ou en base 10, une multiplication par 2, le chiffre des unités étant soit le bit 5 qu'on a récupéré en binaire ou la partie entière d'une division par 32 du nombre.
-> on garde toutes les permutations qui marchent
-> on repasse dans N et on ne teste que les permutations qui marchent

vu qu'on part de 5^6 possibilités, ça sera bien plus rapide que le "compte est bon"

[pascal16]

Il y a dix minutes, je me lance et dit :
je fais un petite fonction de rotation de vecteur
je fais une petite fonction de vérification
déclaration des 6 vecteurs d'entiers
les 5 boucles imbriquées.
je lance et (0,3,2,4,0,3) est la permutation de chaque ligne à faire
temps d'exécution <0.1s

[sanson87]

Il y a dix minutes, je me lance et dit :
je fais un petite fonction de rotation de vecteur
je fais une petite fonction de vérification
déclaration des 6 vecteurs d'entiers
les 5 boucles imbriquées.
je lance et (0,3,2,4,0,3) est la permutation de chaque ligne à faire
temps d'exécution <0.1s

Héhé on est bien d'accord que le temps de calcul n'est absolument pas un sujet pour n = 6
Bien joué en tout cas au moins on a la solution pour cette instance

[Ben314]

Sur un 12x12 de ce type là (qui n'est pas un carré magique) :

Code: Tout sélectionner

{ { 20, 29, 31, 26, 28,  6,  5, 31,  9, 18, 34,  2},
  { 29, 36,  4, 33, 23, 28, 36, 25, 11, 22, 44, 25},
  { 19, 39, 18, 11,  2, 10,  8, 21, 38, 29, 19,  3},
  {  9,  8,  6, -2, 25, 15, 40, 12, 13, 41,  7, 27},
  { 23, -6, 24, 15, 11, 24, 12, 33, 31, 23, 20, 30},
  {  7, 17, 34, -1, -3, 23,  3, 17, 31, 16, 38, 18},
  { 49, 40, 24, -2,  2, 19, 16, 34, 19, 24, 20, 42},
  { 13, 10, 29, 34, 20, 20,  6, 12, 22, 25, 27,  6},
  { 23, 22, 24, 12, 18, 27, 30, 16, 18, 11, 18,  8},
  { 12,  2, 28, 17, 30, 13, -7, 12, 15, 28, 21, 19},
  { 25, 12, 22, 17, 34,  3, 38, 26, 18, 44, 30, 19},
  { 18, 23, 18,  6, 36, 31,  2,  9, 18, 14, 40, 36} }

Avec une procédure "random" sur le graphe puis recherche "dans le sens de la descente" (en prenant la somme des valeurs absolue des écarts comme mesure de la distance à la solution), j'ai des temps qui vont de 20 secondes à plus de 6 minutes.

Après, je me demande s'il n'y a pas moyen d'utiliser Fourrier pour ce type de truc :
Si sur une certaine roue on a les nombres (où nombre de secteurs) alors, on peut calculer tels que, pour tout on ait avec et ce "codage" de la roue a le bon goût :
1) D'être additif : ajouter les secteurs de deux roues, c'est ajouter les des deux roues.
2) De se comporter "pas trop mal" concernant la rotation d'une roue : si on tourne la roue de les nouveaux coeff. sont .