# Difference between revisions of "N-queens problem"

### From CodeCodex

m |
(→OCaml) |
||

Line 25: | Line 25: | ||

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

− | let | + | let print qs = |

− | let a = Array. | + | let a = Array.init n (fun _ -> String.make n '.') in |

− | iter (fun (x, y) -> a.(y). | + | List.iter (fun (x, y) -> a.(y).[x] <- 'Q') qs; |

− | + | Array.iter print_endline a;; | |

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

## Revision as of 21:18, 13 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 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_board n qs; n + 1) n [] ps 0;; Printf.printf "%d solutions.\n" sols;;