Home > Algebra, Linear Algebra, Linear programming, Numerical Analysis, Optimization > Two more mind games solved using Matlab

Two more mind games solved using Matlab


After doing this, solving the Sudoku puzzle with Matlab, I wondered what else can we do using integer programming? Many of the mind games you can find on the Internet can be modelled as matrix problems with linear constraints. I will present two of them, as well as their solutions, below. The game ideas are taken from www.brainbashers.com. Note that in order to use the pieces of code I wrote you need to install the YALMIP toolbox.

1. Three in a row

You have a {2n \times 2n} table {(n \geq 3)} and on each row and column you need to have {n} squares coloured with color {A} and {n} squares coloured with color {B} such that no three squares taken vertically or horizontally have the same color. In the begining you are given the colors of some of the square such that it leads to a unique solution satisfying the given properties. The goal is to find the colors corresponding to each small square starting from the ones given such that the end configuration satisfies the given properties.

The problem can be modelled as a matrix integer problem in the following way: the matrix {S} containing the initial conditions has the following components:

\displaystyle S(i,j) = \begin{cases} 0 & \text{ if we don't know the color}\\ 1 & \text{ if the square has color }A\\ 2 & \text{ if the square has color }B \end{cases}.

The {2n\times 2n} matrix {A} of the final configuration can be defined as a binary matrix (it contains only elements equal to {0} or {1}; {0} for color {A}, {1} for color {B}). The condition that {A} has {n} squares of each color on every line and column can be written as

\displaystyle \sum_{i=1}^{2n} A(i,j)=n, \sum_{j=1}^{2n} A(i,j)=n.

The fact that {A} does not have on its lines or columns three consecutive squares of the same color can be written as

\displaystyle 1\leq A*vec_i \leq 2 \text{ and } 1\leq A^t*vec_i \leq 2

where {vec_0 = [1,1,1,0...,0]^T} and {vec_i} is obtained from {vec_0} by shifting all elements {i} position to the right. The inequalities are considered elementwise.

From here you can use YALMIP or any other MILP (mixed-integer linear programming) solver to get the result. Here’s the code:


function three_in_a_row
S = [2 0 0 2 0 0 0 0 0 0 0 0 0 2;...
0 1 0 0 0 0 0 0 2 0 1 1 0 0;...
0 0 0 2 2 0 0 0 0 0 2 0 0 0;...
2 0 0 0 0 2 0 1 0 0 0 0 1 0;...
0 0 0 2 1 0 0 0 0 0 0 0 1 0;...
1 0 0 0 1 0 0 2 0 0 1 0 0 0;...
1 0 0 0 0 2 0 0 0 0 2 0 0 2;...
0 1 0 2 0 2 0 2 0 0 0 0 0 0;...
1 0 0 0 0 0 0 0 0 0 2 0 1 0;...
1 0 2 0 0 0 0 2 0 2 0 0 0 0;...
0 0 0 1 0 0 0 0 1 0 2 0 0 0;...
2 0 0 1 0 0 0 0 0 0 0 0 0 0;...
0 1 0 0 0 0 0 0 2 1 0 0 2 2;...
0 0 0 0 0 0 0 1 0 0 0 2 1 0]

p = size(S,1);
n = p/2;
vec = [ones(3,1); zeros(p-3,1)];
A = binvar(p,p,'full');
F = [sum(A,1)==n, sum(A,2)==n];
for i = 0:p-3
   F = [F, A*circshift(vec,i)<=2, A*circshift(vec,i)>=1, A'*circshift(vec,i)<=2, A'*circshift(vec,i)>=1];
end

for i=1:p
   for j=1:p
      if S(i,j)==2
         F = [F; A(i,j)==1];
      end
      if S(i,j)==1
         F = [F; A(i,j)==0];
      end
   end
end
sol = solvesdp(F);
Z =double(A)+1

2. kakurasu

You have a {n \times n} board (let’s say it is white in the beginning). You have some numbers corresponding to the columns and some values corresponding to the lines (it is not necessary that all lines or columns have a corresponding number). The idea is to place black unit squares on the board so that the numbers corresponding to a line or column is the sum of the positions on that line/column of the black squares, starting from left/up.

The modelling of the problem is simple: the desired configuration is a binary matrix {A} of size {n \times n}, and {A(i,j)1} if the corresponding square {(i,j)} is black on the board. The column vector of values corresponding tu lines is {v} and the line vector corresponding to the columns is {h}. Then if {v=(1,2,3,..,n)} the condition is written as

\displaystyle A(i,:)*vec^T = v(i)

if {v(i)} is not zero and

\displaystyle vec*A(:,j) = h(i)

if {h(i)} is not zero.

Now call your favorite MILP solver and you are done. I managed to solve only games up to {n=6} using this method. Note that you have only maximum {2n} constraints with {n^2} unknowns. Even if the matrix is binary and the solution unique, it still is a complicated thing, and may need some additional good rules to accelerate the finding process for higher {n}.


function kakurasu

vtotals = [21;5;16;1;17;3];
btotals = [5;0;0;0;9;0]';

p = length(vtotals);
A = binvar(p,p,'full');
vech = 1:p;
vecv = vech(:);
s = sum(vech)
F = [];

for i=1:p
   if vtotals(i)
      F = [F, A(i,:)*vecv == vtotals(i)];
   end
   if btotals(i)
      F = [F, vech*A(:,i) == btotals(i)];
   end
end
sol = solvesdp(F)
double(A)

Update: Seems like adding the command

opts = sdpsettings('solver','bintprog');

and then calling

 F = solvesdp(F,[],opts)

makes it possible to solve larger kakurasu problems (I’ve tried up to 8 \times 8). With minor changes I guess even non-square problems can be solved.

Advertisements
  1. No comments yet.
  1. January 28, 2017 at 2:52 pm

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: