July 2023 - Solution
July 2023 Solution:
We can use an undirected graph a to decribe the states of the board with edge between two states which differ by one piece move (the graph is undirected since every move is reversible). We add edge weights according to the size of the piece moved, and this transforms the problem into standard shortest-path finding in a graph. Since the the of possible nodes is relatively big, it is best to use a shortest-path finding algorithm which gradually adds new nodes based on their path-length from the source, such as Dijkstra's algorithm (some solvers reported using A* or simple BFS). Some solvers turned to the classic metod instead - solving by hand, which is indeed possible in this problem. One such solution, found by Bertram Felgenhauer, is:
Main problem: 8D9D5D6D7L7L4D3D3D2R2R1R1R7U7U5U6U6U3L3L1D1D1R3R3U9U9R5D5D5R6L6D6D Bonus problem: 8D9D7D6R5R1D1D2L3L7L4L4D4D3R3R2R2R1U1U5L6L7L4L3D2R4U4U4L2L3U8U9R9R9R7D7R6D5R1D1D1D4L4D2L3L8U6 R6R6R5D5R5RThe solver K S was kind enough to create animated GIFs of his solutions:
![](../images/July_solution.gif)
![](../images/July_star_solution.gif)