Knight

[Adrian Hey]

On Fri 02 Feb, Christoph M. wrote:
> Yes, I meant the Knight's Tour problem. Could anybody post me a solve of
> this problem in haskell ?
> Thanks a lot,

Sorry I've never done this in Haskell. The second computer program I ever
wrote was to solve this (in BASIC). That was many years ago:-)

IIRC, it can be solved following a very simple rule. For each square of the
chess board keep track of the No. of squares which can be reached in a single
move from that square. The next Knight move is to which ever square has the
lowest No. (Unused squares and legal legal moves only of course). If you have
2 or more equally good moves just make a random choice.

After the move you decrement the counts for each square which can be reached
in a single move from the new square. 

This is more of a heuristic than an algorithm, in that I couldn't prove that
it will always work, nor could I prove that not obeying this rule will result
in failure. (That's why I wrote the program). It does seem to work. But it's
not hard to see why this is reasonable strategy. (The best next move is the
one which minimises the No. of possible future moves which get blocked as a
result). 

As far as  Haskell solution is concerned, the only difficult decision you
have to make is what data structure to use to represent the chess board
squares and counts. An array seems the obvious choice, but maybe somebody
can suggest something else better suited to a functional solution.

Regards
-- 
Adrian Hey