> #light;;

> type Position = int * int;;

type Position = int * int

> let safe p q =

- fst p <> fst q && snd p <> snd q && fst p + snd p <> fst q + snd q && fst p - snd p <> fst q - snd q;;

val safe : int * int -> int * int -> bool

> let all_safe p positions =

- Seq.for_all (safe p) positions;;

val all_safe : int * int -> #seq-> bool

> all_safe (1, 2) [(1, 2)];;

val it : bool = false

> all_safe (1, 2) [(3, 3)];;

val it : bool = true

> let range = [1..8];;

val range : int list

> range;;

val it : int list = [1; 2; 3; 4; 5; 6; 7; 8]

> let queens size =

- let range = [1..size]

- let rec queens' columns answers =

- match columns with

- | [] -> answers

- | column::tail -> queens' tail [for answer in answers for position in [for row in range -> (column, row)] when all_safe position answer -> position::answer]

- queens' range [[]];;

val queens : int -> (int * int) list list

> queens 4;;

val it : (int * int) list list

= [[(4, 3); (3, 1); (2, 4); (1, 2)]; [(4, 2); (3, 4); (2, 1); (1, 3)]]

>

Implemented recursively, it's:

> let queens size =

- let range = [1..size]

- let rec queens' columns =

- match columns with

- | column::tail -> [for answer in (queens' tail) for position in [for row in range -> (column, row)] when all_safe position answer -> position::answer]

- | _ -> [[]]

- queens' range;;

val queens : int -> (int * int) list list

> queens 4

- ;;

val it : (int * int) list list

= [[(1, 3); (2, 1); (3, 4); (4, 2)]; [(1, 2); (2, 4); (3, 1); (4, 3)]]

>

## No comments:

Post a Comment