N-queens problem

From CodeCodex

Description[edit]

Find all ways to position n queens on an n by n chessboard such that no queen attacks any other, print the boards and the number of solutions found for n=8.

Note that the programs must print the boards (there are algorithms that count the number of solutions without actually finding them) and must work for general n.

Implementations[edit]

Erlang[edit]

-export([queen/1]).

queen(N) ->
    IJ = [{I, J} || I <- lists:seq(1, N), J <- lists:seq(1, N)],
    lists:foreach(fun({I, J}) -> put_data(I, J, true) end, IJ),
    solve(N, 1, [], 0).

solve(N, J, Board, Count) when N < J ->
    print(N, Board),
    Count + 1;
solve(N, J, Board, Count) ->
    F = fun(I, Cnt) ->
            case get_data(I, J) of
                true  ->
                    put_data(I, J, false),
                    Cnt2 = solve(N, J+1, [I|Board], Cnt),
                    put_data(I, J, true),
                    Cnt2;
                false -> Cnt
            end
        end,
    lists:foldl(F, Count, lists:seq(1, N)).

put_data(I, J, Bool) ->
    put({row, I  }, Bool),
    put({add, I+J}, Bool),
    put({sub, I-J}, Bool).

get_data(I, J) ->
    get({row, I}) andalso get({add, I+J}) andalso get({sub, I-J}).

print(N, Board) ->
    Frame = "+-" ++ string:copies("--", N) ++ "+",
    io:format("~s~n", [Frame]),
    lists:foreach(fun(I) -> print_line(N, I) end, Board),
    io:format("~s~n", [Frame]).

print_line(N, I) ->
    F = fun(X, S) when X == I -> "Q " ++ S;
           (_, S)             -> ". " ++ S
        end,
    Line = lists:foldl(F, "", lists:seq(1, N)),
    io:format("| ~s|~n", [Line]).

F#[edit]

Much like the OCaml but uses list comprehensions and avoids string mutation:

let n = 8;;

open List

let rec safe (x1, y1) (x2, y2) =
  x1 <> x2 && y1 <> y2 && x2 - x1 <> y2 - y1 && x1 - y2 <> x2 - y1

let rec search f n nqs qs ps accu = match ps with
  | [] -> if nqs = n then f qs accu else accu
  | q::ps -> search f n (nqs+1) (q::qs) (filter (safe q) ps) (search f n nqs qs ps accu)

let ps = [for i in 1 .. n for j in 1 .. n -> i, j]

let print qs =
  let a = Array.init n (fun _ -> String.make n '.') in
  List.iter (fun (x, y) -> a.(y).[x] <- 'Q') qs;
  Array.iter print_endline a;;

let sols = search (fun qs n -> print n qs; n + 1) n 0 [] ps 0;;

do Printf.printf "%d solutions for n=%d.\n" sols n;;

OCaml[edit]

This implementation starts with a list of all board positions and recursively searches, filtering out unsafe board positions:

open List;;

let rec safe (x1, y1) (x2, y2) =
  x1 <> x2 && y1 <> y2 && x2 - x1 <> y2 - y1 && x1 - y2 <> x2 - y1;;

let rec search f n qs ps accu = match ps with
  | [] -> if length qs = n then f qs accu else accu
  | q::ps -> search f n (q::qs) (filter (safe q) ps) (search f n qs ps accu);;

let n = 8;;

let rec init n f = if n=0 then [] else init (n-1) f @ [f n];;

let ps = flatten (init n (fun i -> init n (fun j -> i, j)));;

let print qs =
  let a = Array.init n (fun _ -> String.make n '.') in
  List.iter (fun (x, y) -> a.(y).[x] <- 'Q') qs;
  Array.iter print_endline a;;

let sols = search (fun qs n -> print n qs; n + 1) n [] ps 0;;

Printf.printf "%d solutions.\n" sols;;

Ruby[edit]

class Queen
  def initialize(num = 8)
    @size  = num
    @board = Array.new(num)
    @row   = Array.new(num)
    @add   = Array.new(2 * num - 1)
    @sub   = Array.new(2 * num - 1)
    @line  = "+-" + "--" * num + "+"
    @count = 0
  end
  
  def print_out
    puts @line
    @board.each do |i|
      print "| "
      @size.times {|j| print j==i ? "Q " : ". "}
      puts "|"
    end
    puts @line
  end
  
  def solve(y = 0)
    if y == @size
      print_out
      @count += 1
    else
      @size.times do |x|
        unless @row[x] || @add[x+y] || @sub[x-y]
          @row[x] = @add[x+y] = @sub[x-y] = true
          @board[y] = x
          solve(y + 1)
          @row[x] = @add[x+y] = @sub[x-y] = nil
        end
      end
    end
    @count
  end
end

pzl = Queen.new(8)
puts pzl.solve