N-Queens puzzle (using AMK)

Location: contrib, 28 Lines

; Scheme 9 from Empty Space, Function Library
; By Nils M Holm, 2013
; Placed in the Public Domain
;
; (queens n)  ==>  list
;
; Solve the N-Queens puzzle using AMK. All solutions for the
; given board size will be returned, where the offset in each
; list is an X position on the board and the value at that
; offset is the corresponding Y position. E.g., the board
; (2 0 3 1) would look like this:
;
; . . & . 3
; & . . . 2
; . . . & 1
; . & . . 0
; 0 1 2 3
;
; Example:   (queens 4)  ==>  ((2 0 3 1) (1 3 0 2))

(load-from-library "amk.scm")

(define (safeo p1x p1y p2x p2y)
  (all (/=p p1x p2x)
       (/=p p1y p2y)
       (/=p (abs (- p1x p2x))
            (abs (- p1y p2y)))))

(define (board-safeo x y n b)
  (any (nullo b)
       (fresh (a d nn)
         (conso a d b)
         (eql nn (- n 1))
         (safeo x y nn a)
         (board-safeo x y nn d))))

(define (queenso n b z r)
  (any (all (== n z)
            (== b r))
       (fresh (t nn nb)
         (range t 0 (- z 1))
         (board-safeo n t n b)
         (eql nn (+ 1 n))
         (conso t b nb)
         (queenso nn nb z r))))

(define (queens z)
  (run* (q) (queenso 0 '() z q)))

contact  |  privacy