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.<\/p>\n
(defun<\/a> start-tour (position)\r\n(let<\/a> ((board (make-array '(8 8))))\r\n(move position board 1)))\r\n\r\n(defun<\/a> move (position board n)\r\n(setf<\/a> (aref<\/a> board (car<\/a> position) (cadr<\/a> position)) n)\r\n;; (print-board board)\r\n;; (print (evaluate-possible-moves position board))\r\n;; (format t \"~%\")\r\n(cond<\/a> ((=<\/a> n 64) (print-board board))\r\n((null<\/a> (possible-moves position board)) 'failed-dead-end)\r\n((<<\/a> n 64) (move (best-move position board) board (+<\/a> n 1)))))\r\n\r\n(defun<\/a> best-move (position board)\r\n(car<\/a> (evaluate-possible-moves position board)))\r\n\r\n(defun<\/a> evaluate-possible-moves (position board)\r\n;; (print position)\r\n;; (format t \"~%\")\r\n(sort<\/a> (mapcar<\/a> #'(lambda<\/a> (x) (append<\/a> x (list<\/a> (length<\/a> (possible-moves x board)))))\r\n(possible-moves position board))\r\n#'(lambda<\/a> (triple-a triple-b) (<<\/a> (caddr<\/a> triple-a) (caddr<\/a> triple-b)))))\r\n\r\n(defun<\/a> print-board (board)\r\n(do<\/a> ((x 0 (+<\/a> x 1)))\r\n((=<\/a> x 8))\r\n(do<\/a> ((y 0 (+<\/a> y 1)))\r\n((=<\/a> y 8))\r\n(format<\/a> t \"~2D \" (aref<\/a> board x y)))\r\n(format<\/a> t \"~%\"))\r\n(format<\/a> t \"~%\"))\r\n\r\n(defun<\/a> on-board-p (position)\r\n(and<\/a> (>=<\/a> (car<\/a> position) 0)\r\n(<=<\/a> (car<\/a> position) 7)\r\n(>=<\/a> (cadr<\/a> position) 0)\r\n(<=<\/a> (cadr<\/a> position) 7)))\r\n\r\n(defun<\/a> visited-p (position board)\r\n(><\/a> (aref<\/a> board (car<\/a> position) (cadr<\/a> position)) 0))\r\n\r\n(defun<\/a> possible-moves (position board)\r\n(remove-if<\/a> #'(lambda<\/a> (x) (visited-p x board)) (moves position)))\r\n\r\n(defun<\/a> moves (position)\r\n(let<\/a> ((x (car position))\r\n(y (cadr position)))\r\n(remove-if-not<\/a> #'on-board-p\r\n`((,(+<\/a> x 1) ,(+<\/a> y 2))\r\n(,(+<\/a> x 1) ,(-<\/a> y 2))\r\n(,(-<\/a> x 1) ,(+<\/a> y 2))\r\n(,(-<\/a> x 1) ,(-<\/a> y 2))\r\n(,(+<\/a> x 2) ,(+<\/a> y 1))\r\n(,(+<\/a> x 2) ,(-<\/a> y 1))\r\n(,(-<\/a> x 2) ,(+<\/a> y 1))\r\n(,(-<\/a> x 2) ,(-<\/a> y 1))))))<\/pre>\n","protected":false},"excerpt":{"rendered":"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 […]<\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[14],"tags":[],"_links":{"self":[{"href":"https:\/\/blogs.bl0rg.net\/neingeist\/wp-json\/wp\/v2\/posts\/193"}],"collection":[{"href":"https:\/\/blogs.bl0rg.net\/neingeist\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.bl0rg.net\/neingeist\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.bl0rg.net\/neingeist\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.bl0rg.net\/neingeist\/wp-json\/wp\/v2\/comments?post=193"}],"version-history":[{"count":0,"href":"https:\/\/blogs.bl0rg.net\/neingeist\/wp-json\/wp\/v2\/posts\/193\/revisions"}],"wp:attachment":[{"href":"https:\/\/blogs.bl0rg.net\/neingeist\/wp-json\/wp\/v2\/media?parent=193"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.bl0rg.net\/neingeist\/wp-json\/wp\/v2\/categories?post=193"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.bl0rg.net\/neingeist\/wp-json\/wp\/v2\/tags?post=193"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}