# How to solve Rogo Puzzle with an extra constraint?

Given a n×m grid with numbered cells and forbidden cells, the objective of the Rogo puzzle is to find a loop of fixed length through the grid such that the sum of the numbers in the cells on the loop is maximized. Some cells should be avoided. ROGO Puzzle

How to add this constraint as a set of mixed integer linear constraints? We need to make sure no Banned cell (black square) is trapped in the closed route? The following red route is optimal (maxizes the total values but it contains black squares.

Two feasible routes are shown as follows:

Introduce a dummy depot (adjacent only to the "border" cells in the first or last row or column) and send one unit of flow from the depot to each banned cell. Let nonnegative decision variable $$z_{i,j}$$ represent the flow along the directed arc from node $$i$$ to node $$j$$, and let binary decision variable $$y_k$$ indicate whether node $$k$$ is part of the loop. Let $$B$$ be the number of banned cells. To prevent trapping banned cells, you need flow balance constraints along with big-M constraint $$z_{i,j} \le B(1 - y_j) \quad \text{for all (i,j)},$$ which enforces $$z_{i,j} > 0 \implies y_j = 0$$.
For your example instance, the maximum score turns out to be $$33$$: