%
% bigdom.m
%
% Big Domino Code
%
% usage:  pay = bigdom(m,n,v)
%
%    where m and n give size of board and
%    v = 1 if one wants to view optimal strategies
%    v = 0 if one only wants payoff
%

function pay = bigdom(m,n,v)

rdim = 2*m*n-m-n;
cdim = m*n;
G = ones(rdim,cdim);

for i=1:m,
for j=1:n-1,
    r = (i-1)*(n-1) + j;
    G(r,[r+i-1 r+i]) = -1;
end 
end

R = r;

for i=1:m-1,
for j=1:n,
    r = R + (i-1)*n + j;
    G(r,[r-R r-R+n]) = -1;
end
end

if v==1
  figure(1)
  spy(G-1)
end

% solve the row linprog for x

f = [zeros(1,rdim) -1]';
A = [-G' ones(cdim,1)];
b = zeros(cdim,1);
Aeq = [ones(1,rdim) 0];
beq = 1;
LB = [zeros(1,rdim) -inf]';
UB = [ones(1,rdim) inf];

x = linprog(f,A,b,Aeq,beq,LB,UB)
pay = x(end);

if v==0
   return
end

% solve the column linprog for y

f = [zeros(1,cdim) 1]';
A = [G -ones(rdim,1)];
b = zeros(rdim,1);
Aeq = [ones(1,cdim) 0];
beq = 1;
LB = [zeros(1,cdim) -inf]';
UB = [ones(1,cdim) inf];

y = linprog(f,A,b,Aeq,beq,LB,UB)

figure(2)

subplot(1,2,1)		% plot optimal domino strategy

for i=1:m		% horizontal dominoes
for j=1:n-1
    xp = [j-.4 j+.4 j+.4 j-.4];
    yp = [m-(i-1)-1/3 m-(i-1)-1/3 m-(i-1)-2/3 m-(i-1)-2/3];
    patch(xp,yp,x((i-1)*(n-1)+j))
end
end

R = m*(n-1);

for i=1:m-1  		% vertical dominoes
for j=1:n
    xp = [(j-1)+1/3 (j-1)+2/3 (j-1)+2/3 (j-1)+1/3];
    yp = [m-i+.4 m-i+.4 m-i-.4 m-i-.4];
    patch(xp,yp,x(R+(i-1)*n+j))
end
end

axis equal
axis([0 n 0 m])
grid
title('Optimal Domino Strategy','fontsize',16)
colorbar

subplot(1,2,2)		% plot optimal square strategy
for i=1:m
for j=1:n
    patch([j-1 j j j-1],[m-i m-i m-(i-1) m-(i-1)],y((i-1)*n+j))
end
end
axis equal
axis([0 n 0 m])
title('Optimal Square Strategy','fontsize',16)
colorbar