N-queens problem: Difference between revisions
(Add J) |
(→{{header|Python}}: Copied Raymond Hettingers solution from Activestate Code (Original under compatable MIT license).) |
||
Line 108: | Line 108: | ||
Gc.set ({(Gc.get ()) with Gc.space_overhead = 500}); (* May help except with an underRAMed system *) |
Gc.set ({(Gc.get ()) with Gc.space_overhead = 500}); (* May help except with an underRAMed system *) |
||
queens (int_of_string Sys.argv.(1));;</lang> |
queens (int_of_string Sys.argv.(1));;</lang> |
||
=={{header|Python}}== |
|||
This solution, originally by [[http://code.activestate.com/recipes/576647/ Raymond Hettinger]] for demonstrating the power of the itertools module. |
|||
<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> |
|||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
Revision as of 09:08, 13 September 2009
Solve the eight queens puzzle. You can extend the problem to solve the puzzle with a board of side NxN.
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>
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>
Python
This solution, originally by [Raymond Hettinger] for demonstrating the power of the itertools module. <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>
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|_|_|_|_|