Graph theory, Search
Best explained in problem statement.
This was a challenge problem and so one din’t need to find the optimal move
sequence. Though it is not proved to be an NP complete problem, as stated here,
this problem is an open problem and so if you
do have an algorithm which finds the optimal sequence, you should try to publish
a paper quickly
One of the easiest methods to get accepted was using randomization. Randomly
choose a checker and try to move it along a random direction (except for two
directions). After sufficient number of such random moves, grid
would be solved. The reason is in every turn we’re decreasing the “distance” of
current configuration from the goal configuration.
Setter’s solution involves filling in the goal squares one at a time, using
a bfs to find a piece that can be efficiently moved there. Maybe one could also
try some sort of local search with solution of one of these methods as the base
solution and an appropriate neighborhood function.
solutions will take advantage of the jump rule and set up long series
of jumps (especially for dense grids). Setter’s expectations were that top
solutions would reach a score of 5, though it was only in last hours, ACRush
reached aronud 4. All others are way behind at 2.5. I’ve not understood ACRush’s
over 1000 line solution but I saw a function with the name MST in it One
combinatorial idea is as follows : consider a graph on all cells with upto three
edges per piece, corresponding to available jumps over that piece. It is highly
benificial to have large connected components in this graph as single piece
would be able to make several jumps.
One thing that really bothered us was there were a low number of submissions.
Even more interesting was the fact that there wasn’t a single comment on the
problem page uptil around 1 hour before the contest concluded.
I request contestants to share the high level idea of their solutions here.
In the end, here is a trivia from setter: The title for this problem comes from the fact that it’s a
one-player version of Chinese Checkers, but Chinese Checkers is neither Chinese nor a variant of Checkers!
Can be found here.
Can be found here.