N-queens problem: Difference between revisions
m (→{{header|Tcl}}: minor correction for readability) |
(add Ruby) |
||
Line 65: | Line 65: | ||
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|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> |
|||
=={{header|Tcl}}== |
=={{header|Tcl}}== |
Revision as of 21:39, 12 September 2009
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>
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|_|_|_|_|