Fill a NxN grid with numbers from 1 to N. Starting from 1 the next cell can be either two places apart vertically or horizontally or one cell apart diagonally.

002.rkt

#lang typed/racket

(require math/array)

(: possible-moves ((Array Fixnum) Indexes -> (Listof Indexes)))
(define (possible-moves arr idx)
  (let ((shape (array-shape arr)))
    (cast
     (filter (λ ([i : (Vector Integer Integer)]) (and (< -1 (vector-ref i 0) (vector-ref shape 0))
                                                      (< -1 (vector-ref i 1) (vector-ref shape 1))
                                                      (zero? (array-ref arr i))))
             (map (λ ([off : (Vector Integer Integer)])
                    (vector (+ (vector-ref idx 0) (vector-ref off 0))
                            (+ (vector-ref idx 1) (vector-ref off 1))))
                  (list #(-2 0) #(-1 -1) #(-1 1) #(0 -2) #(0 2) #(1 -1) #(1 1)  #(2 0))))
     (Listof Indexes))))

(: solve ((Mutable-Array Fixnum) Indexes Fixnum Fixnum -> (U Void (Array Fixnum))))
(define (solve arr idx n target)
  (if (= n target)
      arr
      (let ((n (cast (+ n 1) Fixnum)))
        (let l ((moves (possible-moves arr idx)))
          (unless (empty? moves)
            (array-set! arr (car moves) n)
            (let ((solution (solve arr (car moves) n target)))
              (if (void? solution)
                  (begin
                    (array-set! arr (car moves) 0)
                    (l (cdr moves)))
                  solution)))))))

(define shape #(10 10))
(: grid (Mutable-Array Fixnum))
(define grid (array->mutable-array (make-array shape 0)))
(define target (cast (* (vector-ref shape 0) (vector-ref shape 1)) Fixnum))
(display target)
(newline)

(array-set! grid #(0 0) 1)

(display (solve grid #(0 0) 1 target))