N-queens problem
Solve the eight queens puzzle. You can extend the problem to solve the puzzle with a board of side NxN.
OCaml
Library: FaCiLe (A Functional Constraint Library)
<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>
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 . . . . . . . . . . . .
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|_|_|_|_|