Arc Forum | Actually, the above code contains an error: (~mem pos visited) should be: ...

Arc Forum

5 points by rntz 5869 days ago | link | parent

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