← All posts

Can Apple Game Be Solved Optimally?

tl;dr - Probably not efficiently in the general case.

Checking whether a single rectangle sums to 10 is easy. Verifying a proposed move sequence is also easy. The hard part is finding the best sequence, because every move changes the set of future legal moves. That creates a large search tree with weak decomposition, so exact search scales poorly. For small boards, exact methods like DFS with Branch and Bound can work. For realistic board sizes, heuristic search is the more practical approach.

Problem setup

Consider an m x n board where each cell contains a value from 1 to 9. A legal move selects an axis-aligned rectangle whose cells sum to exactly 10, then removes those cells from the board.

The objective is to maximize the total number of removed cells.

So the problem is: Given an initial board, find the legal move sequence that produces the highest final score.

What is easy

Some parts of the problem are straightforward.

A single candidate rectangle can be checked quickly. With a 2D prefix sum, its cell sum can be computed in O(1) time after O(mn) preprocessing. If legality also requires every cell in the rectangle to still be present, then a second prefix sum over live cells is enough to check that too.

Enumerating all candidate rectangles on the current board is also manageable. There are O(m^2 n^2) axis-aligned rectangles, and each one can be tested quickly.

Verification is manageable as well. If someone gives a full move sequence and claims it removes at least K cells, that claim can be checked in polynomial time by replaying the sequence.

The bottleneck is not local checking. It is global search.

Why exact search gets hard

The difficulty comes from move dependence.

A move can destroy later opportunities. It can also create better future opportunities by changing the remaining layout. So the value of a move is not determined by its immediate gain alone. It depends on the board state it leaves behind.

That makes move ordering central. Two different sequences starting from the same board can end with very different scores.

If the average branching factor is B and the game lasts D moves, a naive search tree has size on the order of B^D. On a 17 x 10 board, both B and D can be large enough for that search space to blow up quickly.

This also limits Dynamic Programming. In problems with strong decomposition, DP works because the state can be broken into nearly independent subproblems. Apple Game does not behave that way in general. A removal in one region can change future feasibility elsewhere, especially when large rectangles are allowed.

Relation to NP-style search

A cleaner way to state the complexity question is as a decision problem: Given a board and an integer K, does there exist a legal move sequence that removes at least K cells?

This version has the usual NP-style structure. A proposed solution can be verified in polynomial time, but finding one may require exploring a large search space.

This is not a proof of NP-hardness. A real proof would require a reduction from a known NP-hard problem. But structurally, the problem looks much closer to hard combinatorial search than to a problem with a simple polynomial-time exact algorithm.

Exact methods

For small boards, exact search is possible.

A standard baseline is DFS with Branch and Bound. Search proceeds depth-first, while branches are pruned whenever an upper bound shows they cannot beat the current best solution.

Memoization can help when different move sequences lead to the same board state. For a fixed initial board, each cell only changes between two states: present or removed. That gives an upper bound of 2^(mn) reachable states rather than 10^(mn). On a 17 x 10 board, that is still far too large for exhaustive state caching.

Constraint programming or ILP-style formulations are also possible on smaller instances. The main issue is that sequential feasibility makes the encoding grow quickly.

For narrow special cases, Dynamic Programming may still be possible. A 1 x n variant, or other restricted geometries, may admit a compact state representation. The general 2D case does not.

Practical conclusion

For small instances, exact optimization is feasible.

For realistic board sizes, exact search becomes expensive quickly. The most promising exact approach is usually DFS with Branch and Bound, combined with good move ordering, a transposition table, and a cheap admissible upper bound such as the number of remaining live cells.

If the goal is strong performance rather than guaranteed optimality, heuristics are the practical choice.

Heuristic search

Beam search visualization. CC BY-SA 4.0, Wikimedia Commons.

A Greedy Solver picks the best-looking move according to a local rule. It is fast and easy to implement, but it can miss sequences where a weaker short-term move leads to a much better continuation.

Beam Search keeps the top-k partial solutions at each depth instead of following only one path. This is still approximate, but it explores a wider part of the search space than a purely greedy method.

Heuristics can also use proxy objectives. Instead of maximizing only immediate gain, a solver can prefer moves that preserve future options or avoid isolating difficult cells.

These methods do not guarantee the optimum, but they are much more practical at full board size.