[Haskell-cafe] The Knight's Tour: solutions please

[ajb at spamcop.net]

G'day all.

Quoting Bertram Felgenhauer <bertram.felgenhauer at googlemail.com>:

>   successors n b = sortWith (length . succs) . succs
[...]
>   successors n b = sortWith (length . (succs =<<) . succs) . succs
[...]
>   successors n b = sortWith (length . (succs =<<) . (succs =<<) .   
> succs) . succs
[...]
> These improved heuristics don't come cheap though.

The heuristic is cheaper and more useful when the ply of the tree
is low.  It's more expensive and less useful when the ply is high.
Moreover, deeper neighbour searches may only be useful in cases where
the shallower searchers fail to settle on the best course of action.

So something like the following might be better.  Note that "d" here
is an example only; I don't promise it's good.

successors n b = sortWith heuristic . succs
     where
         heuristic p = let ps = succs p
                           d = 5 - length ps `div` 2
                       in map length . take d . iterate (succs =<<) $ ps

One more thing: Deeper neighbour searches are also unnecessarily expensive
because they recompute "succs" a lot.  It seems to me that if you memoed
this, what you'd actually have is an explicit lazy search tree data
structure.  Hint hint.

Cheers,
Andrew Bromage