Lattice puzzle
Easy to check. Hard to solve.
Every point on the board starts black. Swap black stones for white until the whole board is covered, using as few white stones as you can. You can see at a glance whether you’ve covered it. Finding the fewest stones that do it is much harder.
The rules
One stone covers five points
- Start with a board of black stones. Every intersection has one.
- Swap a black stone for a white one. A white stone covers its own point and the four points directly above, below, left and right of it. Diagonals don’t count.
- Cover every point. Each point must be white or sit next to a white stone. Points can be covered more than once.
- Use as few white stones as possible. Each board has a known minimum. Match it and you’ve found an optimal solution.
Play
Cover the board
- White stones
- 0
- Uncovered points
- 25
- Fewest possible
- 7
Tap a point to swap its stone. On a keyboard, use the arrow keys to move and Enter or Space to swap.
Why it’s hard
A small answer that’s hard to find
The lattice puzzle is the minimum dominating set problem on a square grid, a classic NP-hard problem in combinatorial optimisation. Checking an answer takes a glance. Finding the best one is another matter.
On the full 19×19 board there are 2361 ways to choose which points are white, a 109-digit number. Checking them one at a time at a billion a second would take vastly longer than the age of the universe. You can’t enumerate them; you have to search. The minimum for the full board is only 84 stones. Finding which 84 is the hard part.
The same gap sits underneath materials and chemistry discovery. The space of possible configurations grows exponentially, and scoring one candidate is far cheaper than finding the best. That is the kind of search Percene’s quantum machine learning is built for. See how we apply it.
| Board | Possible arrangements | Fewest stones |
|---|---|---|
| 5 × 5 | 2²⁵ ≈ 3.4 × 10⁷ | 7Proved optimal by exact solver |
| 7 × 7 | 2⁴⁹ ≈ 5.6 × 10¹⁴ | 12Proved optimal by exact solver |
| 9 × 9 | 2⁸¹ ≈ 2.4 × 10²⁴ | 20Proved optimal by exact solver |
| 19 × 19 | 2³⁶¹ ≈ 4.7 × 10¹⁰⁸ | 84Matches the proven formula for n ≥ 14 |
The 5×5, 7×7 and 9×9 minimums were proved with an exact solver. For n ≥ 14 the n×n minimum is ⌊(n+2)²/5⌋ − 4, which gives 84 for 19×19. You may see 79 quoted for the full board; that comes from misreading OEIS A104519, which is offset by two.
Sources: OEIS A104519; Alanko et al., Computing the Domination Number of Grid Graphs; Gonçalves et al., The Domination Number of Grids.