Debian Codegraph @

tests/spec/unit/regression/bug335.mzn

raw
1 /***
2 !Test
3 solvers: [gecode]
4 expected:
5 - !Result
6 solution: !Solution
7 sokPosns: [14, 13, 8, 7, 8, 9, 4, 5, 10, 1, 1, 1]
8 stime: 9
9 ***/
10
11 % Regression test for bug #335.
12 % Previous versions of CPX found this model to be unsatisfiable.
13 % A slightly later version found a solution but it was not optimal
14 % (stime = 11, rather than the optimal stime = 9.)
15
16 int: w; % width of board
17 int: n; % board positions 1, ..., w, w+1, ...., 2w, ...,
18 constraint assert(n mod w == 0, "board must be rectangular");
19 set of int: POS = 1..n;
20 int: stps; % max steps in solution
21 set of int: STEPS = 1..stps;
22
23 int: nw; % number of walls
24 set of int: WALLS = 1..nw;
25 array[WALLS] of POS: walls; % wall positions
26 int: nc; % number of crates + goals
27 set of int: CRATES = 1..nc;
28 set of POS: goals; % goal positions;
29 array[CRATES] of POS: crates; % initial crate positions
30 POS: pInit; % initial sokoban position
31
32 set of int: MOVES = {-w,-1,1,w}; % possible moves
33
34 include "alldifferent.mzn";
35
36 array[STEPS] of var POS: sokPosn; % sokoban position
37 array[STEPS] of var MOVES: move; % sokoban position
38 array[STEPS,CRATES] of var POS: cratePosns;
39 var STEPS: stime :: add_to_output; % time of solution
40
41
42 %% initial positions
43 constraint sokPosn[1] = pInit;
44 constraint forall(c in CRATES)(cratePosns[1,c] = crates[c]);
45
46 %% no overlap of crates, walls and sokoban
47 constraint forall(s in STEPS)(
48 alldifferent(walls ++ [sokPosn[s]] ++ [cratePosns[s,c] | c in CRATES])
49 );
50
51 %% at the end all crates are in a position
52 constraint forall(c in CRATES)(
53 cratePosns[stime,c] in goals
54 );
55
56 % legal move at each step
57 constraint forall(s in 1..stps-1)(
58 sokPosn[s+1] - sokPosn[s] = move[s]
59 );
60
61 % crate pushing
62 constraint forall(s in 1..stps-1, c in CRATES)(
63 cratePosns[s+1,c] = cratePosns[s,c] + bool2int(sokPosn[s+1] == cratePosns[s,c]) * move[s]
64 );
65
66 solve minimize stime;
67
68 % output for test case comparison
69 array[STEPS] of var POS: sokPosns :: add_to_output;
70 constraint forall (s in 1..stime) (sokPosns[s] = sokPosn[s]);
71 constraint forall (s in (stime+1)..stps) (sokPosns[s] = 1); % Just fill the rest with 1 for consistency
72
73 w = 5;
74 n = 15;
75 stps = 12;
76
77 nw = 0;
78 walls = [];
79
80 nc = 2;
81 crates = [7,9];
82 goals = {6,15};
83 pInit = 14;