Download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
%
% MiniZinc model for the water buckets problem
%
% Model created by Hakan Kjellerstrand, hakank@gmail.com
% See also my MiniZinc page: http://www.hakank.org/minizinc
 
%
% Solution should be
%   x: [1, 9, 10, 11, 12, 13, 14, 15]
%   8,0,0 -> 3,5,0
%   3,5,0 -> 3,2,3
%   3,2,3 -> 6,2,0
%   6,2,0 -> 6,0,2
%   6,0,2 -> 1,5,2
%   1,5,2 -> 1,4,3
%   1,4,3 -> 4,4,0
%
include "globals.mzn";
 
int: n_states = 15;
int: input_max = 15;
int: initial_state = 1;
set of int: accepting_states = {15};
 
 
% distance
array[1..n_states, 1..n_states] of 0..input_max: transition_fn =
array2d(1..n_states, 1..n_states,
[%1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
  0, 2, 0, 0, 0, 0, 0, 0, 9, 0, 0, 0, 0, 0, 0, % 1
  0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, % 2
  0, 0, 0, 4, 0, 0, 0, 0, 9, 0, 0, 0, 0, 0, 0, % 3
  0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, % 4
  0, 0, 0, 0, 0, 6, 0, 0, 9, 0, 0, 0, 0, 0, 0, % 5
  0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0, 0, 0, 0, % 6
  0, 0, 0, 0, 0, 0, 0, 8, 9, 0, 0, 0, 0, 0, 0, % 7
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,15, % 8
  0, 0, 0, 0, 0, 0, 0, 0, 0,10, 0, 0, 0, 0, 0, % 9
  0, 2, 0, 0, 0, 0, 0, 0, 0, 0,11, 0, 0, 0, 0, %10
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,12, 0, 0, 0, %11
  0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,13, 0, 0, %12
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,14, 0, %13
  0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,15, %14
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,15, %15
]);
 
 
array[1..n_states] of string:  nodes = [
        "8,0,0", % 1 start
        "5,0,3", % 2
        "5,3,0", % 3
        "2,3,3", % 4
        "2,5,1", % 5
        "7,0,1", % 6
        "7,1,0", % 7
        "4,1,3", % 8
        "3,5,0", % 9
        "3,2,3", % 10
        "6,2,0", % 11
        "6,0,2", % 12
        "1,5,2", % 13
        "1,4,3", % 14
        "4,4,0"  % 15 goal
        ];
 
 
array[1..input_max] of var 0..input_max: x;
var 0..input_max: cost;
 
% solve satisfy;
solve minimize cost;
 
constraint
regular(x, n_states, input_max, transition_fn,
        initial_state, accepting_states)
;
 
constraint
   cost = 2+sum([bool2int(x[i-1] != x[i] ) | i in 2..input_max])
;
 
output
["cost: " ++ show(cost) ++ "\n"] ++
[show(initial_state) ++ " "] ++
[
  if fix(x[i]) < input_max then show(x[i]) ++ " " else " " endif
  | i in 1..input_max where fix(x[i]) < input_max
] ++
[show(input_max) ++ "\n"] ++
["\n\n"] ++
 
[show(nodes[initial_state]) ++ "\n"] ++
[
  if fix(x[i]) < input_max then show(nodes[fix(x[i])]) ++ "\n" else " " endif
  | i in 1..input_max where fix(x[i]) < input_max
] ++
[show(nodes[input_max]) ++ "\n"] ++
["\n"];