How large is your snake? A CP approach

I am not sure if it's important or not but sometimes you are curious to know how many items you can fit into your knapsack in the airport or how many queens you can put on the chess board. Today I want to fit the largest possible snake on a maze shape board using constraint programming.

The rules are easy to understand:

• It can only touch the black cells
• It can touch the Perimeter black cells only once (find the starting cell)
• It can not touch itself (red shapes)
• Snake can move 1 cell at a time (horizontally or vertically)
• The green shape is an allowed path

Let's formulate the problem mathematically:

before you begin, please import your required libraries:

import pandas as pd
!pip install ortools
from ortools.sat.python import cp_model
import matplotlib.pyplot as plt # Data visualization
import random
import numpy as np
import time        

Step 0: Understand the problem's requirements

the informations of each cell should be kept in a dictionary to be used later

dic = {}
counter = 0
N = 17
n = N**2

nr, nc = N, N
for r in range(nr):
  for c in range(nc):
    counter+=1
    dic[counter] = (c,r,1)
    if c==(N-1)/2 and r!=(N-1)/2:
      dic[counter] = (c,r,0)        

Step 1: Code the requirements (Variables)

obviously we need a CP model

    model = cp_model.CpModel()        

create the nodes and variables

nodes = [i for i in dic.keys() if dic[i][2]==1]
x={(i,j):model.NewBoolVar(f"flow_{i}_{j}") for i in nodes for j in nodes if distance(i,j,dic)== 1}
assign = {i: model.NewBoolVar(f"assign_{i}") for i in nodes}
endpoint = {i: model.NewBoolVar(f"end_{i}") for i in nodes if dic[i][1] not in [0,N-1] and dic[i][0] not in [0,N-1]}
startpoint = {i: model.NewBoolVar(f"st_{i}") for i in nodes if dic[i][1] in [0,N-1] or dic[i][0] in [0,N-1]}
linked= {(i,j): model.NewBoolVar(f"linked_{i}_{j}") for i in startpoint for j in endpoint}        

Xij is the boolean variable indicating the move from i to j

assign_i is the boolean variable indicating the cell i is in the path (part of snake's body)

startpoint_i is the boolean variable indicating the cell i is starting point of the path

endpoint_i is the boolean variable indicating the cell i is starting point of the path

Step 2: Code the requirements (Constraints)

Create a close tour of selected nodes (if a node is not selected then a tour containing itself will be created), I use the AddCircuit constraint for this purpose.

    arcs= [ (i,j,v) for (i,j),v in x.items()] + [(i,i,assign[i].Not()) for i in nodes] + [(i,j,v) for (i,j),v in linked.items()]
    model.AddCircuit(arcs)        

Only one cell on the boundary can be selected as the starting point

    boundry_nodes_all = [v for i,v in assign.items() if i in startpoint]
    model.AddExactlyOne(boundry_nodes_all)        

Only one cell on the boundary can be touched (which should be the same as starting point)

boundry_nodes_all = [v for i,v in assign.items() if i in startpoint]
model.AddExactlyOne(boundry_nodes_all)        

Only one cell on the non boundary cells can be selected as the end point

    nonboundry_nodes = [v for v in endpoint.values()]
    model.AddExactlyOne(nonboundry_nodes)        

The start and end point should be connected to each other

for (i,j),v in linked.items():
      model.Add(v <= assign[i])
      model.Add(v <= assign[j])
      model.Add(v >= startpoint[i] + endpoint[j] - 1)
      model.Add(v <= startpoint[i])
      model.Add(v <= endpoint[j])        

Non-touching constraints

If two cells are neighbours but there is no link between them then they can't be both on the path !

    for (i,j),v in x.items():
      if (j,i) in x and i>j:
        model.Add(assign[i]+assign[j]<=  1+ v + x[j,i] )        

The objective function is defined as the total visited cells (to be maximized)

    expressions_of = [v for v in assign.values()]
    model.Maximize(cp_model.LinearExpr.Sum(expressions_of))        

Results

What if there are extra paths between the two sections ?

Conclusion

• There is no easy/difficult concept in math. The things become easy to understand once you learn them.
• Largest path is more interesting than shortest path (LP>SP)
• CP is a powerful tool in supply chain management
• Follow the newsletter to learn more (https://lnkd.in/eEzkkk_M ).
• The git repository is in comment section