N-queens problem

N-queens problem is a programming puzzle. It lays out a problem which Rosetta Code users are encouraged to solve, using languages and techniques they know. Multiple approaches are not discouraged, so long as the puzzle guidelines are followed. For other Puzzles, see Category:Puzzles.

Solve the eight queens puzzle. You can extend the problem to solve the puzzle with a board of side NxN.

C

There is a solution on wikipedia.

Forth

<lang forth>variable solutions variable nodes

bits ( n -- mask ) 1 swap lshift 1- ;

lowBit ( mask -- bit ) dup negate and ;

lowBit- ( mask -- bits ) dup 1- and ;

next3 ( dl dr f files -- dl dr f dl' dr' f' )

 invert >r
 2 pick r@ and 2* 1+
 2 pick r@ and 2/
 2 pick r> and ;

try ( dl dr f -- )

 dup if
   1 nodes +!
   dup 2over and and
   begin ?dup while
     dup >r lowBit next3 recurse r> lowBit-
   repeat
 else 1 solutions +! then
 drop 2drop ;

queens ( n -- )

 0 solutions ! 0 nodes !
 -1 -1 rot bits try
 solutions @ . ." solutions, " nodes @ . ." nodes" ;

8 queens \ 92 solutions, 1965 nodes</lang>

Haskell

<lang haskell>import Control.Monad

-- given n, "queens n" solves the n-queens problem, returning a list of all the -- safe arrangements. each solution is a list of the columns where the queens are -- located for each row queens :: Int -> Int queens n = foldM oneMoreQueen [] [1..n] -- foldM folds in the list monad, which is convenient for "nondeterminstically" -- finding "all possible solutions" of something. the initial value [] corresponds -- to the only safe arrangement of queens in 0 rows

 where -- given a safe arrangement y of queens in the first i rows,
       -- "add_queen y _" returns a list of all the safe arrangements of queens
       -- in the first (i+1) rows
       oneMoreQueen y _ = [ x : y | x <- [1..n], safe x y 1]

-- "safe x y n" tests whether a queen at column x would be safe from previous -- queens in y where the first element of y is n rows away from x, the second -- element is (n+1) rows away from x, etc. safe x [] n = True safe x (c:y) n = and [ x /= c , x /= c + n , x /= c - n , safe x y (n+1)] -- we only need to check for queens in the same column, and the same diagonals; -- queens in the same row are not possible by the fact that we only pick one -- queen per row

-- prints what the board looks like for a solution; with an extra newline printSolution y = do mapM_ (\x -> putStrLn [if z == x then 'Q' else '.' | z <- [1..n]]) y

                    putStrLn ""
 where n = length y

-- prints all the solutions for 6 queens main = mapM_ printSolution $ queens 6</lang>

If you just want one solution, simply take the head of the result of queens n; since Haskell is lazy, it will only do as much work as needed to find one solution and stop.

J

This is one of several J solutions shown and explained on this J wiki page

<lang j>perm =: ! A.&i. ] NB. all permutations of integers 0 to y comb2 =: (, #: I.@,@(</)&i.)~ NB. all size 2 combinations of integers 0 to y mask =: [ */@:~:&(|@-/) { queenst=: comb2 (] #"1~ mask)&.|: perm</lang>

Java

Translation of: C

<lang java>public class NQueens {

 private static int[] b = new int[8];
 private static int s = 0;

 static boolean unsafe(int y) {
   int x = b[y];
   for (int i = 1; i <= y; i++) {
     int t = b[y - i];
     if (t == x ||
         t == x - i ||
         t == x + i) {
       return true;
     }
   }

   return false;
 }

 public static void putboard() {
   System.out.println("\n\nSolution " + (++s));
   for (int y = 0; y < 8; y++) {
     for (int x = 0; x < 8; x++) {
       System.out.print((b[y] == x) ? "|Q" : "|_");
     }
     System.out.println("|");
   }
 }

 public static void main(String[] args) {
   int y = 0;
   b[0] = -1;
   while (y >= 0) {
     do {
       b[y]++;
     } while ((b[y] < 8) && unsafe(y));
     if (b[y] < 8) {
       if (y < 7) {
         b[++y] = -1;
       } else {
         putboard();
       }
     } else {
       y--;
     }
   }
 }

}</lang>

OCaml

Library: FaCiLe

<lang ocaml>(* Authors: Nicolas Barnier, Pascal Brisset

  Copyright 2004 CENA. All rights reserved.
  This code is distributed under the terms of the GNU LGPL *)

open Facile open Easy

(* Print a solution *) let print queens =

 let n = Array.length queens in
 if n <= 10 then (* Pretty printing *)
   for i = 0 to n - 1 do
     let c = Fd.int_value queens.(i) in (* queens.(i) is bound *)
     for j = 0 to n - 1 do
       Printf.printf "%c " (if j = c then '*' else '-')
     done;
     print_newline ()
   done
 else (* Short print *)
   for i = 0 to n-1 do
     Printf.printf "line %d : col %a\n" i Fd.fprint queens.(i)
   done;
 flush stdout;

(* Solve the n-queens problem *) let queens n =

 (* n decision variables in 0..n-1 *)
 let queens = Fd.array n 0 (n-1) in

 (* 2n auxiliary variables for diagonals *)
 let shift op = Array.mapi (fun i qi -> Arith.e2fd (op (fd2e qi) (i2e i))) queens in
 let diag1 = shift (+~) and diag2 = shift (-~) in

 (* Global constraints *)
 Cstr.post (Alldiff.cstr queens);
 Cstr.post (Alldiff.cstr diag1);
 Cstr.post (Alldiff.cstr diag2);

 (* Heuristic Min Size, Min Value *)
 let h a = (Var.Attr.size a, Var.Attr.min a) in
 let min_min = Goals.Array.choose_index (fun a1 a2 -> h a1 < h a2) in

 (* Search goal *)
 let labeling = Goals.Array.forall ~select:min_min Goals.indomain in

 (* Solve *)
 let bt = ref 0 in
 if Goals.solve ~control:(fun b -> bt := b) (labeling queens) then begin
   Printf.printf "%d backtracks\n" !bt;
   print queens
 end else
   prerr_endline "No solution"

let _ =

 if Array.length Sys.argv <> 2
 then raise (Failure "Usage: queens <nb of queens>");
 Gc.set ({(Gc.get ()) with Gc.space_overhead = 500}); (* May help except with an underRAMed system *)
 queens (int_of_string Sys.argv.(1));;</lang>

Python

This solution, originally by [Raymond Hettinger] for demonstrating the power of the itertools module, generates all solutions.

<lang python>from itertools import permutations

n = 8 cols = range(n) for vec in permutations(cols):

   if n == len(set(vec[i]+i for i in cols)) \
        == len(set(vec[i]-i for i in cols)):
       print ( vec )</lang>

The output is presented in vector form (each number represents the column position of a queen on consecutive rows). The vector can be pretty printed by substituting a call to board instead of print, with the same argument, and where board is pre-defined as: <lang python>def board(vec):

   print ("\n".join('.' * i + 'Q' + '.' * (n-i-1) for i in vec) + "\n===\n")</lang>

Raymond's description is:

With the solution represented as a vector with one queen in each row, we don't have to check to see if two queens are on the same row. By using a permutation generator, we know that no value in the vector is repeated, so we don't have to check to see if two queens are on the same column. Since rook moves don't need to be checked, we only need to check bishop moves.

The technique for checking the diagonals is to add or subtract the column number from each entry, so any two entries on the same diagonal will have the same value (in other words, the sum or difference is unique for each diagonal). Now all we have to do is make sure that the diagonals for each of the eight queens are distinct. So, we put them in a set (which eliminates duplicates) and check that the set length is eight (no duplicates were removed).

Any permutation with non-overlapping diagonals is a solution. So, we print it and continue checking other permutations.

One disadvantage with this solution is that we can't simply "skip" all the permutations that start with a certain prefix, after discovering that that prefix is incompatible. For example, it is easy to verify that no permutation of the form (1,2,...) could ever be a solution, but since we don't have control over the generation of the permutations, we can't just tell it to "skip" all the ones that start with (1,2).

Alternative Solution

Works with: Python version 2.6, 3.x

<lang python># From: http://wiki.python.org/moin/SimplePrograms, with permission from the author, Steve Howell BOARD_SIZE = 8

def under_attack(col, queens):

   return col in queens or \
          any(abs(col - x) == len(queens)-i for i,x in enumerate(queens))

def solve(n):

   if n == 0: return [[]]
   smaller_solutions = solve(n-1)
   return [solution+[i+1]
             for i in range(BOARD_SIZE)
             for solution in smaller_solutions
             if not under_attack(i+1, solution)]

for answer in solve(BOARD_SIZE): print(list(enumerate(answer, start=1)))</lang>

Ruby

This implements the heuristics found on the wikipedia page to return just one solution <lang ruby># 1. Divide n by 12. Remember the remainder (n is 8 for the eight queens

1. puzzle).
2. 2. Write a list of the even numbers from 2 to n in order.
3. 3. If the remainder is 3 or 9, move 2 to the end of the list.
4. 4. Append the odd numbers from 1 to n in order, but, if the remainder is 8,
5. switch pairs (i.e. 3, 1, 7, 5, 11, 9, …).
6. 5. If the remainder is 2, switch the places of 1 and 3, then move 5 to the
7. end of the list.
8. 6. If the remainder is 3 or 9, move 1 and 3 to the end of the list.
9. 7. Place the first-column queen in the row with the first number in the
10. list, place the second-column queen in the row with the second number in
11. the list, etc.

def n_queens(n)

 if n == 1
   return "Q"
 elsif n < 4
   puts "no solutions for n=#{n}"
   return ""
 end

 evens = (2..n).step(2).to_a
 odds = (1..n).step(2).to_a

 rem = n % 12  # (1)
 nums = evens  # (2)

 nums.push(nums.shift) if rem == 3 or rem == 9  # (3)

 # (4)
 if rem == 8
   odds = odds.each_slice(2).inject([]) {|ary, (a,b)| ary += [b,a]}
 end
 nums.concat(odds)

 # (5)
 if rem == 2
   idx = []
   [1,3,5].each {|i| idx[i] = nums.index(i)}
   nums[idx[1]], nums[idx[3]] = nums[idx[3]], nums[idx[1]]
   nums.slice!(idx[5])
   nums.push(5)
 end

 # (6)
 if rem == 3 or rem == 9
   [1,3].each do |i|
     nums.slice!( nums.index(i) )
     nums.push(i)
   end
 end

 # (7)
 board = Array.new(n) {Array.new(n) {"."}}
 n.times {|i| board[i][nums[i] - 1] = "Q"}
 board.inject("") {|str, row| str << row.join(" ") << "\n"}

end

(1 .. 15).each {|n| puts "n=#{n}"; puts n_queens(n); puts}</lang>

Output:

n=1
Q

n=2
no solutions for n=2


n=3
no solutions for n=3


n=4
. Q . .
. . . Q
Q . . .
. . Q .

n=5
. Q . . .
. . . Q .
Q . . . .
. . Q . .
. . . . Q

n=6
. Q . . . .
. . . Q . .
. . . . . Q
Q . . . . .
. . Q . . .
. . . . Q .

n=7
. Q . . . . .
. . . Q . . .
. . . . . Q .
Q . . . . . .
. . Q . . . .
. . . . Q . .
. . . . . . Q

n=8
. Q . . . . . .
. . . Q . . . .
. . . . . Q . .
. . . . . . . Q
. . Q . . . . .
Q . . . . . . .
. . . . . . Q .
. . . . Q . . .

n=9
. . . Q . . . . .
. . . . . Q . . .
. . . . . . . Q .
. Q . . . . . . .
. . . . Q . . . .
. . . . . . Q . .
. . . . . . . . Q
Q . . . . . . . .
. . Q . . . . . .

n=10
. Q . . . . . . . .
. . . Q . . . . . .
. . . . . Q . . . .
. . . . . . . Q . .
. . . . . . . . . Q
Q . . . . . . . . .
. . Q . . . . . . .
. . . . Q . . . . .
. . . . . . Q . . .
. . . . . . . . Q .

n=11
. Q . . . . . . . . .
. . . Q . . . . . . .
. . . . . Q . . . . .
. . . . . . . Q . . .
. . . . . . . . . Q .
Q . . . . . . . . . .
. . Q . . . . . . . .
. . . . Q . . . . . .
. . . . . . Q . . . .
. . . . . . . . Q . .
. . . . . . . . . . Q

n=12
. Q . . . . . . . . . .
. . . Q . . . . . . . .
. . . . . Q . . . . . .
. . . . . . . Q . . . .
. . . . . . . . . Q . .
. . . . . . . . . . . Q
Q . . . . . . . . . . .
. . Q . . . . . . . . .
. . . . Q . . . . . . .
. . . . . . Q . . . . .
. . . . . . . . Q . . .
. . . . . . . . . . Q .

n=13
. Q . . . . . . . . . . .
. . . Q . . . . . . . . .
. . . . . Q . . . . . . .
. . . . . . . Q . . . . .
. . . . . . . . . Q . . .
. . . . . . . . . . . Q .
Q . . . . . . . . . . . .
. . Q . . . . . . . . . .
. . . . Q . . . . . . . .
. . . . . . Q . . . . . .
. . . . . . . . Q . . . .
. . . . . . . . . . Q . .
. . . . . . . . . . . . Q

n=14
. Q . . . . . . . . . . . .
. . . Q . . . . . . . . . .
. . . . . Q . . . . . . . .
. . . . . . . Q . . . . . .
. . . . . . . . . Q . . . .
. . . . . . . . . . . Q . .
. . . . . . . . . . . . . Q
. . Q . . . . . . . . . . .
Q . . . . . . . . . . . . .
. . . . . . Q . . . . . . .
. . . . . . . . Q . . . . .
. . . . . . . . . . Q . . .
. . . . . . . . . . . . Q .
. . . . Q . . . . . . . . .

n=15
. . . Q . . . . . . . . . . .
. . . . . Q . . . . . . . . .
. . . . . . . Q . . . . . . .
. . . . . . . . . Q . . . . .
. . . . . . . . . . . Q . . .
. . . . . . . . . . . . . Q .
. Q . . . . . . . . . . . . .
. . . . Q . . . . . . . . . .
. . . . . . Q . . . . . . . .
. . . . . . . . Q . . . . . .
. . . . . . . . . . Q . . . .
. . . . . . . . . . . . Q . .
. . . . . . . . . . . . . . Q
Q . . . . . . . . . . . . . .
. . Q . . . . . . . . . . . .

Tcl

This solution is based on the C version on wikipedia. By default it solves the 8-queen case; to solve for any other number, pass N as an extra argument on the script's command line (see the example for the N=6 case, which has anomalously few solutions).

Works with: Tcl version 8.5

<lang tcl>package require Tcl 8.5

proc unsafe {y} {

   global b
   set x [lindex $b $y]
   for {set i 1} {$i <= $y} {incr i} {

set t [lindex $b [expr {$y - $i}]] if {$t==$x || $t==$x-$i || $t==$x+$i} { return 1 }

   }
   return 0

}

proc putboard {} {

   global b s N
   puts "\n\nSolution #[incr s]"
   for {set y 0} {$y < $N} {incr y} {

for {set x 0} {$x < $N} {incr x} { puts -nonewline [expr {[lindex $b $y] == $x ? "|Q" : "|_"}] } puts "|"

   }

}

proc main {n} {

   global b N
   set N $n
   set b [lrepeat $N 0]
   set y 0
   lset b 0 -1
   while {$y >= 0} {

lset b $y [expr {[lindex $b $y] + 1}] while {[lindex $b $y] < $N && [unsafe $y]} { lset b $y [expr {[lindex $b $y] + 1}] } if {[lindex $b $y] >= $N} { incr y -1 } elseif {$y < $N-1} { lset b [incr y] -1; } else { putboard }

   }

}

main [expr {$argc ? int(0+[lindex $argv 0]) : 8}]</lang> Sample output:

$ tclsh8.5 8queens.tcl 6

Solution #1
|_|Q|_|_|_|_|
|_|_|_|Q|_|_|
|_|_|_|_|_|Q|
|Q|_|_|_|_|_|
|_|_|Q|_|_|_|
|_|_|_|_|Q|_|


Solution #2
|_|_|Q|_|_|_|
|_|_|_|_|_|Q|
|_|Q|_|_|_|_|
|_|_|_|_|Q|_|
|Q|_|_|_|_|_|
|_|_|_|Q|_|_|


Solution #3
|_|_|_|Q|_|_|
|Q|_|_|_|_|_|
|_|_|_|_|Q|_|
|_|Q|_|_|_|_|
|_|_|_|_|_|Q|
|_|_|Q|_|_|_|


Solution #4
|_|_|_|_|Q|_|
|_|_|Q|_|_|_|
|Q|_|_|_|_|_|
|_|_|_|_|_|Q|
|_|_|_|Q|_|_|
|_|Q|_|_|_|_|