Decanta: Measuring How Hard a Water Sort Puzzle Is

Decanta is a water sort puzzle I built for the iPhone and the web. Each glass tube holds four layers of coloured water; tap a tube, then another, and the top colour pours across, onto the same colour or into an empty tube, as much as fits. Sort every colour into a tube of its own to win.

Like my other puzzle games, it has endless levels and a daily puzzle, generated on the device from a seed. The hard part wasn’t generating puzzles; shuffling layers into tubes takes one line. The hard part was knowing how hard each one is, so that level 13 feels harder than level 12, and a “Super Hard” daily deserves its name.

The obvious measure doesn’t work

The first idea is to make harder levels bigger: more colours, more tubes, more pours to the end. Bigger boards do take longer. But a long puzzle where every sensible pour works is tedious, not hard. What makes a water sort hard is the feeling of being stuck: you pour, the board looks fine, and five pours later there is nowhere to go.

So Decanta measures exactly that.

Traps: the moves that lead to a dead end

For every position along a solution, the analysis looks at each pour worth trying (moves that can’t help aren’t counted: pouring a tube that holds a single colour into an empty tube only moves the tube, and all empty tubes are alike) and asks whether the board can still be solved after it. A pour after which it can’t is a trap. (Undo is free in Decanta, so a trap doesn’t end the game; it costs the pours made before the player notices.) The difficulty signal is the share of traps among all the pours worth trying along the way:

// Excerpt from analyze(): tubes starts as the packed deal, the counters at 0,
// and outcome() is the budgeted dead-end search.
result.pours.forEach((step, index) => {
  usefulMoves(height, tubes, moves);
  let dead = 0;
  for (const move of moves) {
    const verdict = outcome(applyMove(height, tubes, move));
    if (verdict === 'dead') dead++;
    else if (verdict === 'unknown') unknown++;
  }
  if (index === 0) startTraps = moves.length > 0 ? dead / moves.length : 0;
  tried += moves.length;
  trapped += dead;
  tubes = applyMove(height, tubes, step.from * 64 + step.to);
});

A traps value of 0.2 means that, at the positions along the solver’s solution, one pour in five worth trying leads, sooner or later, to a dead end. It’s a sample along one good path, not over every position a player might reach. The analysis also records the traps at the very first position, the average number of pours worth trying (the branching), and the length of the solution.

A solver that fits on a phone

All of this needs a solver that can answer “is this position still solvable?” hundreds of times per deal, in a phone’s browser. Decanta uses two budgeted searches over the same packed positions: a weighted A* that finds a solution, and a depth-first search, trying the pours that lower the runs first, that settles whether a position is still alive:

• Positions are packed into plain numbers, one per tube, so copying and comparing them is cheap.
• Tube order doesn’t matter: positions that differ only in the order of their tubes share a key and are visited once.
• The heuristic counts runs of the same colour. A pour lowers the number of runs on the board by one at most, and a solved board has one run per colour, so runs − colours never overestimates the pours left. Weighting it by 2 finds a solution far sooner than plain A*, at the cost of one that is a little longer than the shortest.
• A budget caps the work: 50,000 positions to solve a deal, 5,000 for the depth-first search that settles each pour’s outcome. A pour the budget can’t settle is reported as unknown and not counted as a trap, so the measure errs on the side of easy.

What the numbers say

I ran the real generator on 40 deals at each size (in Node on my laptop; other seeds give slightly different figures), with two empty tubes and four layers per tube:

Two things stand out. Traps do rise with the colours, from none at four to about a fifth of the pours worth trying at twelve, so colours set the general level of a tier. But they vary a lot from deal to deal at the same size: a 10-colour deal can have no traps at all, and an 8-colour one can have a fifth. Size alone would have made some Hard levels easy and some Medium levels brutal.

The number of empty tubes matters even more. With only one, random deals are almost never solvable:

6 colours, 1 empty: solved 5/40
10 colours, 1 empty: solved 0/40

The rest aren’t budget failures: the search exhausts them and proves them unsolvable.

So every board has two empty tubes, and the difficulty comes from the colours and the traps.

From a measure to a level

Each tier sets its colours and a band on the traps, and picks among several candidate deals, each from its own sub-seed (level:13#0, level:13#1 …):

If no candidate lands in the band, the deal nearest to it is kept.

A deal is also re-dealt if it starts with a complete tube or too many neighbouring layers already of one colour, so no level opens half sorted. Everything is deterministic: the same seed keeps the same deal, so level 13 is the same puzzle on every device. On the real levels (again in Node on my laptop):

level 1: easy, 5 tubes, traps 0.000, 1 ms
level 12: medium, 8 tubes, traps 0.086, 2 ms
level 13: hard, 10 tubes, traps 0.183, 17 ms
level 20: superHard, 13 tubes, traps 0.254, 56 ms
level 300: superHard, 14 tubes, traps 0.282, 90 ms

After ten easy levels, the level path mixes the tiers in blocks of ten (medium, medium, hard, medium, medium, medium, hard, medium, medium, super hard), so difficulty rises and falls instead of climbing a wall, and colours grow slowly over the first 300 levels.

The same solver, three jobs

Once the solver existed, it paid for itself twice more in the game:

• Hints: the next pour of a solution from the current position, with a smaller budget (20,000 positions, well under a second), so a hint never keeps the player waiting; if the budget runs out, the game offers no hint rather than a guess.
• Dead-end warning: after each pour, a background worker checks whether the board can still be solved, and when it proves a dead end, the game says so (if the budget runs out, it stays silent) instead of letting the player pour for minutes into a lost position.
• Calibration tests: a test suite generates hundreds of levels and checks that all but a handful of 400 levels land in their tier’s band and that each tier’s average traps stays in range, so a change to the generator can’t silently make the game easier or harder.

Takeaways

• Measure the experience, not the size. For a puzzle, “how often does a reasonable move lose?” is closer to how hard it feels than how big it is.
• Expect variance, and select for it. Generate a few candidates and keep the one in the band; don’t trust a single deal of the right size.
• Give the solver a budget and decide which way unknowns fall.
• Reuse the solver for hints, warnings and tests; it’s the most valuable piece of code in the game.

You can play Decanta in your browser at decanta.jonathas.net; the iPhone version is on its way to the App Store.