Arc Forumnew | comments | leaders | submitlogin
4 points by rntz 5869 days ago | link | parent

    (set board-size 8)

    (set moves
      '((-2 . -1) (-2 . 1)
        (-1 . -2) (-1 . 2)
        ( 1 . -2) ( 1 . 2)
        ( 2 . -1) ( 2 . 1)))

    (def move (pos diff)
      (cons (+ car.pos car.diff) (+ cdr.pos cdr.diff)))

    (def valid (pos visited)
      (and
        (< -1 car.pos board-size)
        (< -1 cdr.pos board-size)
        (~mem pos visited)))

    (def moves-from (pos) (map [move pos _] moves))

    (def succs (pos visited)
      (let valid [valid _ visited]
        (sort (compare < [count valid moves-from._])
          (keep valid moves-from.pos))))

    (def knights-tour (start (o visited))
      (let visited (cons start visited)
        (if (is len.visited (* board-size board-size)) rev.visited
          (ormap [knights-tour _ visited] (succs start visited)))))
Although I aimed for clarity and modularity when writing the above, rather than lines of code or speed, it actually does quite well in both departments. It takes about three seconds on a 20x20 board, and about ten for a 30x30. I suspect that using a hashtable to keep track of visited squares rather than a simple list would speed it up on higher board sizes.


5 points by rntz 5868 days ago | link

Actually, the above code contains an error:

    (~mem pos visited)
should be:

    (~mem [iso _ pos] visited)
Otherwise, the code will generate incorrect tours. This increases runtime. However, I've also tested a version which uses hashtables, and as I suspected, this significantly decreases runtime. To use hashtables, replace 'valid and 'knights-tour in the original with the following:

    (def valid (pos visited)
      (and
        (< -1 car.pos board-size)
        (< -1 cdr.pos board-size)
        (no visited.pos)))
    
    (def trace (k e)
      (cons k (let v e.k (if (isnt t v) (trace v e)))))

    (def knights-tour (start (o prev t) (o visited (table)))
      (= visited.start prev)
      (do1 (if (is len.visited (* board-size board-size)) (rev:trace start visited)
             (ormap [knights-tour _ start visited] (succs start visited)))
        (= visited.start nil)))

-----

1 point by babo 5868 days ago | link

Elegant solution, hats off!

-----