Digits Tracking
Consider the list of cells in the figure.
Each cell has a label which is a digit from 0 to 9.
Place a digit, from 0 to 9, in each cell in a way that the digit placed in cell i equals the number of times the digit i appears in the list.
For example, if you place digit 2 in Cell 1, then digit 1 must be placed in exactly 2 cells.
Source: Puzzle Corner - MIT
Diving Deeper
-
The Digits Tracking puzzle illustrates the challenge of making multiple interconnected decisions.
When we decide to place, let’s say, digit 3 in Cell 2, it implies that digit 2 must be placed in 3 cells. Let's say we place digit 2 in Cells 3, 4, and 5. That will then force us to place each of the digits 3, 4, and 5 in 2 cells, which will again have implications that will likely lead to an infeasible solution.
The number of possibilities is huge, 10 billion to be precise. And only one works! But that doesn’t mean that we have to evaluate all possible combinations to solve the puzzle. That would be insane! By using some logic, we can quickly narrow the possibilities down to a few options and find the one that works.
If you get stuck for too long, consider solving first the "baby version": with digits from 0 to 4 only.
If you find it too easy, try to generalize your solution for the "tough version": with digits from 0 to n, where n is an integer greater than or equal to 4.
-
Interconnected decisions appear everywhere in the real world.
Consider for instance the Maccabi Games, a tournament that involves hundreds of athletes, each playing multiple sports that are hosted in different fields/locations, over several days. Creating a feasible schedule for such an event is like solving the Digits Tracking puzzle but at a much larger scale.
-
We solved this puzzle using mixed-integer programming (MIP).
The hardest part is to write the mathematical formulation, which is then easy to implement in Python and solve in a regular notebook in a fraction of a second—creating good schedules for the Maccabi Games takes a few hours though.