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))
((< 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))

(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)

(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))
(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))))))```

62 Responses to “The Knight’s Tour”

1. wtf Says:

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

2. duh Says:

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

3. vilimini Says:

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

4. simson_yeoh Says:

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:

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:

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:

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:

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

LOL

9. asshole Says:

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:

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:

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:

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..