In this post, we will formulate the LinkedIn's Queens puzzle as an integer programming model and solve it by using PROC OPTMODEL in SAS Optimization. For this fun logic puzzle, the goal is to place queens in a two-dimensional matrix such that:
Each row must contain exactly one queen.
Each column must contain exactly one queen.
Each colored region must contain exactly one queen.
No two queens can be adjacent, including diagonally.
Integer Programming Model
This section shows an integer programming model for solving the Queens puzzle. Note that the model is a feasibility problem where we find a solution that satisfies the set of constraints without optimizing an objective function.
The diagonals constraint (4) can also be written as shown below.
However, this constraint set will generate duplicate constraints. Consider the example below for constraints generated for three different (i,j) elements - (1,1), (1,3), and (2,2). As we can see, constraints (a) and (c) are the same as constraints (e) and (g), where the variables appear in the opposite order. The optimization model will still run with these duplicate constraints, but a best practice is to avoid them. The presolver will automatically eliminate these duplicate constraints during preprocessing.
Input Data
The input data for the model is a two-dimensional square matrix with the numbers in the matrix representing the color identifier for each element in the matrix. The following DATA step contains the input data for an 8x8 matrix:
data Color_Matrix;
input col1-col8;
datalines;
1 1 2 5 5 2 2 8
1 1 2 2 5 2 8 8
2 2 2 2 5 2 8 2
2 3 2 2 2 2 2 2
3 3 3 2 2 6 6 2
2 2 2 2 6 6 2 2
4 2 2 2 2 2 2 2
4 4 4 2 7 7 7 7
;
The following DATA step and PROC SGPLOT statements plot the input two-dimensional square matrix as a heat map.
data Sparse;
set Color_Matrix;
array col[8];
i = _N_;
do j = 1 to 8;
Color = col[j];
output;
end;
run;
/* plot heat map of puzzle */
proc sgplot data=Sparse noborder aspect=1 noautolegend;
heatmapparm y=i x=j colorresponse=Color;
xaxis display=none;
yaxis display=none reverse;
run;
PROC OPTMODEL Code
The first several PROC OPTMODEL statements declare parameters and read the input data:
proc optmodel;
/* read input data */
num dsid = open('Color_Matrix');
num ncol = attrn(dsid,'nvar');
set SIZE = 1..ncol;
set MATRIX = SIZE cross SIZE;
num Color{MATRIX};
read data Color_Matrix into [_N_]
{j in SIZE} <Color[_N_,j] = col('col'||j)>;
set COLORS = setof {<i,j> in MATRIX} Color[i,j];
The next few statements declare the decision variables and the constraints:
/* x[i,j] = 1 if a queen appears in cell (i,j); 0 otherwise */
var x{MATRIX} BINARY;
/* Row constraint */
con con1 {i in SIZE}:
sum {j in SIZE} x[i,j] = 1;
/* Column constraint */
con con2 {i in SIZE}:
sum {j in SIZE} x[j,i] = 1;
/* Color constraint */
con con3 {c in COLORS}:
sum{<i,j> in MATRIX: Color[i,j]=c} x[i,j] = 1;
/* Diagonals constraint */
con con4 {<i,j> in MATRIX, j1 in {j-1,j+1}: <i+1,j1> in MATRIX}:
x[i,j] + x[i+1,j1] <= 1;
PROC OPTMODEL also offers an alternative approach that uses indicator constraints to write constraint (4). The constraint below shows the use of indicator constraints to enforce the diagonal constraints.
/* Diagonals constraints using indicator constraints */
con con4 {<i,j> in MATRIX}:
x[i,j] = 1 implies sum {i1 in {i-1,i+1} inter SIZE, j1 in {j-1,j+1} inter SIZE} x[i1,j1] = 0;
The statements below call the solver, print the decision variables, and create an output data set of the resulting solution. Note that because we want to solve a feasibility problem, there is no need to define an objective function. So, we call the solver with the NOOBJ option.
/* call MILP solver with no objective */
solve noobj;
/* print solution */
print x;
/* create output data set */
create data Queens_Output from [i j]=MATRIX Color x/format=1.0 q=(if x[i,j] > 0.5 then 'Q' else '');
The chart below shows the solution summary of the instance:
Plotting the Solution
The following statements plot the solution as a heat map with a '1' in the image to denote that a queen is placed in that cell and a '0' otherwise.
proc sgplot data=Queens_Output noborder aspect=1 noautolegend;
heatmapparm y=i x=j colorresponse=Color;
text y=i x=j text=x;
xaxis display=none;
yaxis display=none reverse;
run;
The following statements plot the solution as a heat map with a 'Q' in the image to denote that a queen is placed in that cell and an empty string otherwise.
proc sgplot data=Queens_Output noborder aspect=1 noautolegend;
heatmapparm y=i x=j colorresponse=Color;
text y=i x=j text=q;
xaxis display=none;
yaxis display=none reverse;
run;
Conclusion
This post illustrates the usage of PROC OPTMODEL in modeling and solving the LinkedIn's Queens puzzle.
... View more
