% meeting point
int: n; % number of rows
set of int: ROW = 1..n;
int: m = n; % number of cols
set of int: COL = 1..m;
% starting positions
int: s; % number of starting positions
set of int: START = 1..s;
set of int: START0 = 0..s;
array[START] of ROW: row;
array[START] of COL: col;
array[START] of int: turn;
int: maxturn = max(turn);
set of int: TURN = 0..maxturn;
set of int: ROWCOL = 1..n*m;
function var ROW: rowof(var ROWCOL:x) =
(x - 1) div m + 1;
function var COL: colof(var ROWCOL:x) =
(x - 1) mod m + 1;
function var ROWCOL: rowcol(var ROW: x, var COL: y) =
(x - 1) * m + y;
function ROW: rowof(ROWCOL:x) =
(x - 1) div m + 1;
function COL: colof(ROWCOL:x) =
(x - 1) mod m + 1;
function ROWCOL: rowcol(int: x, int: y) =
(x - 1) * m + y;
% directions
int: none = 0;
int: north = 1;
int: east = 2;
int: south = 3;
int: west = 4;
set of int: DIRN0 = 0..4;
array[DIRN0] of string: dd = array1d(DIRN0,[" ","v",">","^","<"]);
% which is the next position in the path
array[ROW,COL] of var ROWCOL: next;
% which is the direction of the next position in the path
array[ROW,COL] of var DIRN0: dirn;
% which path are we on or 0 for none
array[ROW,COL] of var START0: path;
% how many turns remaining
array[ROW,COL] of var TURN: trem;
% meeting point of paths
var ROWCOL: meetp;
var ROW: meetr = rowof(meetp);
var COL: meetc = colof(meetp);
% start positions are on their path and have given turns remaining
constraint forall(k in START)
(path[row[k],col[k]] = k /\
trem[row[k],col[k]] = turn[k]);
% the next position in the path is on the same path or is the meet point
constraint forall(i in ROW, j in COL)
(path[rowof(next[i,j]),colof(next[i,j])] = path[i,j] \/
next[i,j] = meetp);
% if the dirn is none then the next path is zero and turns remaining 0
constraint forall(i in ROW, j in COL)
(dirn[i,j] = none -> (trem[i,j] = 0 /\ path[i,j] = 0));
% if two positions have the same next position its the meet point
constraint forall(i1,i2 in ROW, j1,j2 in COL where i1 != i2 \/ j1 != j2)
(next[i1,j1] = next[i2,j2] -> next[i1,j1] = meetp);
% the dirn and the next information agree dirn = none implied next is self
constraint forall(i in ROW, j in COL)
((dirn[i,j] = north -> next[i,j] = rowcol(i+1,j)) /\
(dirn[i,j] = east -> next[i,j] = rowcol(i,j+1)) /\
(dirn[i,j] = south -> next[i,j] = rowcol(i-1,j)) /\
(dirn[i,j] = west -> next[i,j] = rowcol(i,j-1)) /\
(dirn[i,j] = none -> next[i,j] = rowcol(i,j)));
% redundant constraint the next position is at most 1 manhattan distance away
constraint forall(i in ROW, j in COL)
(abs(rowof(next[i,j]) - i) + abs(colof(next[i,j]) - j) <= 1);
% if the dirns of this position and its next agree then
% there is one less turn remaining at the next
% except if the next is the meet when there must be 0 turns remaining here
constraint forall(i in ROW, j in COL)
(trem[rowof(next[i,j]),colof(next[i,j])] =
if next[i,j] = meetp then 0 else
trem[i,j] - (dirn[i,j] != dirn[rowof(next[i,j]),colof(next[i,j])])
endif
);
% positions that go to the meet point must have no bends remaining
constraint forall(i in ROW, j in COL)
(next[i,j] = meetp -> trem[i,j] = 0);
% no position has as next one of the starting point
constraint forall(i in ROW, j in COL, k in START)
(next[i,j] != rowcol(row[k],col[k]));
% the meet point is not on a path, has no direction, no turns remaining, and itself as next
constraint path[meetr,meetc] = 0 /\ dirn[meetr,meetc] = none /\
next[meetr,meetc] = meetp /\ trem[meetr,meetc] = 0;
solve satisfy;
output [ show(path[i,j]) ++ if j = m then "\n" else "" endif | i in ROW, j in COL ]
++ ["\n"] ++
[ dd[fix(dirn[i,j])] ++ if j = m then "\n" else "" endif | i in ROW, j in COL ]
++ ["\n"] ++
[ "link(\(j),\(i),\(colof(fix(next[i,j]))),\(rowof(fix(next[i,j])))).\n" |
i in COL, j in COL where fix(next[i,j] != rowcol(i,j)) ]
;