; In the CLIQUE problem, a state consists of a graph (adjacency matrix),
;   a list of vertices in the clique, and
;   a list of vertices in the graph
; Vertices are numbered beginning with 0 (for ease in using LIST-REF
;   to consult the graph)
; Partial cliques are constructed in numerical order of the vertices,
;   so that a vertex rejected for a particular clique is never reconsidered.

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

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




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



; An optimistic estimate is that the clique can be expanded to
;   include all unconsidered elements
; Since the given problem is a maximization problem, the estimator
;   must be negated

(define (estimator state) ( - (+ (length (clique state))
                                 (length (unconsidered state)))))


; A state is a goal state if all vertices have been included

(define (goal? state) (null? (unconsidered state)))


; A potential successor is obtained by adding each unconsidered vertex
;   to the clique.  A potential successor is an actual successor if
;   it is adjacent to all vertices already in the clique.  This
;   condition is tested by the predicate ALL-ADJACENT?
; The actual work of finding successors is done by the recursive
;   function SUCCESSORS-REC, which considers for addition to the
;   clique each unconsidered vertex.  It maintains a list
;   SUCCESSORS-SO-FAR of the actual successor states already found

(define (successors state)
  (define (all-adjacent? vertex vertex-list graph)
    (cond ((null? vertex-list) #t)
          ((zero? (list-ref (list-ref graph vertex) (car vertex-list))) #f)
          (else (all-adjacent? vertex (cdr vertex-list) graph))))
  (define (successors-rec graph clique unconsidered successors-so-far)
    (cond ((null? unconsidered) successors-so-far)
          ((all-adjacent? (car unconsidered) clique graph)
           (successors-rec graph
                           clique
                           (cdr unconsidered)
                           (cons (build-state
                                   graph
                                   (cons (car unconsidered) clique)
                                   (cdr unconsidered))
                                 successors-so-far)))
          (else
            (successors-rec graph
                            clique
                            (cdr unconsidered)
                            successors-so-far))))
  (successors-rec (graph state) (clique state) (unconsidered state)
                  '()))