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.
You have a table and on each row and column you need to have squares coloured with color and squares coloured with color 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 containing the initial conditions has the following components:
The matrix of the final configuration can be defined as a binary matrix (it contains only elements equal to or ; for color , for color ). The condition that has squares of each color on every line and column can be written as
The fact that does not have on its lines or columns three consecutive squares of the same color can be written as
where and is obtained from by shifting all elements position to the right. The inequalities are considered elementwise.
From here you can use YALMIP or any other MILP (mixedinteger 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(p3,1)]; A = binvar(p,p,'full'); F = [sum(A,1)==n, sum(A,2)==n]; for i = 0:p3 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 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 of size , and if the corresponding square is black on the board. The column vector of values corresponding tu lines is and the line vector corresponding to the columns is . Then if the condition is written as
if is not zero and
if is not zero.
Now call your favorite MILP solver and you are done. I managed to solve only games up to using this method. Note that you have only maximum constraints with 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 .
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 ). With minor changes I guess even nonsquare problems can be solved.

January 28, 2017 at 2:52 pmLinear programming #1 – Project Euler 185  Beni Bogoşel's blog