Zipping

Posted on by mabouali

No! This is not a post about file compression algorithm called zip. Yes! this is about solving another LinkedIn puzzle called Zip.

What is Zip Puzzle?

It is a nice puzzle. You are given a board, usually 6x6. Certain cells on the board are numbered.

You need to trace a path on the board.

The rules are easy:

  • Start from the cell marked as 1
  • End on the cell with the highest number (14 in above image)
  • You must go through all cell (numbered or not)
  • You cannot cross/intersects your path.
  • Numbered cells must be entered in order.
    • eg. You can enter 4 only after you have entered 3. There could be any number of unnumbered cells between 3 and 4 though.

Some times there are some barriers on the board:

In this case, you are not able to move from one cell to another if it is blocked by the barrier. For example, in above picture, from cell on the first row and 3rd column, you are not allowed to go to the cell on 2nd row and 3rd column.

How to solve it using OR-Tools?

So, let's go through the process and model it with OR-Tools to solve it.

Decision Variables

If you have read Mini-Sudoku solver and Tango Solver, you know that we need to choose some variables that once OR-Tools is done with solving the model, the values set for those decision variables translate into the answer of the puzzle.

In previous two puzzles (i.e. Mini-Sudoku and Tango), choosing decision variables were rather straight forward. In Mini-Sudoku you needed to decide what numbers goes to each cell. That's your decision variable. In Tango you needed to find if moon (0) or sun (1) must be assigned to a cell; that was your decision variable.

In this puzzle (i.e. Zip), it is a bit different. You are not choosing a value for the cell, you are choosing the order that is assigned to each cell. So, in a way, you could say that the value for each cell is its order.

There are multiple way to do this, The harder way, and the easier way. In this post we are doing it using the harder way.

I am going to treat traveling a cell as a task. Each task/cell would have a start and an end. The start is when I enter a cell; likewise, the end is when I exit the cell. I assume it takes 1 unit (of time or length) to enter a cell and exit a cell. It might appear that we are introducing two decision variable per cells, but you will see that essentially there would be only one.

You can also just have one decision variable per cells and that being their order. I will have another post modeling the problem that way later. However, I wanted to use this opportunity to introduce a new type of variables in OR-Tools.

Constraints

If you check the rules, there are couple of constraints that we need to model.

Numbered Cells must be entered in order.

If we denote the start time of i-th task (i.e. the time that we enter i-th cell) as s_i, and its end time as e_i, then essentially we have:

    \[e_i \le s_j\]

where:

    \[n_j - n_i = 1\]

and n_i and n_j are the number assigned to i-th and j-th cell.

You can move only left/right and up/down

You cannot jump a cell. You have to move just left/right and up/down. Each cell have 4 choices then: left, right, up, and down; except:

  • if the cell is on the edge of the board, then depending on which edge it is, one of the 4 moves is not available, and
  • if there is a barrier between the two cells, that move is banned.

for a cell that is on i-th row and j-th column it's neighbors are:

  • Horizontal neighbors: on the same row:
    • left: j-1
    • right: j+1
  • Vertical Neighbors: on the same column:
    • up: i-1
    • down: j+1

so, depending on which direction we decide to move:

  • if we are going up the constraint is: e_{i,j} = s_{i-1,j}
  • if we are going down the constraint is: e_{i,j} = s_{i+1,j}
  • if we are going left the constraint is: e_{i,j} = s_{i,j-1}
  • if we are going right the constraint is: e_{i,j} = s_{i,j+1}

you might think but which one of the above constraint we should impose? There you go, we need to introduce another variable that essentially decides which direction we will go.

The path should cover all cells on the board

We need to cover the board completely. That means we need to visit each cells. we can cover the unnumbered cells in any order, but the number cells must be entered in order.

You would see, however, that instead of explicitly specifying this constraint, we have setup our model in such a way that it results in every cell to be visited. So, there is no need to track the visitation of each cell by a separate variable and make sure they are all visited.

How to implement this with OR-Tools

Helping Methods

Cells

We are going to create two helping objects. The first one is the cell definition:

@dataclass
class Cell:
    row_id: int
    col_id: int

    def is_horizontally_adjecent_to(self, cell: "Cell") -> bool:
        return (
            (self.row_id == cell.row_id) and 
            (abs(self.col_id -  cell.col_id) == 1)
        )

    def is_vertically_adjecent_to(self, cell: "Cell") -> bool:
        return (
            (self.col_id == cell.col_id) and 
            (abs(self.row_id -  cell.row_id) == 1)
        )

    def is_adjacent_to(self, cell: "Cell") -> bool:
        return self.is_horizontally_adjecent_to(cell) or self.is_vertically_adjecent_to(cell)

    def __hash__(self):
        return (self.row_id, self.col_id).__hash__()

This class assists us to keep track of a cell and perform certain actions, like find out if two cells are adjacent or not.

Barriers

The second class is called Barriers:

@dataclass
class Barriers:
    def __init__(self):
        self._map: dict[Cell, set[cell]] = {}

    def add_barrier(self, cell_1: Cell, cell_2: Cell):
        if cell_1.is_adjacent_to(cell_2):
            self._map.setdefault(cell_1, set()).add(cell_2)
            self._map.setdefault(cell_2, set()).add(cell_1)
        else:
            raise ValueError("A barrier can be set only between two cells that are adjacent")
        
        return self
        
    def add_barriers(self, entries: list[tuple[Cell, Cell]]):
        for cell_1, cell_2 in entries:
            self.add_barrier(cell_1, cell_2)

        return self
            
    def has_barrier(self, cell_1: Cell, cell_2: Cell):
        return (
            (cell_1 in self._map) and (cell_2 in self._map[cell_1])
        ) or (
            (cell_2 in self._map) and (cell_1 in self._map[cell_2])
        )

Remember that sometimes the zip puzzle sets barriers between some cells, which limits our capability to freely move between these two cells. The Barriers class allows us to store the location of the barriers and query that later in our main code.

Creating a task for each cell

If you remember, we said a task is defined by its start time, end time, and size or duration. Fortunately OR-Tool has an easy way to introduce task such as the one mention here: It's called interval variables.

NewIntervalVar(start, size, end, name)

You can access the documentation here.

The interval variables, effectively are 3 decision variables and 2 constraints. The variables are:

  • s_i start of the interval
  • e_i the end of the interval
  • d_i the duration, size, or length of the interval.

And the constraints are:

  1. d_i \ge 0
  2. s_i - e_i + d_i = 0

In our solution once we initialize our board we set a task for each cell as follows:

self.task_start_time = [
    [
        self.model.NewIntVar(lb=0, ub = self.board_size, name=f"start_{i}_{j}")
        for j in range(self.col_size)
    ]
    for i in range(self.row_size)
]

self.task_end_time = [
    [
        self.model.NewIntVar(lb=0, ub = self.board_size, name=f"end_{i}_{j}")
        for j in range(self.col_size)
    ]
    for i in range(self.row_size)
]
self.model_tasks = [
    [
        self.model.NewIntervalVar(
            start=self.task_start_time[i][j],
            size=1,
            end=self.task_end_time[i][j],
            name=f"task_{i}_{j}",
        )
        for j in range(self.col_size)
    ]
    for i in range(self.row_size)
]

First we make the start variable, then the end variable and then the interval variable. OR-Tools effectively creates the constraints internally for us.

Numbered cells must be entered in order

As mentioned some cells must be entered in order. In our solver, we will accept a list of Cell objects. Since list is order, we must start from the first cell in the list and go through each cell in the order that they are defined in the cell and then end our path at the last cell noted in the list.

Since we are starting on the first cell we can say the start time that is assigned to that cell should be set to 0 (constraint to zero).

# First Cell starts first
self.model.Add(self.task_start_time[cell_order[0].row_id][cell_order[0].col_id] == 0)

Since we should end our path on the last numbered cell, and we assumed the duration of each task is 1 second, we can say that the end time for the task assigned to that cell must be equal to the size of the board or the number of cells in the board. 

# Last Cell ends the latest.
self.model.Add(self.task_end_time[cell_order[-1].row_id][cell_order[-1].col_id] == self.board_size)

for all the other numbered cells all we can say is that the start time of the next cell in the list should be equal or greater than the end time of the task assigned to the cell before it. The equal is for the case that we enter the next numbered cell immediate without going through some un-numbered cells first.

for i in range(1,len(cell_order)):
    # forcing the previous cell in order to end before or on the start of next cell.
    self.model.Add(
        self.task_end_time[cell_order[i-1].row_id][cell_order[i-1].col_id] <=
        self.task_start_time[cell_order[i].row_id][cell_order[i].col_id]
    )

We can move only up/down and left/right & not cross a barrier

Now we need to set some more constraint that forces us to move from one cells only up/down and left/right without jumping around the board. Also, if there is a barrier between two adjacent cells we are not allowed to move between them. 

# Now we need to set possible moves for each cell
for i in range(self.row_size):
    for j in range(self.col_size):
        if (cell_order[-1].row_id == i) and (cell_order[-1].col_id == j):
            # This is the last cell that we should end up. There is no more moves.
            continue

        self.set_next_move(i,j)

The magic happens in the "set_next_move". Remember we said earlier that if we need to move up, essentially we can force the end time of the current cell to be equal to the start time of the cell above it. Likewise, if we are moving down the end time of the current cell must be equal to the start time of the cell below it. Similarly for the left and right. Of course, we do not need to set any next move for the last cell.

So first we create a method that tells us what are valid neighboring cells that we can move to from the current cell. This is where the barriers also come into play.

def get_neighbor_cells(self, row_id: int, col_id: int) -> list[Cell]:
    neighbor_cells: list[Cell] = []

    # left 
    if col_id > 0 and not self.barriers.has_barrier(Cell(row_id, col_id), Cell(row_id, col_id - 1)):
        neighbor_cells.append(Cell(row_id, col_id - 1))

    # right
    if col_id < (self.col_size - 1) and not self.barriers.has_barrier(Cell(row_id, col_id), Cell(row_id, col_id + 1)):
        neighbor_cells.append(Cell(row_id, col_id + 1))

    # up
    if row_id > 0 and not self.barriers.has_barrier(Cell(row_id, col_id), Cell(row_id - 1, col_id)):
        neighbor_cells.append(Cell(row_id - 1, col_id))

    # down
    if row_id < (self.row_size - 1) and not self.barriers.has_barrier(Cell(row_id, col_id), Cell(row_id + 1, col_id)):
        neighbor_cells.append(Cell(row_id + 1, col_id))

Then for each neighboring cell we are going to create a boolean variable. If the value of that boolean variable is true (1) we have decided to move to that cell. If its value is false (0) we have decided to not move to that cell from our current cell.

bool_variables = [
    self.model.NewBoolVar(f"b_{i}_{j}_{idx}")
    for idx, neighbor_cell in enumerate(neighbor_cells)
]

Then we need to enforce the constraint, that is the end time of the current cell must be equal to the start time of the next cell that we move. This can be done as follows:

for idx, neighbor_cell in enumerate(neighbor_cells):
    self.model.Add(
        self.task_end_time[i][j] == self.task_start_time[neighbor_cell.row_id][neighbor_cell.col_id]
    ).OnlyEnforceIf(bool_variables[idx])

Notice the use of \mathtext{OnlyEnforceIf(bool_{variable})}. What we are doing above we are setting the constraint for each possible move; but we are also telling OR-Tools that this constraint is only enforcable if we decide to go that cell (i.e. the associate boolean variable we create is True). If we have decided not to go that cell, that means the boolean variable is false and OR-Tools knows that it should not enforce that constraint due to the presence of \mathtext{OnlyEnforceIf(bool_{variable})}.

Cover all cells

There is one more constraint that we need to enforce and that is that we need to go to all cells. Notice that in the last section we enforced the constraint for all neighboring cells; except the last cell of course. But we mentioned that the constraint is valid only if we choose to go to that neighboring cell using "OnlyEnforceIf" condition.

One valid choice now would be that OR-Tools sets all the boolean variable that was specifying which neighboring cells we want to move to to false. effectively not moving any where. So, we have to now force OR-Tools that this is not an option. It has to choose one and only one neighboring cell to move to. That can be done using:

self.model.add(sum(bool_variables) == 1)

The last constraint is forcing OR-Tools to make exactly one of those boolean variables to true and the rest to false; effectively to move to the neighbor.

All the code

We discussed different code snippet of the entire model. But If you want to see the entire code, you can download the Jupyter Notebook containing the entire model here.

Let’s zip through some example.

Example 1: No barriers

Let's solve the first example that we shared at the beginning of this post, the one that didn't have any barriers.

zip_solver = ZipSolver()

status = zip_solver.solve(cell_order=[
    Cell(2, 4),
    Cell(5, 4),
    Cell(4, 4),
    Cell(3, 4),
    Cell(1, 5),
    Cell(1, 4),
    Cell(1, 3),
    Cell(0, 2),
    Cell(0, 0),
    Cell(0, 1),
    Cell(1, 1),
    Cell(2, 1),
    Cell(3, 1),
    Cell(4, 1),
])

if status:
    print("Found a solution.")
else:
    print("Failed to find a solution.")

and the output would be:

  0: Start on: Cell(row_id=2, col_id=4)
  1: Go Left  to Cell(row_id=2, col_id=3)
  2: Go Down  to Cell(row_id=3, col_id=3)
  3: Go Down  to Cell(row_id=4, col_id=3)
  4: Go Down  to Cell(row_id=5, col_id=3)
  5: Go Right to Cell(row_id=5, col_id=4)
  6: Go Right to Cell(row_id=5, col_id=5)
  7: Go Up    to Cell(row_id=4, col_id=5)
  8: Go Left  to Cell(row_id=4, col_id=4)
  9: Go Up    to Cell(row_id=3, col_id=4)
 10: Go Right to Cell(row_id=3, col_id=5)
 11: Go Up    to Cell(row_id=2, col_id=5)
 12: Go Up    to Cell(row_id=1, col_id=5)
 13: Go Up    to Cell(row_id=0, col_id=5)
 14: Go Left  to Cell(row_id=0, col_id=4)
 15: Go Down  to Cell(row_id=1, col_id=4)
 16: Go Left  to Cell(row_id=1, col_id=3)
 17: Go Up    to Cell(row_id=0, col_id=3)
 18: Go Left  to Cell(row_id=0, col_id=2)
 19: Go Down  to Cell(row_id=1, col_id=2)
 20: Go Down  to Cell(row_id=2, col_id=2)
 21: Go Down  to Cell(row_id=3, col_id=2)
 22: Go Down  to Cell(row_id=4, col_id=2)
 23: Go Down  to Cell(row_id=5, col_id=2)
 24: Go Left  to Cell(row_id=5, col_id=1)
 25: Go Left  to Cell(row_id=5, col_id=0)
 26: Go Up    to Cell(row_id=4, col_id=0)
 27: Go Up    to Cell(row_id=3, col_id=0)
 28: Go Up    to Cell(row_id=2, col_id=0)
 29: Go Up    to Cell(row_id=1, col_id=0)
 30: Go Up    to Cell(row_id=0, col_id=0)
 31: Go Right to Cell(row_id=0, col_id=1)
 32: Go Down  to Cell(row_id=1, col_id=1)
 33: Go Down  to Cell(row_id=2, col_id=1)
 34: Go Down  to Cell(row_id=3, col_id=1)
 35: Go Down  to Cell(row_id=4, col_id=1)
Found a solution.

Example 2: With Barriers

Let's now try the second board that we shared in the beginning of this post; the one with barriers:

zip_solver = ZipSolver(
    barriers=Barriers().add_barriers([
        (Cell(0, 2), Cell(1, 2)),
        (Cell(0, 3), Cell(1, 3)),
        (Cell(1, 2), Cell(2, 2)),
        (Cell(1, 3), Cell(2, 3)),
        (Cell(2, 1), Cell(3, 1)),
        (Cell(2, 2), Cell(3, 2)),
        (Cell(2, 3), Cell(3, 3)),
        (Cell(2, 4), Cell(3, 4)),
        (Cell(4, 1), Cell(3, 1)),
        (Cell(4, 2), Cell(3, 2)),
        (Cell(4, 3), Cell(3, 3)),
        (Cell(4, 4), Cell(3, 4)),
    ])
)

status = zip_solver.solve(cell_order=[
    Cell(4, 2),
    Cell(4, 1),
    Cell(4, 0),
    Cell(4, 3),
    Cell(4, 4),
    Cell(4, 5),
    Cell(2, 4),
    Cell(2, 1),
    Cell(2, 2),
    Cell(2, 3),
])

if status:
    print("Found a solution.")
else:
    print("Failed to find a solution.")

The only difference is that since, this one has barriers, when initializing the solver, we are adding some barriers. The output of our model would be:

  0: Start on: Cell(row_id=4, col_id=2)
  1: Go Left  to Cell(row_id=4, col_id=1)
  2: Go Left  to Cell(row_id=4, col_id=0)
  3: Go Down  to Cell(row_id=5, col_id=0)
  4: Go Right to Cell(row_id=5, col_id=1)
  5: Go Right to Cell(row_id=5, col_id=2)
  6: Go Right to Cell(row_id=5, col_id=3)
  7: Go Up    to Cell(row_id=4, col_id=3)
  8: Go Right to Cell(row_id=4, col_id=4)
  9: Go Down  to Cell(row_id=5, col_id=4)
 10: Go Right to Cell(row_id=5, col_id=5)
 11: Go Up    to Cell(row_id=4, col_id=5)
 12: Go Up    to Cell(row_id=3, col_id=5)
 13: Go Left  to Cell(row_id=3, col_id=4)
 14: Go Left  to Cell(row_id=3, col_id=3)
 15: Go Left  to Cell(row_id=3, col_id=2)
 16: Go Left  to Cell(row_id=3, col_id=1)
 17: Go Left  to Cell(row_id=3, col_id=0)
 18: Go Up    to Cell(row_id=2, col_id=0)
 19: Go Up    to Cell(row_id=1, col_id=0)
 20: Go Up    to Cell(row_id=0, col_id=0)
 21: Go Right to Cell(row_id=0, col_id=1)
 22: Go Right to Cell(row_id=0, col_id=2)
 23: Go Right to Cell(row_id=0, col_id=3)
 24: Go Right to Cell(row_id=0, col_id=4)
 25: Go Right to Cell(row_id=0, col_id=5)
 26: Go Down  to Cell(row_id=1, col_id=5)
 27: Go Down  to Cell(row_id=2, col_id=5)
 28: Go Left  to Cell(row_id=2, col_id=4)
 29: Go Up    to Cell(row_id=1, col_id=4)
 30: Go Left  to Cell(row_id=1, col_id=3)
 31: Go Left  to Cell(row_id=1, col_id=2)
 32: Go Left  to Cell(row_id=1, col_id=1)
 33: Go Down  to Cell(row_id=2, col_id=1)
 34: Go Right to Cell(row_id=2, col_id=2)
 35: Go Right to Cell(row_id=2, col_id=3)
Found a solution.

Leave a Reply

Your email address will not be published. Required fields are marked *