

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 queens)
  prn "step: " queens  # show progress
  if (len.queens = n)
    prn "solution! " queens
    # else
    let row (if queens (queens.zero.zero + 1) 0)
      for col 0 (col < n) ++col
        let new_queens (cons (list row col) queens)
          if (no conflicts.new_queens)
            (nqueens n new_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 (fn(_) (= _ curr_column))
               (map cadr rest)))  # columns
       (some (fn(_) (diagonal_match curr _))
             rest)
 
def (diagonal_match curr other)
  (= (abs (curr.0 - other.0))
     (abs (curr.1 - other.1)))