How to efficiently rack up billiards for an 8-ball game?

Since racking of billiard balls for the 8-ball game can be done under multiple rules, here's the racking I refer to:

i.e. the 8-ball must be in the center, and along the sides the stripes and the solids must alternate. The two remaining balls (a stripe and a solid) don't matter.

Assume you just finished a game, gather the balls, put them in the rack and proceed to arrange them to start a new one. They're now in a random order. How do you proceed?

Disclaimer: paint art follows

A simple approach would be to start in order, top -> bottom and left -> right.

So for example, we'd assume 1 is at the correct position. 5 is not, we swap it with 2, then we swap 4 with 3 (or with 8), but this would already be inefficient because we've either moved the 4 to the center or the 8 in 4's position - i.e. not where it has to be at the end.

There's also the decision of which types of balls we want in the corners to be made. How do you decide that upfront? Should you take into account how many balls are already in place? In my example, if you want the grey ones in the corners, you already have 3 in place (balls 1,10,14). If you want the white ones in the corners, you have just 2 of them in place (2,11). Should this matter?

To formalize this, we can assume there are two three operations we can do:

  • swap two adjacent balls
  • swap two non-adjacent balls
  • rotate rack

Since we can use both hands, let's assume we can parallelise the first operation (swap 2 couple of balls at the same time), whereas we can only swap two non-adjacent balls at a time.

What approach is best suited for this task that minimizes the time (in the time units described)? Would greedy be best for this? (it's how I do it when I rack them up, I guess)

EDIT: As per existing (or previous answers) - you might assume having more stripes than solids in the corners means that strides will prefer corners - not saying it isn't true, but if you make that assumption, please prove it.


NOTE! This answer was written before the rotation requirement. Proceed at your own caution :)

Here's my initial look at the problem.

The first thing to do is calculate the parity of the exterior - +1 if it would fit 'stripes in corners', -1 if it would fit 'solids in corners', +0 if it's the 8 ball. This gives us a range from +12 to -12, and we aim for the extreme we are closer to. (If +0, pick +12 or randomly)

For example, this is +1 +1 +1 -1 -1 +1 -1 -1 -1 +1 +0 -1 and thus it's -1 leaning solids in corners:

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

The next thing to do is move the 8 ball into the center. If you can do two adjacent swaps with it that moves two balls into position, rather than a single adjacent swap that moves just one ball into position (or a single non-adjacent if it's in a corner), do so.

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

After we move the 8 ball, all combinations of two adjacent swaps sharing a ball can be produced by a non adjacent swap identically, so we have to consider far less complexity at once.

Order all remaining moves by this priority:

-A swap between two adjacent balls on the outside is 'worth 4' (2 if it's our last)

-A swap between two adjacent balls, one on the outside, is 'worth 2' (1 if it's our last)

-A swap between two balls on the outside is 'worth 2'

-A swap between two balls, one on the outside, is 'worth 1'

And perform them from top to bottom.

So we move the o on the top, left (4), the o on the right side in (2), the o on the bottom left in (2) and then swap the x top with the o in the middle (2). We ended up doing five swaps in a 2-2-1 series, so three moves.

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

(Notably, this one would have been solved just as fast if we aimed for stripes in corners.)

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

I think it's impossible to require 4 turns, but I haven't proven it to myself yet.

Another worked example:

This has a parity of +1 so we aim for stripes in corners:

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

swap 8 ball with center x (1-)

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

swap two adjacent on outer, 4 points (1-1)

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

swap adjacent edge into center, 2 points (1-2-)

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

swap edge to edge, 2 points (1-2-1-)

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

3 moves.

EDIT: This works quite well for the example in the opening post, solving it in two moves:

This has a parity of +1 so we aim for stripes in corners:

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

Swap 8 with x on edge then with o in center (solving two edges) (2-)

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

swap adjacent o and x on top and bottom left (solving four edges) (2-2-)

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

2 moves.

You have 2 eight balls, cheater.

In the given example, the solution takes 2 moves:

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

An optimal solution is best found by configuring the problem for dynamic programming (DP). Since the problem is multi-stage with fixed costs and no uncertainties, a DP matrix will exist that optimally solves the problem.

To create the matrix: note that accounting for symmetries the 8-ball can be in one of 9 positions. The solids can be arranged in about (14 choose 7)/2=1716 different ways. That means the total number of rack configurations is about 1716 * 9 = 15,444. Thus, you have 15,444 different possible states. Calculate the cost to go from any one of these states to any other. This results in a matrix with 15,444 * 15,444 cells, or about a quarter of a billion cells. Identify all the end-state cells. To solve the matrix you breadth search forwards from the starting state until you reach an end state (or until you reach a cost total greater than your current minimum cost). By doing this you will have provably found all the least cost paths.

Note that the above solution is somewhat naive and can be optimized in various ways to yield a smaller matrix. For example, you can use rotational symmetry to reduce the number of cells and add a cost of 1 (for rotating the rack) to paths that are correct except for having the 8-ball in one of the low-center positions.


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.

There are 15!/(7!7!1!)=51480 possible positions. Of these, 4 are final: balls 8 and 9 can be exchanged, and stripes/solids can be reversed. We'll say these positions are at distance 0.

For each of these 4 positions, generate all possible moves (1 swap or 2 adjacent swaps). For each position generated by these moves that has not been seen before, remember which move was used to generate it, and give these positions distance 1. Then do the same thing for every position at distance 1 and give the new positions distance 2. Keep doing this until there are no more new positions.

This makes use of the fact that, as @DPenner pointed out, rotations can always be replaced with an adjacent move.

Since swaps are their own inverse, the move to go from position A to B is also the move that will take position B back to A.

So, you end up with a list of all positions, and for each position that is not a final position a move that will with certainty bring it closer to a final position.

You will find that there are 232 positions that take at least 4 moves. (EDIT: My adjacency table contained an error earlier.) For example:

      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

There are no initial positions that take more than 4 moves.

EDIT: The strategy of swapping in the 8-ball first is not optimal. For example:

         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

but we can do better:

         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

The problem is that x is the wrong kind for the corner, so we lose a move.

Rather, the strategy should be to look for a ball that is out of place, but that cannot be exchanged with an adjacent ball, either because they are the same kind or they are already in position. Corners should be preferred, because they have the fewest adjacent swap options. It should be swapped with a ball of the correct kind for the position. If the ball at the first ball's final position is of the wrong kind, an adjacent ball in the wrong place should be chosen. That way, a subsequent adjacent swap will put those balls in the correct final place.

In the above (counter)example, the 8 ball requires a long swap to get to its final position. However, the x in #5 is the wrong kind, so instead we swap with an adjacent o, the 2nd one in the 2nd row.

The earlier example with 4 moves is solved as follows:

        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

In the first step, we pick the o in the bottom left corner. The first x is at position two. Then we pick the 8 at #12, which we can bring home to #5. The o in the middle of the bottom row is next. We exchange it with the next wrongly placed x at #3. Finally, we swap #9 and #10 to get the final rack. The path is different from before, but we still made it in 4 moves.

EDIT: One more point: when performing adjacent swaps, preference should be given to those that do not end up with both balls in their final position. The reason is that this means that at least two moves are required in all, and so it's best to make the first move as soon as possible.

For example, the rack in the question can be solved in two moves: (2-4),(5,6) and (3-6),(12-13). The 8 ball was moved to its final position first, even though the white ball it was swapped with is not yet in its final position. If the two perimeter swaps (2-4),(12-13) were done first, you still need two moves to get to the final rack, taking a sub-optimal 3 moves total.

Salut, first I must say this was a very fun and interesting problem, and something that I haven't thought of when racking, although at 15 total balls some extra moves wouldn't be important.

From the racking description and image we get the following rules:

  1. corners are always the same type
  2. middle of each side is always same type as corner
  3. each set of 2 balls touching the corners are the always same type (and opposite type as corner)
  4. inside triangle has always the 8ball, a stripe and a solid (and 8ball is on top)
  5. on the sides, balls near each other will always alternate type

As @DPenner stated in Lemma 1, rotations aren't necessary because they can be substituted by a swap, provided the cost is the same. If you're a Rubick fan and choose to use them you would need only one.

Can't be solved in less than 4 swaps! ( always )

Your example image is best to prove this, either way you count it you'll need to dislodge 6 color balls from their positions and the 8ball => that's 3½ swaps and because a swap needs 2 balls let's round that to 4 swaps. Why is this? Because it doesn't meet all the rules:

  • [5,1,4] [2,6] [11,13] [10,12] cant be near each other (breaks 5)
  • 8ball is on a side and not in the middle triangle (breaks 4)
  • [5,4] [6,12] [13,9] are not all the same type (breaks 3), moreover in the case of [1,5,4] the set is not opposite to the corner (breaks 3 again)
  • [2] and [11] are not the same type as corners (breaks 2)

1st step: fix the 8ball Swap the 8ball into it's position. It will need to be there anyway. Here's the only chance to rotate (in case the 8ball starts in the inside triangle, but incorrect position)

Count the most balls of same type in the red positions. Highest count balls stay, rest of the spots have to be swapped out.

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

Start swapping:

  • do the corners (pick a ball that needs changing and find an opposite one in a corner)
  • do the middles (pick a ball that needs changing and find an opposite one in a middle of a side)
  • if corners and middles are done, the last swap is in the inside triangle
Demo on your example:
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

if random pick would choose solids to stay:

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

changed 3 with 7, replaced 'white ball no.8' with ball 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

Have fun!

PS: You might also like Algorithm variation #2 that counts the gray positions, but I found it easier for a real-life scenario to use the red spots.

This has been a challenging, deeply frustrating, and fun question all at once. My conjecture is that the following is an optimal solution:

  • Choose whether stripes or solids are in the corners based on Patashu's parity method
  • No rotations
  • Every time-measure, make the move which scores the highest except where a +3 move can put the 8-ball in the centre
  • In case of tie, choice does not matter? Edit: See note at bottom. Ties are difficult.

(I'm scoring moves according to the net difference in the amount of balls in correct positions.)

Here are two example 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

If we number the positions 1 to 15 going left to right, then top to bottom, the first rack solves as (2-4/3-5)(5-11)(10-13) and the second rack solves as (4-8/11-12)(5-10)(1-5).

My latest attempt at a proof had a portion of it fail on just 11 different racks up to symmetry (with the two shown above being a variation of ones that failed). Here are two lemmas I found in my attempts which will hopefully help others with proofs.

Lemma 1: Rotations aren't necessary

Note that if we need to do a rotation at some point in our solution, it doesn't matter when (rotating doesn't change any available swaps). Further more we only need at most one rotation since 2 clockwise rotations = 1 counter-clockwise rotation and vice-versa.

So lets choose to make the rotation on our last move if needed. At this point, due to rotational symmetry of the outside, the outside must be correct. So the 8-ball would be in one of the three central balls. If its in the right spot, we don't need rotation. Otherwise, we could use it but notice that a swap would also complete the rack. It is therefore unnecessary in an optimal solution.

Lemma 2: Greedy is optimal if it solves the rack in under 3 moves

Let strategy A be the greedy solution and strategy B be any non-greedy solution attempting to be faster. B must make at least one non-greedy move. By necessity this cannot be the last move. Therefore if A takes n turns to complete a rack, B must make its non-greedy move at turn n-2 or earlier. This means that if A solves the rack in 2 turns or less, it is optimal.

Edit: Well, I just ran my algorithm on a programmatic test, and found out its not even consistent. In fact it seems that ties are very hard to break. Consider the following rack:

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

My algorithm would do one of the following move sequences: (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), or (5-8/9-10)(7-15)(13-14). The first two solves it in the optimal 2 time-measures, but the others solve it in 3 time-measures. The problem is that the (14-15) and the (9-10) switch ruin a possible +4 move on the second turn. A modification to this algorithm would probably require a look-ahead, which then gets complicated quickly. I'm starting to think there is no "simple" solution, and the solution by @JeffreySax is the way to go. Also note that this rack also defeats the greedy solution. The greedy solution would do either (13-14/10-15)(5-8)(7-8) or (13-14/10-15)(7-8)(5-8).

Need Your Help

Poor Canvas2D performance with Firefox on Linux

performance html5 canvas

I just hit something particularly hard to debug when doing some pretty intensive rendering with Canvas2D. I use all kinds of things, from globalCompositeOperation to multiple off-screen canvases, w...

Error when populating DropDownList with database data razor html-select

In my view I have a DropDownList which I populate with database data. But when I run it I get an error I don't really understand:

About UNIX Resources Network

Original, collect and organize Developers related documents, information and materials, contains jQuery, Html, CSS, MySQL, .NET, ASP.NET, SQL, objective-c, iPhone, Ruby on Rails, C, SQL Server, Ruby, Arrays, Regex, ASP.NET MVC, WPF, XML, Ajax, DataBase, and so on.