Knight's Tour Depth First Search Backtracking

Question

I'm working on a knight's tour implementation using DFS.

My problem is, when I run it, it works fine up to step 20, but after that the algorithm freaks out and outputs this on a 5x5 board (there is a solution for a 5x5 board starting at (0,0)):

(1  10 5  16 24)
(4  15 2  11 20)
(9  6  17 23 22)
(14 3  8  19 12)
(7  18 13 21 25)

*Legal successors must be 0 <= row < n and 0 <= column < n and not be a previous step.

My implementation involves generating *legal successors using the genSuccessors function, throwing them onto a stack and recursively running the algorithm with the item at the top of the stack as the new current position. I only increment the step_count (in charge of tracking the order of squares the knight visits) if the next position is a step not taken before. When I cannot generate any more children, the algorithm explores other alternatives in the frontier until frontier empty (fail condition) or the step_count = # squares on the board (win).

I think the algorithm in general is sound.

edit: I think the problem is that when I can't generate more children, and I go to explore the rest of the frontier I need to scrap some of the current tour. My question is, how do I know how far back I need to go?

Graphically, in a tree I think I would need to go back up to the closest node that had a branch to an unvisited child and restart from there scrapping all the nodes visited when going down the previous (wrong) branch. Is this correct? How would I keep track of that in my code?

Thanks for reading such a long post; and thanks for any help you guys can give me.

John Clements John Clements · Accepted Answer · 2014-02-07T06:32:09

Yikes! Your code is really scary. In particular:

1) It uses mutation everywhere. 2) It tries to model "return". 3) It doesn't have any test cases.

I'm going to be a snooty-poo, here, and simply remark that this combination of features makes for SUPER-hard-to-debug programs.

Also... for DFS, there's really no need to keep track of your own stack; you can just use recursion, right?

Sorry not to be more helpful.

Here's how I'd write it:

#lang racket

;; a position is (make-posn x y)
(struct posn (x y) #:transparent)

(define XDIM 5)
(define YDIM 5)

(define empty-board
  (for*/set ([x XDIM]
             [y YDIM])
    (posn x y)))

(define (add-posn a b)
  (posn (+ (posn-x a) (posn-x b))
        (+ (posn-y a) (posn-y b))))

;; the legal moves, represented as posns:
(define moves
  (list->set
   (list (posn 1 2) (posn 2 1)
         (posn -1 2) (posn 2 -1)
         (posn -1 -2) (posn -2 -1)
         (posn 1 -2) (posn -2 1))))

;; reachable knights moves from a given posn
(define (possible-moves from-posn)
  (for/set ([m moves])
    (add-posn from-posn m)))

;; search loop. invariant: elements of path-taken are not
;; in the remaining set. The path taken is given in reverse order.
(define (search-loop remaining path-taken)
  (cond [(set-empty? remaining) path-taken]
        [else (define possibilities (set-intersect (possible-moves
                                                    (first path-taken))
                                                   remaining))
              (for/or ([p possibilities])
                (search-loop (set-remove remaining p)
                             (cons p path-taken)))]))

(search-loop (set-remove empty-board (posn 0 0)) (list (posn 0 0)))

;; start at every possible posn:
#;(for/or ([p empty-board])
  (search-loop (set-remove empty-board p) (list p)))

Knight's Tour Depth First Search Backtracking

1 Answers