Sunday, August 9, 2015

Blacksmith Khecho's Ingenuity


Another puzzle from Dover's Moscow Puzzles. Building on similar structures and ideas to The Whims of Three Girls, it was much easier to conceive and develop a combinatorial solution for this one.

However... the solution does not terminate!

Presumably this is due to the combinatorial search space being much larger -- even with a small sub-problem with two people weighing 20 and 30 pounds and six of the 10-pound chains, the solver finds 226 solutions.
Solution # 1 of 226 

[20, 30, 10, 10, 10, 10, 10, 10] | * [] --- []  | []

[10, 10, 10, 10, 10, 20, 30] |  [10] --- [] * | []
[10, 10, 10, 10, 20, 30] |  [10] --- [10] * | []
[10, 10, 10, 20, 30] | * [10] --- [10, 10]  | []
[10, 10, 10, 30] |  [10, 20] --- [10, 10] * | []
[10, 10, 10, 30] | * [10] --- [10, 10]  | [20]
[10, 10, 10, 10, 30] | * [] --- [10, 10]  | [20]
[10, 10, 10, 10] |  [30] --- [10, 10] * | [20]
[10, 10, 10, 10] | * [] --- [10, 10]  | [20, 30]

When I use the problem inputs, the solution candidate stack hovers rises steadily to about 1000 candidates, falls to 700 or so over a minute or two, and begins to rise steadily thereafter.

The optimization is interesting to think about because it is not obvious how to evaluate the merits of different states. The only trivial optimization I've done is to permit people to jump off the balance and crash it, if the move results in a complete puzzle (not explicitly addressed in the problem statement, and a plausible interpretation).

I will come back to this later as I haven't made much progress in the past day.