Génération de toutes les combinaisons uniques pour le puzzle "drive ya nuts"

Question

Il ya quelque temps, j'ai écrit un simple programme python pour forcer la solution unique pour le lecteur ya nuts puzzle.

alt text http://www.tabbykat.com/Drive%20ya%20Nuts%20Travel%20Sol%20c.jpg

Le casse-tête se compose de 7 hexagones avec les numéros 1-6 sur eux, et toutes les pièces doivent être alignés de telle sorte que chaque nombre est adjacent sur le même numéro sur la pièce suivante.

Le puzzle a ~1.4G possibilités non uniques: vous avez 7! options pour trier les morceaux par ordre (par exemple, center=0, top=1, continue dans le sens horaire ...). Après avoir trié les pièces, vous pouvez faire pivoter chaque pièce de 6 manières (chaque pièce est un hexagone), ainsi vous obtenez 6**7 rotations possibles pour une permutation donnée des 7 pièces. Totalisation: 7!*(6**7)=~1.4G possibilités. Le code Python suivant génère ces solutions possibles:

def rotations(p): 
    for i in range(len(p)): 
     yield p[i:] + p[:i] 

def permutations(l): 
    if len(l)<=1: 
     yield l 
    else: 
     for perm in permutations(l[1:]): 
      for i in range(len(perm)+1): 
       yield perm[:i] + l[0:1] + perm[i:] 

def constructs(l): 
    for p in permutations(l): 
     for c in product(*(rotations(x) for x in p)): 
      yield c 

Cependant, notez que le puzzle ne dispose que ~0.2G uniques solutions possibles, comme vous devez diviser le nombre total de possibilités de 6 puisque chaque solution est équivalente à 5 d'autres solutions (faites simplement pivoter le puzzle entier de 1/6 par tour).

Existe-t-il une meilleure façon de générer seulement les possibilités uniques pour ce puzzle?

Answer 1

Pour obtenir uniquement des solutions valables uniques, vous pouvez fixer l'orientation de la pièce au centre. Par exemple, vous pouvez supposer que le "1" sur la pièce au centre pointe toujours vers le haut.

Si vous ne le faites pas déjà, vous pouvez rendre votre programme beaucoup plus efficace en recherchant une solution valide après avoir placé chaque pièce. Une fois que vous avez placé deux pièces d'une manière invalide, vous n'avez pas besoin d'énumérer toutes les autres combinaisons invalides.

Answer 2

S'il n'y avait pas de pièce au centre, ce serait facile. Il suffit de considérer uniquement les situations où la pièce 0 est en haut. Mais nous pouvons étendre cette idée à la situation actuelle. Vous pouvez considérer uniquement les situations où la pièce i est au centre, et la pièce (i+1) % 7 est au sommet.

Answer 3

Je pense que l'espace de recherche est assez petit, bien que la programmation puisse être gênante.

Nous avons sept choix pour la pièce centrale. Ensuite nous avons 6 choix pour le pièce au dessus mais son orientation est fixe, car son bord inférieur doit correspondre au bord supérieur de la pièce centrale, et de même chaque fois que nous choisissons une pièce à enfiler dans une fente, l'orientation est fixe.

Il y a moins de choix pour les pièces restantes. Supposons pour l'exemple que nous avions choisi la pièce centrale et la pièce supérieure comme sur l'image; alors la pièce en haut à droite doit avoir des bords (5,3) consécutifs (dans le sens des aiguilles d'une montre) pour correspondre aux pièces en , et seulement trois des pièces ont une telle paire d'arêtes (et en fait nous avons déjà choisi l'une des eux comme la pièce centrale).

On pourrait d'abord construire une table avec une liste de pièces pour chaque paire de bord, puis pour chacun des 42 choix de centre et le haut procéder dans le sens horaire, choisir seulement parmi les pièces qui ont la paire nécessaire d'arêtes (pour faire correspondre la pièce centrale et la pièce précédemment placée) et revenir en arrière s'il n'y a pas de telles pièces. Je pense que la paire d'arêtes la plus commune est (1,6) qui se produit sur 4 pièces, deux autres paires de bords ((6,5) et (5,3)) se produisent sur 3 pièces, il y a 9 arêtes paires qui se produisent sur deux pièces, 14 qui se produisent sur 1 pièce et 4 qui ne se produisent pas du tout. Donc une estimation très pessimiste du nombre de choix que nous devons faire est 7 * 6 * 4 * 3 * 3 * 2 ou 3024.