# Model name   : flowfree.mod
# Description  : Flow free puzzle 
# Source       : android app
# Date written : 6/12/2013
# Written by   : Martin Chlond, Lancashire Business School
# Email        : mchlond@uclan.ac.uk 
# note: for 12x12 GLPK had no solution after 60700 seconds - Minisat solved in .8 second.

param m;
param n;

set M := 1..m;
set N := 1..n;

param P{i in M, j in M}, default 0;
param S{i in M,j in M,k in N} binary := if P[i,j] = k then 1 else 0;

var x{i in M,j in M,k in N} binary; 

subject to

# force given cells
fgc{i in M,j in M,k in N}: x[i,j,k] >= S[i,j,k];

# each cell contains a single colour
eccsc{i in M,j in M}: sum{k in N} x[i,j,k] = 1;

# ensure continuous flow for each colour
ecfeca{i in M,j in M,k in N}: sum{p in i-1..i+1:p>=1 and p<=m and p!=i} x[p,j,k]
                             +sum{q in j-1..j+1:q>=1 and q<=m and q!=j} x[i,q,k]
                             +S[i,j,k] >= 2*x[i,j,k]-5*(1-x[i,j,k]);

ecfecb{i in M,j in M,k in N}: sum{p in i-1..i+1:p>=1 and p<=m and p!=i} x[p,j,k]
                             +sum{q in j-1..j+1:q>=1 and q<=m and q!=j} x[i,q,k]
                             +S[i,j,k] <= 2*x[i,j,k]+5*(1-x[i,j,k]);

solve;

# display results
for {i in M} {
  for {j in M} {
    printf sum{k in N} k*x[i,j,k];
    printf " ";
  }
  printf "\n";
}
printf "\n";

data;

param m := 8;
param n := 4;

param P : 1 2 3 4 5 6 7 8 :=
      1   . . . . . . . .
      2   . . . . . . 4 .
      3   . . 1 2 . . . .
      4   . . . 3 1 . . .
      5   . . . . . . . .
      6   . . . . . . . .
      7   . . . . 2 . . 3
      8   . . . . . . . 4;
/*
param m := 12;
param n := 9;

param P : 1 2 3 4 5 6 7 8 9 10 11 12:=
      1   1 . . . . . . . .  .  .  .
      2   2 . . . 4 . . . .  .  4  .
      3   . 3 . . 1 5 6 . .  .  .  .
      4   . . . . . . . . .  8  .  .
      5   . . 7 . 7 . . . .  .  .  8
      6   . . . . . . . . .  .  .  .
      7   . . . . . . . . .  .  .  .
      8   . . . . . . . . .  9  .  .
      9   . . . . . . . . .  .  .  .
      10  . . . . . . . 9 .  .  .  .
      11  . 2 . . . . . . .  6  5  3
      12  . . . . . . . . .  .  .  .;
*/
end;