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))))))
December 14th, 2005 at 5:11
Hi Neingeist!
I’m really hope you can explain to me this code…this is my first time seeing knight tour in lisp…
December 14th, 2005 at 5:18
what would you like to know about it?
+++ neingeist
December 15th, 2005 at 6:47
Did u use Warndorff’s heuristic when u built up this code? Sorry i’m really new in lisp
December 24th, 2005 at 4:40
how do i run the lisp?
December 24th, 2005 at 15:14
Your code is good Neingeist. I’ve complied n load it but then i got some problem when i run it. i typed (start-tour ‘(1 5)). can you please explain how to run it.
December 24th, 2005 at 17:29
hey friend, nice job there. btw, i am having the same problem when i typed (start-tour ‘(1 5)). Can you help me out on this?
December 26th, 2005 at 6:14
hi there, i have a prob of to run d program, i already compile and load the file but when i typed (start-tour ‘(3 4)) i can’t executed it. Please guide me anyone
December 26th, 2005 at 6:39
my code seems to have problems with clisp. which lisp compiler are you using?
+++ neingeist
December 26th, 2005 at 14:40
i’m using allegro cl ver 7.0
December 26th, 2005 at 15:26
try replacing (make-array ‘(8 8)) with (make-array ‘(8
:initial-element 0)!
at least that fixes problems with clisp due to the uninitialised board.
+++ neingeist
December 27th, 2005 at 9:09
its work !! Thanks a lot for the changes. I have another doubts for the code, u declare 2 move function , can u plz explain bit specifiy coz i need to know all about the code flow btw
December 27th, 2005 at 11:22
2 move functions? there are somewhat different functions here:
move: moves to the best-possible position (using best-move)
best-move: gives the best-possible position (using evaluate-possible-moves)
evaluate-possible-moves: evaluates the possible moves using Warndorff’s heuristic (using possible-moves)
and finally:
moves: gives all moves for a knight from the position
possible-moves: gives all moves that lead to a position not visited before (using visited-p)
December 27th, 2005 at 19:47
hi there, i have a prob of to run d program, i already compile and load the file but when i try to run it by gvn a value for start-tour ‘ x y then it didn’t execute instead promted me an error mesage saying that move undefine .Please guide me anyone
December 27th, 2005 at 20:18
@dave:
what error _exactly_ in which compiler?
+++ neingeist
December 28th, 2005 at 5:59
Thanks neingeist!!
Your work is really awsome & marvellous. Way to go ^^
December 28th, 2005 at 11:09
I m using using allegro cl ver 7.0 oso but when i run with typing (start-tour ‘(3 4)) it oso can’t work. can you plz tell me why? thanks
December 28th, 2005 at 11:24
hi,neingeist.
i using allegro cl ver 6.2.
when i compiler, i got a error said that >. Actually the error is under “defun move” function.
thanks for help.
December 28th, 2005 at 11:39
hi,neingeist.
i using allegro cl ver 6.2.
when i compiler, i got a error said that (comma not inside a backquote. [file position = 1436]). Actually the error is under “defun move” function.
thanks for help.
December 28th, 2005 at 15:35
Tom Pyros is a student from MMU.
December 28th, 2005 at 18:02
@kelvin:
did you copy the code exactly? there is a backquote in the “moves”-function:
`((,(+ x 1) ,(+ y 2))
+++ neingeist
December 28th, 2005 at 18:15
Dave , kelvin , Sau Pei la…so easy oso wan to aask…MMu got this kind of student , really embarassing oh!!!~~ walao…nya sing…
December 29th, 2005 at 10:37
Hi Neingeist!
What do triple-a and triple-b represent in the lambda function ?
Thanks
December 29th, 2005 at 12:03
what about is the different btw on-board-p and visited-p ?
December 29th, 2005 at 12:12
The difference between on-board-p and visited-p:
[1] on-board-p checks for the range of the rows and columns of the board. Note the 0 - 7 for both rows and columns.
[2] visited-p is a straigtforward function to checks if a particular cell has been visited once and only once.
December 29th, 2005 at 12:22
Thx for explaining Fred. i also wondering about the triple-a and triple-b variables
December 29th, 2005 at 15:30
@fred+jasper:
the mapcar in evaluate-possible-moves appends the number of possible moves to a position (that’s basically warndorff’s heuristic).
(mapcar #’(lambda (x) (append x (list (length (possible-moves x board)))))
(possible-moves position board))
so if we had a position on the board, let’s say ‘(4 5) and we could move to 3 other positions from that position, this triple gets ‘(4 5 3).
the sort sorts by this third number (= caddr). that’s how we find out where to move next: we just move the knight to the position where we have the smallest possibility to getting back to again (best-move).
+++ neingeist
December 29th, 2005 at 15:47
Where to download the code?
December 29th, 2005 at 16:23
@baby:
You do not have the option to download the code since there is no link to it.All you need to do is, if your are desperate enough to submit your assignment in few days time, just copy the whole code listing and submit it as your own work for your AI assignment.(only if you do not observe the academic integrity) LOL
cheers
December 30th, 2005 at 10:12
i have problem on excuting this code. The code seemed fine but i cant excute it. Can u help me on this since i am desperate to learn this code. Thank u
December 30th, 2005 at 10:19
@fms:
what exactly is your problem? did it load and compile? did a
(start-tour ‘(3 4))
work?
+++ neingeist
December 30th, 2005 at 16:12
What do the commas represent in the moves function ? Anybody care to explain ?
December 30th, 2005 at 16:34
@ray:
it’s part of a backquote form:
http://www.lisp.org/HyperSpec/Body/sec_2-4-6.html
+++ neingeist
December 30th, 2005 at 16:40
(start-tour ‘(3 4)) doesnt work..
CG-USER(5): (start-tour ‘(3 4))
Error: attempt to call `MOVE’ which is an undefined function.
this is what the compiler said..
so what is the problem here? pls help.. thank u
December 30th, 2005 at 17:14
@fms:
well, you should really try to load+compile the whole code first, before running it. maybe get used to lisp a little bit?
+++ neingeist
December 30th, 2005 at 17:42
It is most likely that those who are complaining the program is not running properly, don’t even know how to complie the LISP code.
December 30th, 2005 at 18:12
allrite..thank u anyway
December 30th, 2005 at 18:19
>
ermm… then why u didn’t teach us how to compile it…
December 31st, 2005 at 11:00
O_o
just (load “c:/tehpwnagedirectory/filename.lisp”) in allegro.
but..i have this
Error: :INITIAL-ELEMENT is an illegal dimension
[condition type: SIMPLE-ERROR]
error after initializing zero and i still can’t run the code. can you help? :p
December 31st, 2005 at 11:19
oh, you have to put :element-type ‘integer in too. great job and thanks ! ^_^
December 31st, 2005 at 18:26
dear mmu students,
i know this is a good resource, use it strictly as reference, thank you.
Neingeist, good work!
January 3rd, 2006 at 17:10
Nice job..i did try to run the program but i get this Error: `NIL’ is not of the expected type `REAL’
Can you help me to fix it..thankz
January 3rd, 2006 at 17:17
@angel:
please see my previous comment about “make-array”.
+++ neingeist
January 3rd, 2006 at 18:14
hey Grant Palmer, wats wrong wit u pal…
u think ur one big head issit!!
first of all try learn sum basic manners plz..a.h.
i gues u r stupid enuf to expose ur ppl identity!
January 3rd, 2006 at 18:53
Thankz neingeist but it still shows me error after i change the (make array).The error is Error: Attempt to take the value of the unbound variable `BOARD’
January 3rd, 2006 at 19:41
how to change the above code to hueristic function?
January 3rd, 2006 at 21:30
suddently this is the best site of the semester! LOL! Thanks mr. neingeist ! Youre our savior!
January 4th, 2006 at 8:23
After change the make array still got error.
CG-USER(2): (START-TOUR ‘(X Y))
Error: attempt to call `MOVE’ which is an undefined function.
[condition type: UNDEFINED-FUNCTION]
How to fix this. Thank you for your kindness.
January 4th, 2006 at 8:24
I using allegro 6.2.
January 4th, 2006 at 8:41
i have another code
go:-go(5).
go(N):-
time(_),
make_board(N,Board,NbMoves),
knight(NbMoves,1,1,N,Board),!,
time(T),
nl,write(’BMARK_fknight’=[time(T),'N'=N]
),nl,
statistics,show(N,Board).
make_board(N,Board,M):-
M is N*N,
functor(Line,line,N),
findall(Line,range(_,1,N),LBoard),
go:-go(5).
go(N):-
time(_),
make_board(N,Board,NbMoves),
knight(NbMoves,1,1,N,Board),!,
time(T),
nl,write(’BMARK_fknight’=[time(T),'N'=N]
),nl,
statistics,show(N,Board).
make_board(N,Board,M):-
M is N*N,
functor(Line,line,N),
findall(Line,range(_,1,N),LBoard),
Board=..[board|LBoard].
val(I,J,Val,N,Board):-
I>0,I=0,J=nl;true),
fail.
show(_,_):-nl.
move( 2, 1).
move( 2,-1).
move(-2, 1).
move(-2,-1).
move( 1, 2).
move(-1, 2).
move( 1,-2).
move(-1,-2).
time(T) :- statistics(runtime,[_,T]).
January 4th, 2006 at 8:43
i have another version as well
(defun valid-coord (c)
(and (>= c 1) (
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?
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!
January 5th, 2006 at 15:01
wtf : hei i am from UTAR one la , don simply accuse people , stupid .
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
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
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!!!
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…
January 6th, 2006 at 10:16
Old practice: copy and paste
New practice: copy and paste and understand and modify only the variables
LOL
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
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) (
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 !
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..