change solver from depth-first to breadth-first

[runar-rkmedia]

This solver is depth-first, which is very bad since it is very likely that the a game can create very deep branches with just some simple variations of swiping. We should create a breadth-first implementation. This could possible be done by have one function that evaluates once for all hints for the game, but does not actually do any work into these branches, but adds these into a queue, which is then performed.

For instance the generated game below goes to a depth of 5564. which is just ridiculous considering the board can be solved in 3 moves.

Name = '0130-current-paul-robin'
Preview = """

       0:    1:    2: 
 00: [  4 ][ 10 ][ 12 ]
 03: [  2 ][ 10 ][  8 ]
 06: [  1 ][  7 ][    ]"""
Hash = 'AwMECgwCCggBBwA='
Cells = [4, 10, 12, 2, 10, 8, 1, 7, 0]

[GeneratorOptions]
Rows = 3
Columns = 3
TargetCellValue = 64
MaxBricks = 9
MinBricks = 4
MinMoves = 0
MaxMoves = 7
MaxIterations = 100000000000
Concurrency = 1000
Seed = 0
MinGames = 100

[[Solutions]]
History = [[7, 6, 3, 4], [2, 5, 4], [0, 1, 4]]
HighestCellValue = 80
Score = 140
Moves = 3

[[Solutions]]
History = [[7, 6, 3, 4], [2, 5, 4], 'Right', [1, 2, 5]]
HighestCellValue = 80
Score = 140
Moves = 4

[[Solutions]]
History = [[7, 6, 3, 4], [2, 5, 4], 'Right', 'Down', 'Left', [3, 6, 7]]
HighestCellValue = 80
Score = 140
Moves = 6

[[Solutions]]
History = [[7, 6, 3, 4], [2, 5, 4], 'Right', 'Down', 'Left', 'Up', [3, 0, 1]]
HighestCellValue = 80
Score = 140
Moves = 7

[runar-rkmedia]

Update: I was wrong in arguing for that this is not a real requirement, see the comment below.

---

Not a real requirement at this point. Might revisit in the future.

This is only slow on rare edge-cases. There are some statistics gathered on branch feat/solve-statistics that should showcase this exact example. On my machine on this example, it seems that about 50% of the runs, it takes only ~70µs, while other times it is as slow as ~400ms. Even this is not too slow, as getting a Hint is non-critical, and users can wait a bit here. Of course, it needs to be fixed one day, but simply not a priority right now.

Measurements from running on fly.io, seems to indicate that this operation is sometimes as slow as 1100ms. That is a bit slow, but still reasonable.

There are other more important prioritities, like:

• Getting a better looking interface
• Challenge-selection
• Some kind of onboarding, probably simply improving the tutorial.

[runar-rkmedia]

There is actually a pretty solid improvement to using a breath-first generator, in addition to the performance-improvements. Notably for generating games, where we use the Solver to ensure we create solvable games, and also to show the lowest amount of moves a game can be solved in. A depth-first-solver is terrible at this, while a breath-first would would find that solution first, every time.

[runar-rkmedia]

A third algorithm was added in 3a7ee7d2. All three are good at some board.

Depth-first: Fastest if there are not too many levels of depth that give almost valid-solutions. Does not guarantee finding the shortest solution. Results are not sorted. Breadth-first: Fastest if many of the starting-branches can be eliminated. It is guaranteed to find the shortest solutions. Results are not sorted. CombineHint: Very fast at giving a very good hint at the current board, or getting a very good start. It does not do any swipes or such, but it very quickly finds a hint that is best suited for the starting board. If a deeper solution is required, it can be chained, or be the starting-hint for one of the other algorithms, deeply reducing the calculations reqiured. Always returns the same hints for the same input, in the same order.