August 2017

[uau]

Finding an optimal 9-ball solution to the original intended problem was relatively straightforward, but most solvers didn't have a single star, so I assume they must have used an inefficient approach if they only found a solution with 8 balls. Below is the approach I used for that (finding a 26-ball solution to the alternative version required a bit more complications).

First, consider exactly what kind of moves to pocket a ball are possible. We can model the bounces by tiling the plane with copies of the board such that every other column is horizontally mirrored and every other row is vertically mirrored. In this model, any bouncing shot can be drawn as just a straight line. The board repeats horizontally at distance 12 (6 normal + 6 mirrored, then repeats) and vertically at distance 8.

Thus possible moves are lines from the current white ball position which intersect a black ball and then a corner pocket. In general, there may be an infinite number of such lines in the plane. However, we only care which integer points a line intersects before hitting a pocket. If (dx, dy) is the direction of the ball/line, expressed as integers with no common factor, then the only integer positions the line intersects are the starting position plus integer multiples of (dx, dy). Thus we can consider dx mod 12 and dy mod 8, and get a finite number of possible directions for the next shot. Note that "no common factor" is considered before reducing mod (12, 8); it's not possible to have a direction where both coordinates are even as that's the (only) shared factor of 12 and 8 too, but it is possible to have a direction (3,3) for example. This could correspond to an unreduced direction like (3, 11) or (3, 19).

The approach I used to find the solution is a straightforward exhaustive search. Given the starting position of the white ball and all moves so far (which direction the white ball went and where it hit a black ball), try all possible next moves (which direction next, and where that direction could hit a black ball - it must be a position which no ball has moved over during an earlier move, as having a black ball there would have caused an invalid collision then). To calculate the possible next moves, only two pieces of information about prior moves are directly required: current position of white ball, and set of positions no ball has moved over (the valid positions for adding the next black ball).

The possible directions for a shot from each white ball starting position can be precalculated. It doesn't actually matter in exactly which order the line goes through integer positions; just the set of positions hit before hitting a pocket. Additionally we need to know if the bouncing path intersected itself, as those positions are not valid for placing a black ball (the white ball would first the the black ball there, then it would hit the white ball again when the path returns to the same position). Thus we have two variables for each possible shot from a position: set of integer coordinates the line travels through, and the subset that is crossed more than once. These sets can be efficiently stored as bitmasks.

So what we do at each step of the exhaustive search is: go through all possible (precalculated) moves from the current white ball position. For each, go through all possible black ball positions along that move (positions non-doubly crossed by that move, but not in the set of all positions covered in earlier moves). For each such position, set current white ball position to that and add positions covered by the move to set of all covered positions. Repeat for next move.

The attached program implements this strategy. Even written in Python, it's fast enough to find all optimal solutions within a couple of seconds.

[R. Gerbicz]

Originally Posted by uau

Finding an optimal 9-ball solution to the original intended problem was relatively straightforward, but most solvers didn't have a single star, so I assume they must have used an inefficient approach if they only found a solution with 8 balls. Below is the approach I used for that (finding a 26-ball solution to the alternative version required a bit more complications).

Thanks for the description, I've found all of your tricks.
Known technique, see for example a triangle PE problem in this context: https://projecteuler.net/problem=202.
I'd easily get the 9 ball solution, I have just not went for it. I held the record for 24 balls for long days. My sent solutions (without code), notice the same example, and used variables. (we have a quite good brain) Considered only the case where we can place balls on the rails.

1st email:

One (possible) solution for 11 black balls:

O.BWB.O
B.BB..B
BBB...B
.......
O.B...O
(-5,4),(-1,-2),(-5,2),(-5,4),(-4,1),(6,1),(-3,-1),(-3,1),(6,-1),(-4,-3),(-4,-3)

Used a backtracking search: first fix the white ball, and then in each layer (depth) try all directions for the latest ball, see the route of the ball: we shouldn't visit the already visited positions. And for each such position see if there would be a black ball in that position would it fall in the pocket at the corner and doesn't visit a forbidden position. If yes, then save this balck ball's position, and the direction of the hit.

To make easier the following of the ball's route we make a partition of the plane with isomorph [2*W]X[2*L] rectangles, using this the ball's route is a half line and to get the original position from (x,y) to (V(x),V(y)) we simply do:
if x>W then V(x)=2*W-x otherwise V(x)=x, similarly:
if y>L then V(y)=2*L-y otherwise V(y)=y.

If (dx,dy) is the direction of the hit, then we can assume that (dx!=0 or dy!=0) and gcd(dx,dy)=1 [otherwise we can use the same (dx/g,dy/g) direction with g=gcd(dy,dy)].

We can assume that abs(dx)<=W and abs(dy)<=L.
The computer search took less than a minute, and running it with NB=12 show that there is no solution for 12 black balls.

and 2nd email:

Improved solution for 24 black balls:

O.BBBBO
WBBB..B
B.BBBBB
.BBBBBB
OBBBB.O
(0,1) (3,1) (1,3) (4,1) (4,1) (5,-7) (5,1) (11,1) (7,3) (5,1) (5,3) (0,1) (-6,7)
(-10,1) (2,1) (8,3) (5,-4) (5,4) (1,0) (1,2) (5,2) (7,6) (1,4) (5,-4)

My previous search was very restricted: we should assure only that:
1. the white ball doesn't fall in one of the corner's pocket
2. the black ball's initial position isn't the same of an already visited position (by white and black balls)
3. the allowed (dx,dy) directions are such that gcd(dx,dy,2*W,2*L)=1, so the greatest common divisor of these 4 numbers is 1, this is because for (dx2,dy2) direction, where dx2=dx+c1*(2*W) and dy2=dy+c2*(2*L) the final positions will be the same and if gcd(dx,dy,2*W,2*L)=1 then we can find c1,c2 for that gcd(dx2,dy2)=1. And in that case there will be no middle grid position on the route, when we make the move with the (dx2,dy2) direction. Example: even (dx,dy)=(3,3) isn't usable, but dx2=dx=3; dy2=dy+2*L=3+2*4=11 is usable, because gcd(3,11)=1. [in my code W=6;L=4 the lengths of the billiard table].

The attached code solves the easier NB=23 black balls problem quite easily in 1 second, but struggles with NB=24, that has been found with another code in roughly 20 minutes. But shows how important is the order of the white ball's position in the search and the order of the directions.

[uau]

For the variant problem, the above basic search plus the adding a check described below is enough to get a C implementation that can find a 26-ball solution in a dozen or so seconds (depending on exactly which order you search in) and almost instantly (less than 0.01 seconds) prove that no 27-ball solution exists.

First, you can get an obvious upper bound for the achievable number of balls by taking the number currently placed on board, and adding all points on board that haven't been crossed. This allows rejecting bad search paths early if you have a minimum result to search for. However, there's a not-immediately-obvious possible improvement to this bound: for the top, middle and bottom rows, it's impossible to get all three odd positions in the row (the ones marked below):

OX.X.XO
.......
.X.X.X.
.......
OX.X.XO

(You can verify this by considering how it'd be possible to get the first ball out of the row while the two others still remain. If it's a center ball, consider the shot that brings the white ball there. Any possible direction (one which has a possible starting position instead of coming straight out of a pocket) would continue through one of the side balls before the black ball would go into a pocket. If it's a side ball, consider the next shot. Any direction that doesn't immediately sink the white ball into a pocket will go through first through the center position in the row and then the other side position, causing a collision between black balls.)

After improving the upper bound to take this into account, the bound is tight enough that when searching for 26+ balls most less than perfect moves can be rejected quickly.

[Xyzzy]

https://www.research.ibm.com/haifa/p...ugust2017.html

[LaurV]

Very nice! (all of you). Thank you for sharing it. I have read all of it.
Oleg's video shared on the answers' page is also nice to see, I watched it to the end. It worth the time.

I also clicked the wiki link... not sure it was a good move... it somehow ruined my morning...
Mother life is a bitch. In times like this, I am angry with the gods...
What the hack they had with her? So young, so beautiful, so intelligent...

Rest in peace Prof. Mirzakhani.