«
»

The Knight’s Tour

One of my favorite problems when I try new programming languages is the Knight’s Tour. The goal is to move a knight on a chess board in a way that each square of the chess board is visited exactly once. The naive approach is to use simple backtracing, but a better way was found in the 19th century by H. C. Warnsdorff. This is an implementation of his algorithm. I hope the Lisp code is not too embarassing.

(defun start-tour (position)
(let ((board (make-array '(8 8))))
(move position board 1)))

(defun move (position board n)
(setf (aref board (car position) (cadr position)) n)
;;  (print-board board)
;;  (print (evaluate-possible-moves position board))
;;  (format t "~%")
(cond ((= n 64) (print-board board))
((null (possible-moves position board)) 'failed-dead-end)
((< n 64) (move (best-move position board) board (+ n 1)))))

(defun best-move (position board)
(car (evaluate-possible-moves position board)))

(defun evaluate-possible-moves (position board)
;;  (print position)
;;  (format t "~%")
(sort (mapcar #'(lambda (x) (append x (list (length (possible-moves x board)))))
(possible-moves position board))
#'(lambda (triple-a triple-b) (< (caddr triple-a) (caddr triple-b)))))

(defun print-board (board)
(do ((x 0 (+ x 1)))
((= x 8))
(do ((y 0 (+ y 1)))
((= y 8))
(format t "~2D " (aref board x y)))
(format t "~%"))
(format t "~%"))

(defun on-board-p (position)
(and (>= (car position) 0)
(<= (car position) 7)
(>= (cadr position) 0)
(<= (cadr position) 7)))

(defun visited-p (position board)
(> (aref board (car position) (cadr position)) 0))

(defun possible-moves (position board)
(remove-if #'(lambda (x) (visited-p x board)) (moves position)))

(defun moves (position)
(let ((x (car position))
(y (cadr position)))
(remove-if-not #'on-board-p
`((,(+ x 1) ,(+ y 2))
(,(+ x 1) ,(- y 2))
(,(- x 1) ,(+ y 2))
(,(- x 1) ,(- y 2))
(,(+ x 2) ,(+ y 1))
(,(+ x 2) ,(- y 1))
(,(- x 2) ,(+ y 1))
(,(- x 2) ,(- y 1))))))

This entry was posted on Friday, May 28th, 2004 at 3:38 and is filed under lisp. You can follow any responses to this entry through the RSS 2.0 feed. You can skip to the end and leave a response. Pinging is currently not allowed.

62 Responses to “The Knight’s Tour”

  1. wtf Says:
    January 4th, 2006 at 20:59

    mmu student really no brain or wat? find other code then want to post here to show f**k?

  2. duh Says:
    January 4th, 2006 at 22:39

    want to copy or refer also don’t let people know where (what uni) you’re from la. beh paiseh!

  3. vilimini Says:
    January 5th, 2006 at 15:01

    wtf : hei i am from UTAR one la , don simply accuse people , stupid .

  4. simson_yeoh Says:
    January 5th, 2006 at 15:03

    duh , u really duh la , people say they from MMU then u believe ah .. hahaha really duh .. by i am a proud student of UTM

  5. simson_yeoh Says:
    January 5th, 2006 at 15:06

    duh , u really duh , poeple say they from MMU u believe ah … hahaha really duh la u , btw i am proud student of UTM

  6. somnuk the great Says:
    January 5th, 2006 at 16:36

    wtf u all.. why be bad people.. be good people.. copy and understand… share coding… explain too.. PEACE! NO WAR! AMERICA SUCKS! FREE IRAQ!!!

  7. andy Says:
    January 6th, 2006 at 6:49

    we all are undergraduate..so pls behave among ourselves..sharing is caring…we should exchange our opinion and learn from each other…cheers..:)
    Btw,i am from MMU also…

  8. andy Says:
    January 6th, 2006 at 10:16

    Old practice: copy and paste
    New practice: copy and paste and understand and modify only the variables

    LOL

  9. asshole Says:
    January 6th, 2006 at 10:36

    yet another a** claiming tat he’s from MMU and telling everyone to behave themselves. ever heard of the word “anonymousity” ? wanna use a loud speaker to announce tat u r from MMU ? dun dent the image of MMU la.

    AMERICA SUCKS. IRAQ SUCKS TOO.

    Malaysia the Bolehland

  10. nimikuki Says:
    January 8th, 2006 at 22:40

    Hm im too having problems with your code mr neingeist.
    first i copy&pasted it into knight.c and then ran ./configure && make but nothing happened .. then i read something about a thing named gcc so i ran gcc knight.c against it and got the following message:
    stupid.c:1: error: syntax error before “start”
    stupid.c:2:29: missing terminating ‘ character
    stupid.c:2:29: warning: character constant too long for its type
    stupid.c:7: error: syntax error before ‘-‘ token
    stupid.c:8: error: syntax error before ‘-‘ token
    stupid.c:9: warning: data definition has no type or storage class
    stupid.c:9: error: syntax error before “t”
    stupid.c:11:105: missing terminating ‘ character
    stupid.c:11:105: warning: character constant too long for its type
    stupid.c:18: error: syntax error before “position”
    stupid.c:19: error: syntax error before “t”
    stupid.c:20: error: syntax error at ‘#’ token
    stupid.c:20:51: missing terminating ‘ character
    stupid.c:20:51: warning: character constant too long for its type
    stupid.c:22:58: missing terminating ‘ character
    stupid.c:22:58: invalid preprocessing directive #'(lambda (triple-a triple-b) (

  11. nimikuki Says:
    January 8th, 2006 at 22:42

    stupid.c:43: error: syntax error at ‘#’ token
    stupid.c:43:48: missing terminating ‘ character
    stupid.c:43:48: warning: character constant too long for its type
    stupid.c:49: error: syntax error at ‘#’ token
    stupid.c:49:69: missing terminating ‘ character
    stupid.c:49:69: warning: character constant too long for its type
    stupid.c:50: error: stray ‘`’ in program
    WTF ?? is this about the allegro thingy ?
    i also tried your make-array fix. but i still get the same ugly messages. i also tried gcc4.0 with the same results…
    maybe i have to load the file first ?
    is there a possibility to load a file like with allegro into gcc ?
    greetings from nimikuki and thx for your great work !

  12. sham Says:
    September 26th, 2007 at 8:42

    Error: Attempt to take the value of the unbound variable `BOARD’.
    [condition type: UNBOUND-VARIABLE]

    that was my error and i dont know how to solve this so can u please help me on this.. thanks..

Leave a Reply