

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


(defun queens (n &optional (m n))
  (if (zerop n)
      (list nil)
      (loop for solution in (queens (1- n) m)
            nconc (loop for new-col from 1 to m
                         when (loop for row from 1 to n
                                     for col in solution
                                     always (/= new-col col (+ col row) (- col row)))
                         collect (cons new-col solution)))))
 
(defun print-solution (solution)
  (loop for queen-col in solution
        do (loop for col from 1 to (length solution)
                  do (write-char (if (= col queen-col) #\Q #\.)))
           (terpri))
  (terpri))
 
(defun print-queens (n)
  (mapc #'print-solution (queens n)))