The Quickest Way to Rack Pool Balls

Whilst playing pool in the college bar years ago my friend Chris posed an interesting question: after removing the balls from the end of the table and randomly dropping them into the triangle, what is the minimum number of 'moves' necessary to rearrange the balls into the correct pattern? Where a 'move' is swapping the positions of two balls.

It turns out that if the black ball starts off in one of the centre positions (marked with an 'X' in Fig 1) then you canĀ always get to the correct pattern in 3 swaps or fewer. If the black starts off in one of the outside positions then you can still get to the correct pattern in 3 swaps 75% of the time, the remaining 25% require one additional swap. An explanation of this result is given below...

The correct pattern, as defined by the World Eightball Pool Federation, is shown on the left in Fig 1:

The official pattern (left) and symmetrical variations of it (right).

Fig 1: The official pattern (left) and symmetrical variations of it (right).

To make our lives easier, we will also allow the three patterns on the right of the figure, as these are all symmetrical, in colour or side, versions of the official pattern. The table is symmetrical, so these 4 are all equivalent. We also note that turning the triangle 1/3 of a turn either way is very easy, so we will not count this as a 'move'. This means that all 3 rotated versions of each of the above 4 patterns are counted as correct. In total then we have 12 patterns which we consider to be 'solved'.

Let's number the positions, starting from 1 at the bottom left corner, and counting to the right along the bottom row, up to 5, then left to right along the second row, from 6 to 9 etc... If we represent each red ball as a '1', each yellow ball as a '0', and the black as a '2', then we can write down the pattern of balls in the official arrangement (left of Fig 1) as a list of numbers, or vector, namely:

[1 0 0 1 0 0 1 0 1 1 2 0 0 1 1]

If we swap the bottom left red with the yellow on its right (positions 1 and 2), we get a slightly different pattern:

[0 1 0 1 0 0 1 0 1 1 2 0 0 1 1]

If we have these two vectors on a computer we can easily find which elements don't match by using the 'not equal to' operation, in Matlab this is denoted by '~=', so for example:

[1 0 0 1 0 0 1 0 1 1 2 0 0 1 1]

~=

[0 1 0 1 0 0 1 0 1 1 2 0 0 1 1]

=

[1 1 0 0 0 0 0 0 0 0 0 0 0 0 0]

In this way we can identify which, and how many, balls differ in position from one pattern to the other. One swap changes the positions of two balls, so if we divide the number of differences between any two patterns by two we get the number of swaps necessary to get from one pattern to the other. We have to round this number up, if it's not an integer, because if two patterns differ by the positions of three balls (one of which must be black) then two swaps will be required to change one into the other. We can't do one and a half swaps!

It is a fairly simple operation to compute all patterns that are possible with seven '1's, seven '0's and one '2'; there are 51,480 of them. Using the above method we can find the number of swaps necessary to change each of the 51,480 possible patterns into each of the 12 solutions. Taking the smallest of these 12 numbers for each pattern we find the answer to our question:

If the black is in one of the central positions (which happens in 3 of every 15 patterns) then the pattern can always be solved in 3 swaps; if the black is not in the centre then the pattern can be solved in three swaps 75% of the time, and always in 4 swaps!