This still isn't going to be a proof.

I'm not sure quite how I'd go about doing that. Finding some kind of upper
and lower bound might be helpful. If it can be proved that the optimal
solution never takes a non-optimal move under a given heuristic (which can
be complex, since it only needs to be evaluated 86 times), a brute force
search might be possible for the 4x4 (sloyd extreme).  I suspect this
problem is in general NP-hard, though.

-Chris

Post a reply to this message