Heuristic Search on 8 Tile Puzzles

gistfile1.rkt

#lang racket
(require data/heap)
(require racket/trace)

;globals
  (define GOAL (list 1 2 3 4 5 6 7 8 0))
  (define GOAL-COORDINATES (list
                            (list 0 0) (list 0 1) (list 0 2)
                            (list 1 0) (list 1 1) (list 1 2)
                            (list 2 0) (list 2 1) (list 2 2)))
  
  (define PUZZLES (list
                   (list 8 3 2 5 1 0 7 4 6)
                   (list 0 7 1 6 4 8 2 5 3)
                   (list 8 4 0 6 7 3 5 2 1)
                   (list 5 0 2 3 6 7 1 4 8)
                   (list 6 5 3 1 8 2 0 4 7)
                   (list 0 2 5 1 8 3 7 4 6)
                   (list 8 3 4 0 6 1 2 5 7)
                   (list 0 3 4 5 2 7 6 8 1)))
  
  (define OPEN (make-heap (lambda (v1 v2) (vertex-<= v1 v2))))
  (define CLOSED (make-hash))
  
;vertex structure
  (struct vertex (state action previous g h f))
  (define (make-vertex state)
    (vertex state
            'nil
            'nil
            'nil
            (calculate-h state)
            'nil))
  
  (define (vertex-<= v1 v2) (<= (vertex-h v1) (vertex-h v2)))
  
  (define (calculate-h state)
    (apply + (flatten
               (map (lambda (i)
                      (map (lambda (j)
                             (if (eqv? 0 (list-ref state (+ (* 3 i) j)))
                                 0
                                 (calculate-manhattan-distance (list-ref state (+ (* 3 i) j)) i j)))
                           (list 0 1 2)))
                    (list 0 1 2)))))
  
  (define (calculate-manhattan-distance key x y)
    (+ (abs (- (first (list-ref GOAL-COORDINATES (- key 1))) x))
       (abs (- (second (list-ref GOAL-COORDINATES (- key 1))) y))))
  
;a* graph search algorithm
  (define (EXPAND vertex) (list vertex))

  
;2. construct the manhattan distance heuristics for 8 tile puzzles
  (map calculate-h PUZZLES)