title: Iterative deepening in common lisp
body: <p>I've written an iterative deepening algorithm, it works except when I add cycle checking, the algorithm returns a deeper solution than it should. But when I don't check for cycles it does work correctly, but it takes too long. Can anyone please spot the bug?</p>
  
  <pre><code>(defun rec-depth-limited (problem node cutoff closed)
    (if (= cutoff 0)
      (if (funcall (problem-goalp problem) node)
            node)
      (if (visited-p node closed)
          nil
          (progn
            ;; when i remove the next line, it works correctly
            (setf (gethash (node-state node) closed) t)
            (loop for child in (expand node (problem-actions problem)) do
              (let ((result (rec-depth-limited problem child (1- cutoff) closed)))
                  (if result
                      (return result))))))))
  
  (defun iterative-deepening (problem)
    "Iterative deepening search"
    (let ((cutoff 0))
      (loop
        (format t "~%cut-off: ~A" cutoff)
        (let ((solution (rec-depth-limited
                               problem
                               (make-node :state (problem-state problem)) 
                               cutoff 
                               (make-hash-table :test #'equalp)))) ;solve problem up to cutoff
          (if (null  solution) 
              (incf cutoff);if solution is not found, increment the depth
              (return solution))))))
  
  (defun visited-p (node table)
    "Checks if state in node was visited before by checking
  if it exists in the table"
    (nth-value 1 (gethash (node-state node) table)))
  </code></pre>
  
  <p>Edit: here is the expand function</p>
  
  <pre><code>(defun expand (node actions)
    "Expands a node, returns a list of the new nodes"
    (remove-if #'null (apply-actions node actions)));apply all actions on all nodes
  
  (defun apply-actions (node actions)
    "Applies all actions to a state, returns a list of new states"
    (mapcan #'(lambda (action) 
                (mapcar #'(lambda (tile) (funcall action tile node))
                       (node-state node)))
            actions))
  </code></pre>
  
  <p>This is one of the actions, they are all the same except for minor changes</p>
  
  <pre><code>(defun slide-right (tile node)
    "slide the tile one cell to the right. returns nil if not possible, 
    otherwise returns a node with the new state"
    (when (can-slide-right-p tile (node-state node));if can slide right
        (and visualize (format t "~%slide ~A to the right" (tile-label tile)))
        (let*  ((newstate (mapcar #'copy-tile (node-state node)));copy the current state
               (depth (node-depth node))
               (newcol (incf (tile-col (find tile newstate :test #'equalp))));update state
               (cost (1+ (node-cost node))))
          (make-node :state newstate ;create new node with the new state
                     :parent node 
                     :depth (1+ depth) 
                     :action (concatenate 'string
                                          "slide "
                                          (tile-label tile)
                                          " right" )
                     :cost cost))))
  </code></pre>
  
  <p>Predicates</p>
  
  <pre><code>(defun can-slide-right-p (tile state)
    "returns T if the specified tile can be sled one cell to the right"
    (let  ((row (tile-row tile)) 
          (end (+ (tile-col tile) (tile-length tile))) ;col at which tile ends after being sled
          (orient (tile-orientation tile)))
      (and (equal orient 'H)
           (or (tile-is-mouse tile) (&lt; end *board-w*))
           (empty-cell-p row end state))))
  
  (defun spans-cell-p (row col tile)
    "returns T if the specified tile spans the specified cell"
    (if (equal (tile-orientation tile) 'H)
        (horizontally-spans-cell-p row col tile)
        (vertically-spans-cell-p row col tile)))
  
  (defun horizontally-spans-cell-p (row col tile)
    "Tests if the specified horizontal tile spans the specified cell"
    (let ((tile-col (tile-col tile))
          (tile-row (tile-row tile))
          (tile-len (tile-length tile)))
      (and (= tile-row row) (&gt;= col tile-col) (&lt; col (+ tile-col tile-len)))))
  
  (defun vertically-spans-cell-p (row col tile)
    "Tests if the specified vertical tile spans the specified cell"
    (let  ((tile-col (tile-col tile))
          (tile-row (tile-row tile))
          (tile-len (tile-length tile)))
      (and (= tile-col col) (&gt;= row tile-row) (&lt; row (+ tile-row tile-len)))))
  </code></pre>