Continuous Line
Draw a continuous line that visits every empty cell of the grid exactly once. The line can start in any empty cell, but it can only move to a horizontal or verticallly adjacent cell (diagonal moves are not allowed). The line must not visit any of the colored cells.
Source: Mip Wise team
Diving Deeper
-
This puzzle is simple enough that kids can often solve it. But don’t feel bad if you are an adult and have a hard time finding a solution. There are many ways to start that will lead to a dead-end or to an incomplete solution that leaves cells not visited.
After a few trials, you will see that the trick is to start from the right spot. Humans are surprisingly good at gaining intuition and learning from a few trials in a problem like this.
For a computer, on the other hand, this is still a combinatorial problem. As such, computers still need some systematic way to explore the large set of possibilities.
-
This puzzle is basically a traveling salesman problem (TSP) in disguise. In fact, the goal here is to visit all the nodes, or cells in this case, with a single tour. The main difference is that we don't care about the cost in this puzzle.
The TSP is one of the most infamous problems in operations research and finds application in the most unexpected settings, much beyond the obvious applications in vehicle routing. Production planning where multiple machines produce multiple products is an example of a non-obvious application of TSP.
-
If we frame this puzzle as a TSP, there will be tons of alternatives to solve it, ranging from heuristics of all sorts to exact methods, including mathematical optimization.
Even if we go only with the mathematical optimization approach, there will be multiple ways we can formulate the problem, two of the most famous are known as DFJ and MTZ formulations.