; A state in the Hamiltonian Circuit problem consists of
;    a graph, represented in adjacency matrix form as a list of lists
;    a sequence of vertices representing the circuit so far, and
;    a list of vertices not yet part of the circuit
; A start state has an empty circuit so far; an alternate
;    representation would be to have the first vertex be included
;    as part of the circuit

(define (graph state) (car state))
(define (circuit state) (cadr state))
(define (unconsidered state) (caddr state))

(define (build-state g c u) (list g c u))

(define start1 '(((0 1 0 0 0 0 1) (1 0 1 0 0 0 0)
                  (0 1 0 1 0 0 0) (0 0 1 0 1 0 0)
                  (0 0 0 1 0 1 0) (0 0 0 0 1 0 1)
                  (1 0 0 0 0 1 0))
                 ()
                 (0 1 2 3 4 5 6)))
(define start2 '(((0 0 0 0 0 1 0) (1 0 1 1 0 0 1)
                  (1 0 0 0 0 0 0) (1 0 1 0 0 0 0)
                  (1 1 1 1 0 0 1) (1 1 1 1 1 0 1)
                  (1 0 1 1 0 0 0))
                 ()
                 (0 1 2 3 4 5 6)))
(define start3 '(((0 1 0 1 0 1 0 1) (1 0 1 0 1 0 1 0)
                  (0 1 0 1 0 1 0 1) (1 0 1 0 1 0 1 0)
                  (0 1 0 1 0 1 0 1) (1 0 1 0 1 0 1 0)
                  (0 1 0 1 0 1 0 1) (1 0 1 0 1 0 1 0))
                 ()
                 (0 1 2 3 4 5 6 7)))
(define start4 '(((0 1 1 1 1 1 0) (1 0 1 1 1 1 0)
                  (1 1 0 1 1 1 0) (1 1 1 0 1 1 0)
                  (1 1 1 1 0 1 0) (1 1 1 1 1 0 0)
                  (1 1 1 1 1 1 0))
                 ()
                 (0 1 2 3 4 5 6)))
(define start5 '(((0 0 1 0 1 0 1 0) (0 1 0 1 0 1 0 1)
                  (0 0 1 0 1 0 1 0) (0 1 0 1 0 1 0 1)
                  (0 0 1 0 1 0 1 0) (0 1 0 1 0 1 0 1)
                  (0 0 1 0 1 0 1 0) (0 1 0 1 0 1 0 1))
                 ()
                 (0 1 2 3 4 5 6 7)))
(define start6 '(((0 1 1 1 1 1) (0 0 1 1 0 1)
                  (1 0 0 1 1 0) (1 0 1 0 0 1)
                  (1 1 1 0 0 1) (0 1 1 1 1 0))
                 ()
                 (0 1 2 3 4 5)))


; An auxiliary function to determine whether vertices V and W are
;   adjacent in graph G (represented by an adjacency matrix as a list
;   of lists

(define (adjacent? v w g)
  (not (zero? (list-ref (list-ref g v) w))))


; A list of vertices represents a Hamiltonian circuit iff every
;   vertex is included, and there is an edge from the last vertex
;   added to the circuit (appearing as the car of the list)
;   and the first one added (appearing as the car of the reverse of
;   the list).
; Doesn't work for graphs with 1 vertex

(define (goal? state)
  (and (null? (unconsidered state))
       (adjacent? (car (circuit state))
                  (car (reverse (circuit state)))
                  (graph state))))


; Preference is given to expanding states with few vertices not included
;   in a cycle

(define (estimator state) (length (unconsidered state)))


; Every unconsidered vertex must be considered as the next vertex of the
;   circuit.  The SUCCESSORS function first adds each possible vertex, and
;   then calls FILTER to remove those in which the newly added vertex is
;   not adjacent to the previously added vertex.  FILTER calls an
;   auxiliary function REMOVE to do the removing.
; Circuits are constructed in reverse, which is ok by the symmetry of
;   the problem.

(define (successors state)
  ; remove the first occurrence of an element ELT from a list LYST
  (define (remove elt lyst)
    (cond ((null? lyst) lyst)
          ((eq? elt (car lyst)) (cdr lyst))
          (else (cons (car lyst) (remove elt (cdr lyst))))))
  (define (filter state-list)
    (cond ((null? state-list) state-list)
          ((let ((c (circuit (car state-list))))
             (or (null? (cdr c))
                 (adjacent? (cadr c) (car c) (graph (car state-list)))))
           (cons (car state-list) (filter (cdr state-list))))
          (else (filter (cdr state-list)))))
  (filter (map (lambda (vertex)
                 (build-state (graph state)
                              (cons vertex (circuit state))
                              (remove vertex (unconsidered state))))
               (unconsidered state))))