Comment accumuler efficacement des billards pour un jeu de 8 balles?

Question

Depuis le soutirage de boules de billard pour le 8-ball de jeu peut être effectuée en vertu de plusieurs règles, voici les rayonnages je me réfère à:

c'est à dire le 8-ball doit être dans le centre, et sur les côtés les rayures et les solides doit alterner. Les deux autres boules (une bande et un solide) n'a pas d'importance.

Supposons que vous venez de terminer un jeu, recueillir les boules, les mettre dans la baie et continuer à les organiser pour en commencer une nouvelle. Ils sont maintenant dans un ordre aléatoire. Comment procédez-vous?

_{Avertissement: l'art de la peinture suit}

Une approche simple serait de commencer dans l'ordre, de haut -> bas et de gauche -> droite.

Ainsi, par exemple, on suppose 1 est à la bonne position. 5 n'est pas, nous l'échanger avec 2, puis nous swap 4 avec 3 (ou 8), mais ce serait déjà inefficace, parce que nous avons déplacé l' 4 pour le centre ou l' 8 en 4'à la position - c'est à dire pas où il doit être à la fin.

Il y a aussi la décision de quels types de balles que nous voulons dans les coins afin d'être faite. Comment décidez-vous qui d'avance? Devriez-vous prendre en compte combien de balles sont déjà en place? Dans mon exemple, si vous souhaitez que le gris dans les coins, vous avez déjà 3 en place (les boules 1,10,14). Si vous voulez les blancs dans les coins, vous avez seulement 2 d'entre eux en place (2,11). Est-ce important?

Pour formaliser cela, on peut supposer il y a deux trois opérations que nous pouvons faire:

• permuter deux boules adjacentes
• permuter deux non-boules adjacentes
• tourner rack

Puisque l'on peut utiliser les deux mains, supposons que nous pouvons paralléliser la première opération (swap 2 couple de balles dans le même temps), alors que l'on ne peut permuter deux non adjacents balles à la fois.

Quelle est l'approche la mieux adaptée pour cette tâche qui minimise le temps (dans les unités de temps décrite)? Serait gourmand être le mieux pour cela? (c'est la façon dont je le fais quand je les accumuler, je suppose)

EDIT: Comme par existante (ou des réponses précédentes) - vous croyez peut-être avoir plus de rayures que les solides dans les coins signifie que les progrès préfèrent les coins de ne pas dire qu'il n'est pas vrai, mais si vous faites cette hypothèse, merci de le prouver.

Answer 1

REMARQUE! Cette réponse a été écrit avant la rotation de l'exigence. Procéder à votre propre attention :)

Voici ma première examiner le problème.

La première chose à faire est de calculer la parité de l'extérieur - +1 si ça colle 'bandes dans les coins", -1 si elle serait d'ajustement "de solides dans les coins", +0 si c'est le 8-ball. Cela nous donne une plage de +12 à -12, et nous nous efforçons pour l'extrême nous sont plus proches. (Si +0, pick +12 ou aléatoire)

Par exemple, c'est +1 +1 +1 -1 -1 +1 -1 -1 -1 +1 +0 -1 et donc c'est -1 penchée solides dans les coins:

x o x x o
 x o x o
  8 x o
   o x
    o

La prochaine chose à faire est de déplacer la boule 8 dans le centre. Si vous pouvez le faire de deux adjacents swaps avec elle qui se déplace de deux balles dans la position, plutôt qu'un seul adjacentes swap qui se déplace d'une balle dans la position (ou une non-adjacents si c'est dans un coin), faites-le.

x o x x o
 x 8 x o
  o x o
   o x
    o

Après nous déplacer la boule 8, toutes les combinaisons de deux adjacents à des swaps de partage d'une balle peut être produite par un non adjacentes de swap à l'identique, de sorte que nous avons à considérer beaucoup moins de complexité à la fois.

Commande tous les mouvements restants par cette priorité:

-Un échange entre les deux boules adjacentes sur l'extérieur est d'une valeur de 4' (2 si c'est notre dernière)

-Un échange entre les deux boules adjacentes, l'une sur l'extérieur, est "d'une valeur de 2' (1 si c'est notre dernière)

-Un échange entre les deux boules sur l'extérieur est d'une valeur de 2'

-Un échange entre les deux boules, une à l'extérieur, est d'une valeur de 1'

Et de les exécuter à partir du haut vers le bas.

Nous nous déplaçons donc le o sur le haut, à gauche (4), le joint sur le côté droit (2), le joint en bas à gauche dans (2) et le swap x en haut avec le o dans le milieu (2). Nous nous sommes retrouvés à cinq swaps dans un 2-2-1 série, donc, trois mouvements.

o x o x o
 x 8 x x
  o o o
   x x
    o

(Notamment, celui-ci aurait été résolu aussi vite si nous nous sommes efforcés de rayures dans les coins.)

x x o o x
 o 8 o x
  o x o
   x o
    x

Je pense qu'il est impossible d'exiger de 4 tours, mais je n'ai pas prouvé à moi-même encore.

Un autre exemple:

Cela a une parité de +1, de sorte que nous visons pour les bandes dans les coins:

8 o o o x
 o o o x
  o x x
   x x
    x

swap 8 boule de centre x (1-)

x o o o x
 o o o x
  o 8 x
   x x
    x

permuter deux adjacents sur l'extérieur, 4 points (1-1)

x o o o x
 o o o x
  x 8 x
   o x
    x

swap arête adjacente dans le centre, à 2 points (1 à 2)

x o o o x
 o o x o
  x 8 x
   o x
    x

swap bord à bord, 2 points (1-2-1-)

x o x o x
 o o x o
  x 8 x
   o o
    x

3 se déplace.

EDIT: Cela fonctionne très bien pour l'exemple, dans le message d'ouverture, de le résoudre en deux coups:

Cela a une parité de +1, de sorte que nous visons pour les bandes dans les coins:

x x o o x
 o o x o
  o o 8
   x x
    x

Swap de 8 x sur le bord de la avec o dans le centre (la résolution de deux bords) (2-)

x x o o x
 o o x o
  o 8 x
   x o
    x

swap adjacentes o et x en haut et en bas à gauche (afin de résoudre les quatre bords) (2-2-)

x o x o x
 o o x o
  x 8 x
   o o
    x

2 se déplace.

Answer 2

Vous avez 2 boules de huit, tricheur.

Dans l'exemple donné, la solution prend 2 coups:

2-5, 3-8
3-4, 11-12

Une solution optimale est la meilleure trouvé en configurant le problème de la programmation dynamique (DP). Car le problème est multi-étape avec les coûts fixes et sans incertitudes, une DP matrice d'exister que de façon optimale pour résoudre le problème.

Pour créer la matrice: a noter que la comptabilité pour les symétries de la 8-ball peut être dans l'un des 9 positions. Les solides peuvent être organisées dans les environ (14 choisir 7)/2=1716 différentes façons. Cela signifie que le nombre total de rack configurations est d'environ 1716 * 9 = 15,444. Ainsi, vous avez 15,444 différents états possibles. Calculer le coût d'aller de l'un de ces états à un autre. Cette résultats dans une matrice avec 15,444 * 15,444 cellules, soit environ un quart de milliards de cellules. Identifier tous les la fin de l'état des cellules. Pour résoudre la matrice de vous de largeur de la recherche vers l'avant à partir de l'état initial jusqu'à ce que vous atteindre un état final (ou jusqu'à ce que vous atteignez un coût total plus élevé que le minimum actuel de coût). En faisant cela, vous aurez prouvable trouvé tout le moins le coût des chemins.

Notez que la solution ci-dessus est un peu naïf et peut être optimisé de différentes manières pour obtenir une plus petite matrice. Par exemple, vous pouvez utiliser la symétrie de rotation de réduire le nombre de cellules et ajouter un coût de 1 (pour la rotation du rack) pour les chemins qui sont correct sauf pour le 8-ball dans l'un des bas-centre de positions.

Pseudocode:

Create DP Matrix:

(1) determine number of possible arrangements, A, of balls
(2) for each arrangement, make a list of possible unique moves  
---- the possible moves are:  
------- rotating right  
------- rotating left  
------- exchanging any pair of balls  
------- exchanging any two pairs of adjacent balls  
(3) for each move in A store a pointer to the resulting arrangement  
(4) for each arrangment make an attribute indicating whether it is an end state  

Solve Problem  
(5) goto arrangement for starting position S  
(6) set best-cost-so-far (BCSF) variable to infinity
(6) breadth search from S, accumulating current cost CC as +1 for each transition
(7) if you reach an end state CC < BCSF, then set BCSF = CC and make solution list contain only the current path
(8) if you reach an end state CC = BCSF, then add path to solution list
(9) if CC > BCSF abandon branch and try next branch

The result will be a list of all possible solutions and the minimum cost BCSF.

Answer 3

Il y a 15!/(7!7!1!)=51480 positions possibles. De ceux-ci, 4 sont en finale: les balles de 8 et 9 peuvent être échangés, et à rayures/matières solides peuvent être inversés. Nous allons dire que ces postes sont à une distance de 0.

Pour chacun de ces 4 positions, de générer tous les mouvements possibles (1 swap ou 2 adjacentes swaps). Pour chaque position générés par ces mouvements qui n'a pas été vu avant, rappelez-vous, dont le déménagement a été utilisé pour générer, et de donner à ces positions à distance 1. Puis faire la même chose pour chaque position à une distance de 1 et de donner de nouveaux postes à distance 2. Continuez à faire cela jusqu'à ce qu'il n'y a plus de nouvelles positions.

Cela rend l'utilisation du fait que, comme @DPenner souligné, les rotations peuvent toujours être remplacés à côté d'un déménagement.

Depuis les swaps sont leur propre inverse, le déplacer pour aller de la position A à B est aussi la mesure qui va prendre la position B à A.

Donc, vous vous retrouvez avec une liste de tous les postes, et pour chaque position qui n'est pas une position définitive une mesure qui va avec certitude à la rapprocher d'une position finale.

Vous trouverez qu'il ya 232 positions que peut prendre au moins 4 coups. (EDIT: Mon contiguïté table contenait une erreur plus tôt.) Par exemple:

      6-9,14-15     2-12       2-5,4-7       1-2
    x           x           x           x           o
   x x         x x         8 x         o x         x x
  x o x   =>  x o o   =>  x o o   =>  o 8 o   =>  o 8 o
 o o o x     o o x x     o o x x     x o x x     x o x x
o 8 o o x   o 8 o x o   o x o x o   o x o x o   o x o x o

Il n'existe pas de positions initiales que prendre plus de 4 coups.

EDIT: La stratégie de l'échange dans les 8-la première balle n'est pas optimale. Par exemple:

         5-11     12-13,14-15    4-7,6-10
    x            x            x            x
   o o          o o          o o          o o
  o x o   =>   o 8 o   =>   o 8 o   =>   x 8 x
 x o x x      x o x x      x o x x      o o x o
8 x o x o    x x o x o    x o x o x    x o x o x

mais nous pouvons faire mieux:

         3-11       1-2,3-5
    x            x            o
   o o          o 8          x x
  o x o   =>   o x o   =>   o 8 o
 x o x x      x o x x      x o x x
8 x o x o    o x o x o    o x o x o

Le problème, c'est que x est le mauvais genre pour le coin, donc nous perdre d'un coup.

Plutôt, la stratégie devrait être de chercher un ballon qui est à sa place, mais qui ne peuvent pas être échangés avec d'un côté de la balle, soit parce qu'ils sont du même type, ou s'ils sont déjà en position. Les coins doivent être privilégiées, parce qu'ils ont le moins adjacent swap options. Il doit être échangé avec un ballon de type correct pour le poste. Si le ballon lors de la première boule de la position finale de l'est de la mauvaise sorte, adjacente d'une balle dans le mauvais endroit doit être choisi. De cette façon, une autre adjacente swap va mettre les balles dans le bon endroit final.

Dans le ci-dessus (compteur), par exemple, le 8-ball nécessite un long swap pour arriver à sa position finale. Cependant, le x dans le #5 est le mauvais genre, donc à la place on les échange avec un côté o, de la 2e à la 2e rangée.

L'exemple précédent avec 4 coups est résolu comme suit:

        11-2         12-5        13-3       9-10
    x           x           x           x           x
   x x         o x         o x         o o         o o
  x o x   =>  x o x   =>  x 8 x   =>  x 8 x   =>  x 8 x
 o o o x     o o o x     o o o x     o o o x     o o x o
o 8 o o x   x 8 o o x   x o o o x   x o x o x   x o x o x

Dans la première étape, nous choisissons le o dans le coin en bas à gauche. Le premier x est à la position deux. Ensuite, nous choisissons le 8 au n ° 12, que nous pouvons ramener à la maison #5. Le o dans le milieu de la ligne du bas est la suivante. Nous échangeons avec le prochain mal placée x au n ° 3. Enfin, nous swap #9 et #10 pour obtenir la valeur finale de rack. Le chemin est différent d'avant, mais nous avons toujours fait en 4 coups.

EDIT: Un point de plus: lors de l'exécution adjacentes swaps, la préférence devrait être donnée à ceux qui ne finissent pas avec deux balles dans leur position finale. La raison en est que cela signifie qu'au moins deux mouvements sont nécessaires dans tous les, et il est donc préférable de faire le premier pas dès que possible.

Par exemple, la grille dans le problème peut être réglé en deux coups de: (2-4),(5,6) et (3 à 6),(12-13). La boule 8 a été déplacé vers sa position finale d'abord, même si la bille blanche, il a été échangé avec n'est pas encore dans sa position finale. Si le périmètre de deux swaps (2-4),(12-13) ont été effectuées d'abord, vous avez encore besoin de deux déplacements pour se rendre à la finale rack, en prenant un sous-optimale de 3 coups au total.

Answer 4

Cela a été difficile, profondément frustrant, et le plaisir question tout à la fois. Ma conjecture est que la suite est une solution optimale:

• Choisir les rayures ou les solides sont dans les coins basé sur Patashu de la méthode de la parité
• Aucune rotation
• À chaque fois, de mesurer, de faire le mouvement qui les scores les plus élevés, sauf lorsqu'un +3 déplacez pouvez mettre la 8-ball dans le centre
• En cas d'égalité, le choix n'a pas d'importance? Edit: Voir la note au bas. Les liens sont difficiles.

(Je suis de notation se déplace en fonction de la différence nette entre le nombre de balles dans les positions correctes.)

Voici deux exemples de racks:

    x            8
   x x          o o
  o o x        o o x
 o o x x      o x x x
8 o o o x    o x x o x

Si nous nombre les positions 1 à 15 de gauche à droite, puis de haut en bas, le premier rack résout comme (2-4/3-5)(5-11)(10-13) et le deuxième support résout comme (4-8/11-12)(5-10)(1-5).

Ma dernière tentative de preuve, une partie de celle-ci échoue à seulement 11 racks jusqu'à symétrie (avec les deux indiqué ci-dessus étant une variation de ceux qui ont échoué). Voici deux lemmes j'ai trouvé dans mes tentatives qui, nous l'espérons aider les autres avec des preuves.

Lemme 1: les Rotations ne sont pas nécessaires

Notez que si nous avons besoin de faire une rotation à un certain point dans notre solution, il n'a pas d'importance lors de la rotation ne change pas tout swaps). De plus, nous avons seulement besoin au plus une rotation depuis 2 rotations dans le sens horaire = 1 rotation anti-horaire et vice-versa.

Donc permet de choisir pour faire de la rotation de notre dernier déplacement si nécessaire. À ce stade, en raison de symétrie de rotation de l'extérieur, l'extérieur doit être correcte. Ainsi, le 8-ball serait dans l'une des trois balles. Si son dans le bon endroit, nous n'avons pas besoin de rotation. Sinon, on pourrait l'utiliser, mais notez qu'un échange serait également remplir la grille. Il est donc inutile dans une solution optimale.

Lemme 2: Gourmande est optimale si elle résout le rack en moins de 3 coups

Stratégie d' A être le gourmand de la solution et de la stratégie B être non-greedy solution d'essayer d'être plus rapide. B doit faire au moins un non-greedy déplacer. Par nécessité, ce ne peut être le dernier mouvement. Par conséquent, si A prend n spires de remplir une grille, B doit rendre sa non-greedy déplacer au tour n-2 ou une version antérieure. Cela signifie que si A résout le rack à 2 tours ou moins, il est optimal.

---

Edit: eh Bien, j'ai juste couru mon algorithme sur des programmes de test, et a trouvé son pas encore compatibles. En fait, il semble que les liens sont très difficile à briser. Considérez les points suivants rack:

    x
   o o
  x o x
 x 8 o x
x o o x o

Mon algorithme effectuez l'une des opérations suivantes déplacer des séquences: (5-8/13-14)(7-8/10-15), (5-8/10-15)(7-8/13-14), (5-8/14-15)(10-13)(7-8), (5-8/14-15)(7-8)(10-13), (5-8/9-10)(14-15)(7-13), (5-8/9-10)(7-13)(14-15), (5-8/9-10)(13-14)(7-15), ou (5-8/9-10)(7-15)(13-14). Les deux premiers de la résoudre dans le meilleur des 2 temps-mesures, mais les autres le résoudre en 3 temps-mesures. Le problème est que l' (14-15) et le (9-10) commutateur de ruiner une possible +4 passer le deuxième tour. Une modification de cet algorithme, nécessiterait sans doute un "look-ahead", qui ensuite se complique rapidement. Je commence à penser que il n'y a pas de "simple" solution, et la solution par @JeffreySax est le chemin à parcourir. Notez également que cette rack également défaites le gourmand de la solution. La gourmande solution serait de le faire (13-14/10-15)(5-8)(7-8) ou (13-14/10-15)(7-8)(5-8).

Answer 5

Salut, d'abord je dois dire que c'est un très amusant et intéressant problème, et quelque chose que je n'ai pas pensé lors des soutirages, bien qu'à un total de 15 balles de quelques mouvements supplémentaires ne serait pas important.

Depuis le soutirage, la description et l'image, nous obtenons les suivantes règles:

1. les coins sont toujours du même type
2. milieu de chaque côté est toujours le même type de coin
3. chaque set de 2 boules de toucher les coins sont toujours du même type (et le type opposé en coin)
4. dans le triangle a toujours le 8ball, d'une bande et un solide (et 8ball est sur le dessus)
5. sur les côtés, des boules de près les uns des autres sera toujours autre type de

Comme @DPenner a déclaré en Lemma 1, les rotations ne sont pas nécessaires, car ils peuvent être remplacés par un échange, à condition que le coût est le même. Si vous êtes un Rubick ventilateur et choisissez de les utiliser, vous devez seulement une.

Ne peut pas être résolu en moins de 4 swaps! ( toujours )

Votre exemple de l'image est mieux pour le prouver, ce qui, de toute façon vous comptez vous aurez besoin pour déloger 6 couleur des boules à partir de leurs positions et la 8ball => c'est 3½ swaps et parce qu'un swap a besoin de 2 boules voyons autour de 4 swaps.
Pourquoi est-ce?
Parce qu'il ne répond pas à toutes les règles:

• [5,1,4] [2,6] [11,13] [10,12] ne peut pas être à proximité les uns des autres (les sauts de 5)
• 8ball sur un côté et pas dans le triangle du milieu (sauts de 4)
• [5,4] [6,12] [13,9] ne sont pas tous du même type (les sauts de 3), en outre, dans le cas d' [1,5,4] le jeu n'est pas opposé à l'angle (pauses 3 fois)
• [2] et [11] ne sont pas du même type que les coins (les sauts de 2)

Algorithme

1ère étape: fixer le 8ball
Swap le 8ball dans sa position. Il aura besoin d'être là de toute façon.
Voici la seule chance de tourner (dans le cas où le 8ball commence à l'intérieur du triangle, mais la position incorrecte)

Count le plus de boules de même type dans le rouge les positions.
Plus grande quantité de boules de séjour, le reste de l'spots doivent être permutées.

IF count is 3 {
    #inside triangle will choose 
    IF inside triangle has 2 of a kind, that type stays (in the red spots)
    ELSE pick random
}

Commencer échange:

• ne les coins (ramasser un ballon qui doit changer et trouver un en face de l'un dans un coin)
• faire de milieux (ramasser un ballon qui doit changer et trouver un en face de l'un au milieu d'un côté)
• si les coins et les milieux sont faites, le dernier swap est à l'intérieur du triangle

Démo sur votre exemple:

swap 8 with 3  #move1
count[stripe]=3 [6,13,9]  
count[solid]=3 [5,4,12]
highest count=3, checking inside, inside is correct, random pick: stripes stay
Pick 5, corners() correct, swap with middles(2)  #move2
Pick 4, corners() correct, swap with middles(11)  #move3
Pick 12, corners() correct, swap with middles(3)  #move4
Done.

si random pick choisir solides pour rester:

Pick 6, swap with corners(10)  #move2
Pick 13, swap with corners(1)  #move3
Pick 9, swap with corners(14)  #move4
Done.

Demo2:

changé 3 à 7, remplacé " boule blanche pas.8' avec le ballon no.15

swap 8 with 3  #move1
count[stripe]=3 [6,13,9]  
count[solid]=3 [5,4,12]
highest count=3, checking inside, inside has 2 of a kind(stripes) => stripes stay
Pick 5, corners() correct, swap with middles(2)  #move2
Pick 4, corners() correct, swap with middles(11)  #move3
Pick 12, corners() correct, swap with middles(15)  #move4
Done.

Have fun!

PS: Vous pouvez également l'Algorithme de variation #2 qu' counts le gris des positions, mais je l'ai trouvé plus facile pour un scénario de la vie réelle à utiliser les points rouges.