For more than three years, the online puzzle game Digit Party sometimes showed players a perfect score… that was actually impossible to achieve.
The principle behind the game is simple. A grid contains 25 squares, in which the player gradually places numbers. Identical values earn points when they touch, even diagonally. Three 8s grouped together can therefore earn 24 points, while an isolated 8 earns nothing.
Two grids showing different arrangements with the same draw, illustrating various connections.
At the end of a game, Digit Party also displays the theoretically possible high score. This was the number that caused the problem. Its creators, mathematicians Vincent Vatter and Robert Brignall, knew how to calculate a value that no player could exceed. But this limit was not always actually attainable.
To understand why, the grid must be viewed as a packing problem. Taken separately, each group of numbers has an ideal arrangement: all the 4s together, all the 8s together, and so on. But all these arrangements must then share the same 25 squares. Sometimes, what is perfect for one group prevents another group from achieving its best arrangement.
In other words, adding up the best possible results for each number does not necessarily produce the best result for the entire grid. This is precisely what misled the game. Of the 1,096 daily grids offered over three years, 55 displayed an unattainable target. The error remained small: about two points on average, and six at most, for scores generally ranging between 150 and 200.
The next challenge was finding a method fast enough to fix the problem. In theory, Digit Party can produce around 13.9 million different draws. The researchers nevertheless noticed that many of them are mathematically similar. What matters most is how many times each number appears, not its exact value.
By grouping draws with the same structure, they reduced the millions of possibilities to 1,291 basic cases. In 891 cases, all the groups of numbers can reach their best arrangement simultaneously. For the other 400, a few points must be sacrificed somewhere.
The researchers then calculated the most advantageous compromises in advance. If the grid does not allow, for example, all the 4s and all the 8s to be grouped perfectly, sacrificing a few points on the 4s may be preferable. The 8s are worth more and can make up for that loss. The game can now immediately find the true maximum corresponding to each draw.
This story relates to a classic optimization problem: several excellent choices made separately do not necessarily form the best overall solution. The same principle applies when organizing schedules, loading a vehicle, or distributing tasks in a factory.
One question remains open. Knowing the maximum score still does not tell a player how to play to reach it, because the numbers appear one at a time. Even Digit Party’s two creators do not yet know which strategy is best.