Problem
This is another board game similar to the problem described in snake. Given 50 pellets each colored with one of five colors. 10 pellets at a time have the same color. The problem is to place all pellets on a board consisting of 50 notches layouted on a 10 × 5 grid points in such a way that all pellets with the same color must have at least one neighbor and build a sequence without braching. Two pellets are neighbors if they are immediate horizontal or vertical neighbors on the grid. The game begins after 5 pellets – all of different colors – have been placed on arbitary grid points (notches).
A (trivial) solution is given in Figure 1 (left part) if the 5 initial pellets have been placed in positions {1, 11, 21, 31, 41}: all pellets with the same color are placed verically in one line. Try to find a solution when the 5 initial pellets are placed in positions {44, 23, 28, 13, 15}, as in Figure 1 (right part). (The initial 5 pellets are drawn a little bit larger.) This problem and the mathematical formulation is from [2]. This board game seemed to exist a long time ago. The author wrote that he was inspired by the real board game found in a shelf at his grandmotherinlaw, Meta Trumpp.
Modeling Steps
The set of pellets – corresponding to the set of grid points – is defined as a set I = {1,…, 50} (since the grid has 10 × 5 points) with the indexes i,j ∈ I. There are 5 colors introduced as a set H = {1,…, 5} with index h ∈ H. Let J_{h} = {44, 23, 28, 13, 15} be the five grid points where the 5 initial pellets are placed.
The position in the sequence of 10 pellets is defined as an (ordered) set K = {1,…, 10}. The positions of pellet i has position (x_{i},y_{i}) on the grid with
Two pellets i and j are neighbors if e_{i,j} is true, where
In the code, the different parameters n, m, and p generalize the game. So it is easy to play variants of the game: varying the size, the grid, or the number of colors.

A binary variable z_{h,i,k} is introduced where z_{h,i,k} = 1 if and only if at the grid point i a pellet with color h in position k in the sequence is placed.

Fixing the 5 starting pellets which are placed in position 1 of a sequence:

At each grid point only one pellet can be placed:

Each pellet with color h and at position k must be set:

Each pellet at positions 2 to 9 must have a predecessor and a follower:

If no “circles” are allowed, another constraint is needed in addition: (a circle is a set of pellets with the same color that form a rectangle)
This constraint limits the neighbors of a pellet with the same color to 2, that is, if a pellet at grid location i has a given color h then only 2 pellets with the same color can be in the neighborhood, otherwise 4 neighbors (with diffent colors) are possible.

We are looking for a feasible solution
model snake1 "Snakes Problem";
set i,j "set of notches";
e{i,j} "i and j are neighours";
h "set of snakes (colors)";
k "Length of snakes (ordered set of position)";
parameter J{h} "Starting positions (heads of snake)";
binary variable z{h,i,k};
constraint
A{h}: z[h,J,1] = 1;
B{i}: sum{h,k} z = 1;
C{h,k}: sum{i} z = 1;
D{h,i,k1<k<#k}: 2*z[h,i,k] <=
sum{je[i,j]} z[h,j,k1] + sum{je[i,j]} z[h,j,k+1];
D0{h,i,k}: 42*z[h,i,k] >= sum{j,k1 in ke[i,j]} z[h,j,k1];
solve;
end
Solution
A solution with and without circles is given in Figure 2.
Questions

Try a solution with J_{h} = {44, 23, 28, 13, 14}. What is your conclusion?

Formulate the constraint D as a logical constraint.

How can we find other initial positions to start the game that have solutions?

Extend the problem to a grid of 15×6 with various starting settings and m = 6. Run the problem without the contraint D0 (circles are allowed). Compare the solution time once with the original constraints D and once with the logical constraints. What do you realize?
Answers

With this setting only solutions with circles exist.

The constraint says: “if a pellet is set at position k for all intermediate pellets (pellets at position k=2 to 9) then at least one predecessor and at least one follower must exist”. Formally:
LPL translates this into two constraints as follows:
The LPL formulation of this constraint is:
D{h,i,k1<k<#k}: z[h,i,k] >
or{je[i,j]} z[h,j,k1] and or{je[i,j]} z[h,j,k+1]; 
Choose J_{h} randomly in the interval [10(h – 1) + 1, 10h]. The change is about 90% that a feasible solution with circles (without constraint D0) results. Without circles (including constraint D0) the chance is much smaller, for a 10 × 5 game the chance is less than 10%. This was found experimentally with the code snake2.

Three settings are J = {4, 14, 21, 31, 43, 58}, J = {1, 16, 25, 32, 43, 56}, and J = {8, 19, 23, 39, 48, 54}. The total running time triples for the original constraints against the logical constraints, altough the original D has a much smaller number of constraints. The reason is that the logical constraints (respectively its linear counterparts) yield a much stronger LPrelaxation. This is a typical example of aggregated versus desaggregated constraints. (For the related concept of strong valid inequalities see [3].)
References
[1] MatMod. Homepage for Learning Mathematical Modeling : https://matmod.ch.
[2] SudermannMerx N. MatheWürmchen, eine Aufgabestellung. private communication, from Prof. Dr. Nathan SudermannMerx, Duale Hochschule BadenWürttemberg Mannheim (nathan.sudermannmerx@dhbwmannheim.de).
[3] G.L. Nemhauser and L.A. Wolsey. Integer and Combinatorial Optimization. Wiley, 1988.
[4] Hürlimann T. Reference Manual for the LPL Modeling Language, most recent version. https://matmod.ch/lpl/doc/manual.pdf.