Solving the LinkedIn Queens Puzzle with PROC OPTMODEL

7 Likes

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.

ChrisHemedinger · ‎02-05-2025

Fun post and cool to see an optimal solution. Now can you do one for Pinpoint? That's the only LinkedIn game I can manage to make time for. 😉

ballardw · ‎02-05-2025

I think there may be some constraints on the "colored regions" that are missing in the description unless the puzzle is supposed to generate some (many) non-solvable puzzles. For example, anything with other than exactly 8 regions can't be solved and it would be easy to arrange regions of size one in column or row making the region constraint non-solvable.

RobPratt · ‎02-05-2025

@ballardw A valid puzzle must have the same number of rows, columns, and colors, but that common number need not be 8.

SAS Communities Library