N-queens problem
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.
Clojure
This produces all solutions by essentially a backtracking algorithm. The heart is the extends? function, which takes a partial solution for the first k<size columns and sees if the solution can be extended by adding a queen at row n of column k+1. The extend function takes a list of all partial solutions for k columns and produces a list of all partial solutions for k+1 columns. The final list solutions is calculated by starting with the list of 0-column solutions (obviously this is the list [ [] ], and iterates extend for size times. <lang clojure> (def size 8)
(defn extends? [v n]
(let [k (count v)]
(not-any? true?
(for [i (range k) :let [vi (v i)]]
(or
(= vi n) ;check for shared row
(= (- k i) (Math/abs (- n vi)))))))) ;check for shared diagonal
(defn extend [vs]
(for [v vs
n (range 1 (inc size)) :when (extends? v n)]
(conj v n)))
(def solutions
(nth (iterate extend [[]]) size))
(doseq [s solutions]
(println s))
(println (count solutions) "solutions") </lang>
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
<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
<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
<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):
solutions = [[]]
for row in range(n):
solutions = [solution+[i+1]
for i in range(BOARD_SIZE)
for solution in solutions
if not under_attack(i+1, solution)]
return solutions
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
- puzzle).
- 2. Write a list of the even numbers from 2 to n in order.
- 3. If the remainder is 3 or 9, move 2 to the end of the list.
- 4. Append the odd numbers from 1 to n in order, but, if the remainder is 8,
- switch pairs (i.e. 3, 1, 7, 5, 11, 9, …).
- 5. If the remainder is 2, switch the places of 1 and 3, then move 5 to the
- end of the list.
- 6. If the remainder is 3 or 9, move 1 and 3 to the end of the list.
- 7. Place the first-column queen in the row with the first number in the
- list, place the second-column queen in the row with the second number in
- 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 . . . . . . . . . . . .
Scala
The algorithm below is lazy. It returns an iterator, and each solution is computed as you ask for the next element of the iterator. If you ask for one element, it will only compute one solution.
The test for legal moves is a bit redundant, as the algorithm can never generate two positions in the same row.
<lang scala>case class Pos(row: Int, column: Int) {
def sameRow(p: Pos) = row == p.row def sameColumn(p: Pos) = column == p.column def sameDiag(p: Pos) = (p.column - column).abs == (p.row - row).abs def illegal(p: Pos) = sameRow(p) || sameColumn(p) || sameDiag(p) def legal(p: Pos) = !illegal(p)
}
def rowSet(size: Int, row: Int) = Iterator.tabulate(size)(column => Pos(row, column))
def expand(solutions: Iterator[List[Pos]], size: Int, row: Int) =
for {
solution <- solutions
pos <- rowSet(size, row)
if solution forall (_ legal pos)
} yield pos :: solution
def seed(size: Int) = rowSet(size, 0) map (sol => List(sol))
def solve(size: Int) = (1 until size).foldLeft(seed(size)) (expand(_, size, _))</lang>
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).
<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|_|_|_|_|
Ursala
This is invoked as a command line application by queens -n, where n is a number greater than 3. Multiple solutions may be reported but reflections and rotations thereof are omitted. <lang Ursala>
- import std
- import nat
remove_reflections = ^D(length@ht,~&); ~&K2hlPS+ * ^lrNCCs/~&r difference*D remove_rotations = ~&K2hlrS2S+ * num; ~&srlXSsPNCCs
- executable <'par',>
- optimize+
queens =
%np+~command.options.&h.keyword.&iNC; -+
~&iNC+ file$[contents: --<>+ mat` *+ %nP*=*],
remove_rotations+ remove_reflections+ ~&rSSs+ nleq-<&l*rFlhthPXPSPS,
~&i&& ~&lNrNCXX; ~&rr->rl ^/~&l ~&lrrhrSiF4E?/~&rrlPlCrtPX @r ^|/~& ^|T\~& -+
-<&l^|*DlrTS/~& ~&iiDlSzyCK9hlPNNXXtCS,
^jrX/~& @rZK20lrpblPOlrEkPK13lhPK2 ~&i&& nleq$-&lh+-,
^/~&NNXS+iota -<&l+ ~&plll2llr2lrPrNCCCCNXS*=irSxPSp+ ^H/block iota; *iiK0 ^/~& sum+-
</lang> The output shows one solution on each line. A solution is reported as a sequence of numbers with the -th number being the index of the occupied row in the -th column.
$ queens -4 2 3 0 1 $ queens -5 0 2 1 3 4 2 4 3 0 1 1 3 2 4 0 $ queens 6 4 3 0 2 1 5