### PROBLEM LINK:

### DIFFICULTY:

Challenge

### PREREQUISITES:

Graph theory, Search

### PROBLEM:

Best explained in problem statement.

### DETAILED EXPLANATION:

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

“bad”

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.

Better

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!

### SETTER’S SOLUTION:

Can be found here.

### TESTER’S SOLUTION:

Can be found here.