Subject: Re: "Knight's Tour"
From: rpw3@rigden.engr.sgi.com (Rob Warnock)
Date: 1999/11/14
Newsgroups: comp.lang.scheme
Message-ID: <80lf4u$1v9f@fido.engr.sgi.com>
LacieG <lacieg@aol.com> asks what sounds like a homework question:
+---------------
| I am trying to write a scheme function that determines the minimum number
| of moves for a knight to get from one square to another. For example
| (on an 8x8 chessboard, with rows and columns numbered 1-8):
|     (Knight (1 1) (1 3)) yields 2
| Any ideas on how to approach this?
+---------------

Look in Paul Graham's "ANSI Common Lisp" (Prentice Hall, 1996) for a simple
"breath-first" search. It's fairly early in the book, IIRC, so he wouldn't
have been using any fancy Common Lisp stuff that would be hard for a Schemer
to read. And IIRC, it's just a couple dozen lines of code.

Graham's example finds the shortest path through a network (that is, a set
of "nodes", some of which are connected by "edges" to other nodes), but you
should be able to map that onto your problem easily enough. Hmmm... In fact,
it should be pretty straightforward: Simply define the network's "nodes" to
be the spaces on the board, and declare that an "edge" exists between each
space and all the other spaces that a knight could move from the first one.

Of course, since he used a simple list representation for the network,
it might run fairly slowly if the starting and ending squares are very
far apart, but I suspect one could improve the representation (and thus
drastically improve the performance) without seriously affecting the
underlying algorithm.

And in any case, it should give you some helpful ideas...


-Rob

p.s. (*rustle* *rustle* *grep* *grep*)  Aha!  I *thought* so...
The code for those books (A.C.L. and his other one, "On Lisp")
is available on-line (though I assure you reading the text itself
will make it a *lot* easier to understand what the code does). See:

	<URL:http://www.eecs.harvard.edu/onlisp/acl/>
	<URL:ftp://ftp.eecs.harvard.edu/pub/onlisp/acl-examples.lisp>

The routines you want are "shortest-path", "bfs" (breath-first search),
and "new-paths" [even shorter than I thought, less than 20 lines of code].

-----
Rob Warnock, 8L-846		rpw3@sgi.com
Applied Networking		http://reality.sgi.com/rpw3/
Silicon Graphics, Inc.		Phone: 650-933-1673
1600 Amphitheatre Pkwy.		FAX: 650-933-0511
Mountain View, CA  94043	PP-ASEL-IA