# Difference between revisions of "N-queens problem"

### From CodeCodex

m |
|||

Line 35: | Line 35: | ||

</pre> | </pre> | ||

− | [[Category: | + | [[Category:Objective Caml]] |

## Revision as of 00:07, 6 January 2007

## Description

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

### OCaml

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_board n queens = let a = Array.make_matrix n n '.' in iter (fun (x, y) -> a.(y).(x) Array.iter print_char row; print_newline()) a; print_newline ();; let sols = search (fun qs n -> print_board n qs; n + 1) n [] ps 0;; Printf.printf "%d solutions.\n" sols;;