

Solve the eight queens puzzle.



You can extend the problem to solve the puzzle with a board of size   NxN.

For the number of solutions for small values of   N,   see   OEIS: A000170.



Related tasks

 A* search algorithm
 Solve a Hidato puzzle
 Solve a Holy Knight's tour
 Knight's tour
 Peaceful chess queen armies
 Solve a Hopido puzzle
 Solve a Numbrix puzzle
 Solve the no connection puzzle


(def nqueens (n (o queens))
  (if (< len.queens n)
    (let row (if queens (+ 1 queens.0.0) 0)
      (each col (range 0 (- n 1))
        (let new-queens (cons (list row col) queens)
          (if (no conflicts.new-queens)
            (nqueens n new-queens)))))
    (prn queens)))
 
; check if the first queen in 'queens' lies on the same column or diagonal as
; any of the others
(def conflicts (queens)
  (let (curr . rest) queens
    (or (let curr-column curr.1
          (some curr-column (map [_ 1] rest)))  ; columns
        (some [diagonal-match curr _] rest))))
 
(def diagonal-match (curr other)
  (is (abs (- curr.0 other.0))
      (abs (- curr.1 other.1))))