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" ]; |