Snakes Problem (snake1)

Table of Contents

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 grandmother-in-law, Meta Trumpp.

Figure 1: A trivial Solution / a more difficult Game

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

xi = ⌊(i - 1)∕10⌋ , yi = ⌊(i - 1) mod 10 ⌋

Two pellets i and j are neighbors if e_i,j is true, where

ei,j = i = j - 10 ∨ (i = j + 1 ∧ (i - 1) mod 10 ⁄= 0 )

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:
$z = 1 , forall h ∈ H h,Jh,1$
At each grid point only one pellet can be placed:
$∑ zh,i,k = 1 , forall i ∈ I h,k$
Each pellet with color h and at position k must be set:
$∑ zh,i,k = 1 , forall h ∈ H, k ∈ K i$
Each pellet at positions 2 to 9 must have a predecessor and a follower:
$∑ ∑ 2z ≤ z + z , forall h ∈ H,i ∈ I,k ∈ {2,...,9 } h,i,k h,j,k-1 h,j,k+1 j|ei,j j|ei,j$
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)
$∑ ′ 4 - 2zh,i,k ≥ zh,j,k , forall h ∈ H, i ∈ I, k ∈ K j,k′∈K|ei,j$
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

Listing 1: The Main Model implemented in LPL [4]

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,k|1<k<#k}: 2*z[h,i,k] <= 
         sum{j|e[i,j]} z[h,j,k-1] + sum{j|e[i,j]} z[h,j,k+1]; 
      D0{h,i,k}: 4-2*z[h,i,k] >= sum{j,k1 in k|e[i,j]} z[h,j,k1]; 
    solve; 
  end

Solution

A solution with and without circles is given in Figure 2.

Figure 2: A Solution with and without Circles

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:

$∨ ∨ zh,i,k → zh,j,k- 1 ∧ zh,j,k+1 , forall h ∈ H, i ∈ I,k ∈ {2, ...,9} j|ei,j j|ei,j$

LPL translates this into two constraints as follows:

$∑ zh,i,k ≤ zh,j,k-1 , forall h ∈ H, i ∈ I,k ∈ {2,...,9} j|e i,j$

$∑ zh,i,k ≤ zh,j,k+1 , forall h ∈ H, i ∈ I,k ∈ {2,...,9} j|ei,j$

The LPL formulation of this constraint is:
```
D{h,i,k|1<k<#k}: z[h,i,k] -> 
      or{j|e[i,j]} z[h,j,k-1] and or{j|e[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 LP-relaxation. 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] Sudermann-Merx N. Mathe-Würmchen, eine Aufgabestellung. private communication, from Prof. Dr. Nathan Sudermann-Merx, Duale Hochschule Baden-Württemberg Mannheim (nathan.sudermann-merx@dhbw-mannheim.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.