#lang racket

(define (solve N)
  (define (pair r c) (+ c (* r N)))
  (define N^2 (* N N))
  (define config (make-vector N^2 #f))
  (define (disconnected?)
    (define visited (make-vector N^2 #f))
    (define init-pos
      (for*/or ([r (in-range N)]
                [c (in-range N)])
        (and (vector-ref config (pair r c)) (cons r c))))
    (cond
      [init-pos
       (let dfs ([r (car init-pos)] [c (cdr init-pos)])
         (when (and (<= 0 r (sub1 N))
                    (<= 0 c (sub1 N))
                    (not (vector-ref visited (pair r c)))
                    (vector-ref config (pair r c)))
           (vector-set! visited (pair r c) #t)
           (for* ([dy '(-1 0 1)] [dx '(-1 0 1)])
             (dfs (+ r dy) (+ c dx)))))
       (for*/or ([r (in-range N)]
                 [c (in-range N)])
         (and (not (vector-ref visited (pair r c)))
              (vector-ref config (pair r c))))]
      [else
       ; trivial case (no leaves)
       #f]))
  (let fill-config ([r 0] [c 0])
    (cond
      [(= r N) (if (disconnected?) 0 1)]
      [(= c N) (fill-config (add1 r) 0)]
      [else (vector-set! config (pair r c) #f)
            (define c1 (fill-config r (add1 c)))
            (vector-set! config (pair r c) #t)
            (define c2 (fill-config r (add1 c)))
            (+ c1 c2)])))

(for ([i (in-range 20)])
  (time (printf "~a: ~a\n" i (solve i))))