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

Question

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.

Answer 1

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     o 

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     o 

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     o 

(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     x 

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     x 

swap 8 ball with center x (1-)

x o o o x  o o o x   o 8 x    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     x 

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

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

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

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

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     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     x 

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     x 

2 moves.