1
(***********************************************************************)
4
(* A Functional Constraint Library *)
6
(* Nicolas Barnier, Pascal Brisset, LOG, CENA *)
8
(* Copyright 2004 CENA. All rights reserved. This file is distributed *)
9
(* under the terms of the GNU Lesser General Public License. *)
10
(***********************************************************************)
11
(* $Id: magic.ml,v 1.9 2001/06/01 14:13:09 barnier Exp $ *)
16
A magic sequence is a sequence of N values (x0, x1, , xN-1) such
17
that 0 will appear in the sequence x0 times, 1 will appear x1
18
times,..., and N-1 will appear in the sequence xN-1 times. For example,
19
for N=3, the following sequence is a solution: (1, 2, 1, 0). That is,
20
0 is present once, 1 is present twice, 2 is present once, and 3 is not
29
let x = Fd.array n 0 (n-1) in
31
(* Constraint: cardinality constraint with x as variables and cardinals *)
32
let card_vals = Array.mapi (fun i x -> (x, i)) x in
33
Cstr.post (Gcc.cstr ~level:Gcc.Medium x card_vals);
35
(* Redundant constraints *)
36
let vals = Array.init n (fun i -> i) in
37
Cstr.post (Arith.scalprod_fd vals x =~ i2e n);
39
(* Search goal: first fail with min domain size *)
41
Goals.Array.choose_index (fun a1 a2 -> Var.Attr.size a1 < Var.Attr.size a2) in
42
let goal = Goals.Array.forall ~select:min_size Goals.indomain x in
45
if Goals.solve goal then begin
46
Array.iter (fun v -> Printf.printf "%a " Fd.fprint v) x; print_newline ()
49
prerr_endline "No solution";;
52
if Array.length Sys.argv < 2 then prerr_endline "Usage: magic <size>"
53
else magic (int_of_string Sys.argv.(1));;