ThirtySomething/Billiard

Solve a billiard puzzle, either with brute force or with a strategy.
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Type Name Latest commit message Commit time
Failed to load latest commit information.
_IDE
doxygen
src
.gitignore

Billiard

Billiard is distributed under the terms of the GNU LESSER GENERAL PUBLIC LICENSE, version 3.0. The text of the license is included in the file LICENSE.TXT in the project root.

What is `Billiard`

This is a mathematics puzzle based on billiard balls. Imagine the triangle of all billiard balls like this here

Level
4 11 12 13 14 15
3 7 8 9 10
2 4 5 6
1 2 3
0 1

On level 0, there is one ball with index 1 called `bottom ball`. On level 1, there are two balls above the `bottom ball`, one with index 2 (called `ball upper left`) and the second with index 3 (called `ball upper right`). The absolute difference (or the distance) between `ball upper left` and `ball upper right` must result in the `bottom ball`. See this example to understand:

Level
1 5 8
0 3
```bottom ball = abs(ball upper left - ball upper right)

3     =           |  5       -         8 |```

This `group` of `two balls above one` is available at least 10 times for 15 balls. For each group this rule must be valid. An extended example looks like this one

Level
2 4 12 7
1 8 5
0 3

Source

The C++ program in the folder `src` will solve this puzzle. There are currently two solvers present.

The first one, `BilliardBruteForce` will perform a brute force method to solve this puzzle. There is a huge amount of permutations for all 15 balls - you need patience and a fast computer. To see the program is working, a dot for 200000 permutations is printed. 50 dots in a row show 10 million permutations.

The second one, `BilliardStrategy` will follow a strategy to solve this puzzle. There are much less permutations required.

Additional solvers are planned for the various frameworks as mentioned in the `ToDo`-section on this page.

Complete ruleset

Assume a function `CheckGroup` where you have as parameter the index of the lower ball, the upper left and the upper right. If the rule is applicable, the function returns true, otherwise false. Based on this the complete ruleset looks like this one:

```Level1 = CheckGroup(0, 1, 2)
Level2 = Level1 & CheckGroup(1, 3, 4) &
CheckGroup(2, 4, 5)
Level3 = Level2 & CheckGroup(4, 6, 7) &
CheckGroup(4, 7, 8) &
CheckGroup(5, 8, 9)
Level4 = Level3 & CheckGroup(6, 10, 11) &
CheckGroup(7, 11, 12) &
CheckGroup(8, 12, 13) &
CheckGroup(9, 13, 14)```

Solution

There are two solutions:

Level
4 6 14 15 3 13
3 8 1 12 10
2 7 11 2
1 4 9
0 5
Level
4 13 3 15 14 6
3 10 12 1 8
2 2 11 7
1 9 4
0 5

ToDo

Speed up the brute force. Evaluate these frameworks and apply a solution to the puzzle solver source.

You can’t perform that action at this time.