← Back to branch summary

~ubuntu-branches/ubuntu/hardy/ocaml-doc/hardy

« back to all changes in this revision

Viewing changes to examples/basics/queens_tail.ml

  • Committer: Bazaar Package Importer
  • Author(s): Samuel Mimram
  • Date: 2007-09-08 01:49:22 UTC
  • mfrom: (0.1.3 upstream)
  • Revision ID: james.westby@ubuntu.com-20070908014922-lvihyehz0ndq7suu
Tags: 3.10-1
* New upstream release.
* Removed camlp4 documentation since it is not up-to-date.
* Updated to standards version 3.7.2, no changes needed.
* Updated my email address.

Show diffs side-by-side

added added

removed removed

Lines of Context:
examples/basics/queens_tail.ml
1
 
(***********************************************************************)
2
 
(*                                                                     *)
3
 
(*                           Objective Caml                            *)
4
 
(*                                                                     *)
5
 
(*               Pierre Weis, projet Cristal, INRIA Rocquencourt       *)
6
 
(*                                                                     *)
7
 
(*  Copyright 2001 Institut National de Recherche en Informatique et   *)
8
 
(*  en Automatique.  All rights reserved.  This file is distributed    *)
9
 
(*  only by permission.                                                *)
10
 
(*                                                                     *)
11
 
(***********************************************************************)
12
 
 
13
 
(*                         E I G H T   Q U E E N S
14
 
 
15
 
 The Eight Queens Program tail recursive version.
16
 
 
17
 
*)
18
 
 
19
 
open List;;
20
 
 
21
 
let map f l =
22
 
 let rec loop accu = function
23
 
   | [] -> accu
24
 
   | x :: l -> loop (f x :: accu) l in
25
 
 loop [] l;;
26
 
 
27
 
let rec interval n m =
28
 
 if n > m then [] else n :: interval (n + 1) m;;
29
 
 
30
 
let rev_append l1 l2 =
31
 
  let rec loop accu = function
32
 
    | [] -> accu
33
 
    | h :: t -> loop (h :: accu) t in
34
 
  loop l2 l1;;
35
 
 
36
 
let filter_append p l l0 =
37
 
  let rec loop accu = function
38
 
    | [] -> accu
39
 
    | h :: t -> if p h then loop (h :: accu) t else loop accu t in
40
 
  let rev_res = loop [] l in
41
 
  rev_append rev_res l0;;
42
 
 
43
 
let concmap f l =
44
 
  let rec loop accu = function
45
 
  | [] -> accu
46
 
  | h :: t -> loop (f h accu) t in
47
 
  loop [] l;;
48
 
 
49
 
let rec safe x d  = function
50
 
  | [] -> true
51
 
  | h :: t ->
52
 
     x <> h && x <> h + d && x <> h - d && safe x (d + 1) t;;
53
 
 
54
 
let rec ok = function
55
 
  | [] -> true
56
 
  | h :: t -> safe h 1 t;;
57
 
 
58
 
let find_solutions size =
59
 
 let line = interval 1 size in
60
 
 let rec gen n size =
61
 
   if n = 0 then [[]] else
62
 
   concmap 
63
 
    (fun b -> filter_append ok (map (fun q -> q :: b) line))
64
 
    (gen (n - 1) size) in
65
 
 gen size size;;
66
 
 
67
 
(* 2. Printing results. *)
68
 
 
69
 
let print_solutions size solutions =
70
 
 let sol_num = ref 1 in
71
 
 iter
72
 
   (fun chess ->
73
 
     Printf.printf "\nSolution number %i\n" !sol_num;
74
 
     sol_num := !sol_num + 1;
75
 
     iter
76
 
       (fun line ->
77
 
         let count = ref 1 in
78
 
         while !count <= size do
79
 
           if !count = line then print_string "Q " else print_string "- ";
80
 
           count := !count + 1
81
 
         done;
82
 
         print_newline ())
83
 
       chess)
84
 
   solutions;;
85
 
 
86
 
let print_result size =
87
 
 let solutions = find_solutions size in
88
 
 let sol_num = List.length solutions in
89
 
 Printf.printf "The %i queens problem has %i solutions.\n" size sol_num;
90
 
 print_newline ();
91
 
 let pr = 
92
 
   print_string "Do you want to see the solutions <n/y> ? "; read_line () in
93
 
 if pr = "y" then print_solutions size solutions;;
94
 
 
95
 
(* 3. Main program. *)
96
 
 
97
 
let queens () =
98
 
 let size = 
99
 
   print_string "Chess boards's size ? "; read_int () in
100
 
 print_result size;;
101
 
 
102
 
if !Sys.interactive then () else queens ();;
103