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>
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 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|_|_|_|_|