Source code in the echolisp programming language

(require 'plot)
(define *knight-moves* 
	'((2 . 1)(2 . -1 ) (1 . -2) (-1 . -2  )(-2 . -1) (-2 . 1) (-1 . 2) (1 . 2))) 
(define *hit-squares* null)
(define *legal-moves* null)
(define *tries* 0)

(define (square x y n ) (+ y (* x n)))
(define (dim n) (1- (* n n))) ; n^2 - 1

;; check legal knight move from sq
;; return null or (list destination-square)

(define (legal-disp n sq k-move)
 (let ((x (+ (quotient sq n) (first k-move)))
 	   (y (+  (modulo sq n)  (rest k-move))))
 	   (if (and (>= x 0) (< x n) (>= y 0) (< y n))
 	       (list (square x y n))  null)))
 	       
 ;; list of legal destination squares from sq
 (define (legal-moves  sq  k-moves n )
           (if (null? k-moves) null
           (append (legal-moves sq (rest k-moves) n) (legal-disp n sq (first k-moves)))))

;; square freedom = number of destination squares not already reached
(define (freedom sq)
		(for/sum ((dest (vector-ref *legal-moves* sq)))
				(if (vector-ref *hit-squares* dest) 0 1)))
				
;; The chess adage" A knight on the rim is dim" is false here :
;; choose to move to square with smallest freedom : Warnsdorf's rule
(define (square-sort a b)
	(< (freedom a) (freedom b)))
				
;; knight tour engine
(define (play sq step starter last-one wants-open)
(set! *tries* (1+ *tries*))
		(vector-set! *hit-squares* sq step) ;; flag used square
		(if (= step last-one) (throw 'HIT last-one)) ;; stop on first path found

		(when (or wants-open ;; cut search iff closed path
		(and  (< step last-one) (> (freedom starter) 0))) ;; this ensures a closed path
		
		(for ((target (list-sort square-sort (vector-ref *legal-moves* sq))))
			 (unless (vector-ref *hit-squares* target)
			         (play target (1+ step)  starter last-one wants-open))))
		(vector-set! *hit-squares* sq #f)) ;; unflag used square
		
(define (show-steps n wants-open)
	(string-delimiter "")
	(if wants-open
		(printf "♘-tour: %d tries."  *tries*)
		(printf "♞-closed-tour: %d tries."  *tries*))
	(for ((x n))
		(writeln)
		(for((y n))
        	(write (string-pad-right (vector-ref *hit-squares*  (square x y n)) 4)))))


(define (k-tour (n  8) (starter 0) (wants-open #t))
(set! *hit-squares* (make-vector (* n n) #f))
;; build vector of legal moves for squares 0..n^2-1
(set! *legal-moves* 
		(build-vector (* n n) (lambda(sq) (legal-moves sq *knight-moves* n))))
(set! *tries* 0) ; counter
	(try
		(play starter 0 starter (dim n) wants-open)
		(catch (hit mess) (show-steps n wants-open))))


(k-tour 8 0 #f)
♞-closed-tour: 66 tries.
0   47  14  31  62  27  12  29 
15  32  63  54  13  30  57  26 
48  1   46  61  56  59  28  11 
33  16  55  50  53  44  25  58 
2   49  42  45  60  51  10  39 
17  34  19  52  43  40  7   24 
20  3   36  41  22  5   38  9  
35  18  21  4   37  8   23  6  

(k-tour 20 57)
♘-tour: 400 tries.
31  34  29  104 209 36  215 300 211 38  213 354 343 40  345 386 383 42  1   388
28  103 32  35  216 299 210 37  214 335 342 39  346 385 382 41  390 387 396 43 
33  30  105 208 201 308 301 336 323 212 353 340 355 344 391 384 395 0   389 2  
102 27  202 219 298 217 322 309 334 341 356 347 358 351 376 381 378 399 44  397
203 106 207 200 307 228 311 302 337 324 339 352 373 364 379 392 375 394 3   368
26  101 220 229 218 297 304 321 310 333 348 357 350 359 374 377 380 367 398 45 
107 204 199 206 227 306 231 312 303 338 325 330 363 372 365 328 393 254 369 4  
100 25  122 221 230 233 296 305 320 313 332 349 326 329 360 371 366 251 46  253
121 108 205 198 145 226 237 232 295 286 319 314 331 362 327 316 255 370 5   178
24  99  144 123 222 129 234 279 236 281 294 289 318 315 256 361 250 179 252 47 
109 120 111 130 197 146 225 238 285 278 287 272 293 290 317 180 257 162 177 6  
98  23  124 143 128 223 276 235 280 239 282 291 288 265 270 249 176 181 48  161
115 110 119 112 131 196 147 224 277 284 273 266 271 292 245 258 163 174 7   58 
22  97  114 125 142 127 140 275 194 267 240 283 264 269 248 175 182 59  160 49 
87  116 95  118 113 132 195 148 187 274 263 268 191 244 259 246 173 164 57  8  
96  21  88  133 126 141 150 139 262 193 190 241 260 247 172 183 60  159 50  65 
77  86  117 94  89  138 135 188 149 186 261 192 171 184 243 156 165 64  9   56 
20  81  78  85  134 93  90  151 136 189 170 185 242 155 166 61  158 53  66  51 
79  76  83  18  91  74  137 16  169 72  153 14  167 70  157 12  63  68  55  10 
82  19  80  75  84  17  92  73  152 15  168 71  154 13  62  69  54  11  52  67


(define (step-color x y n last-one)
		(letrec ((sq (square (floor x) (floor y) n))
		(step (vector-ref *hit-squares* sq) n n))
		(cond ((= 0 step) (rgb 1 0 0)) ;; red starter
			  ((= last-one step) (rgb 0 1 0)) ;; green end
			  (else (gray (// step n n))))))
		
(define  ( k-plot n)
	(plot-rgb (lambda (x y) (step-color x y n (dim n))) (- n epsilon) (- n epsilon)))