Towers of hanoi, breadth-first search

hanoi.rkt

#lang racket
(require data/heap)

;;; Not the most optimized version.

(define N 12)

(define (hanoi N)
  (define visited (make-hash))
  (define heap (make-heap (λ(a b) (<= (first a) (first b)))))
  (define state0 (list (build-list N add1) '() '()))
  (heap-add! heap (list 0 state0))
  (let loop ()
    (define-values (depth state) (apply values (heap-min heap)))
    (heap-remove-min! heap)
    (if (hash-has-key? visited state)
        (loop)
        (let ()
          (hash-set! visited state #t)
          (if (and (empty? (first state))
                   (empty? (second state)))
              (list 'found depth)
              (let ()
                (for* ([from (in-range 3)]
                       [to (in-range 3)])
                  (unless (= from to)
                    (define lfrom (list-ref state from))
                    (define lto (list-ref state to))
                    (when (and
                           (not (empty? lfrom))
                           (or (empty? lto)
                               (< (first lfrom) (first lto))))
                      (heap-add! heap
                                 (list (+ depth 1)
                                       (list-set (list-set state from (rest lfrom))
                                                 to
                                                 (cons (first lfrom) lto)))))))
                (if (= 0 (heap-count heap))
                    'not-found
                    (loop))))))))

(define solution-length (time (hanoi N)))

(displayln solution-length) ; should be 2^N - 1