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