Problem #488 of the Brute To Best series: Zuma Game.
You’re given a row of coloured balls (board) and the balls in your hand. Each turn, insert one ball from your hand anywhere on the board. Any run of 3 or more balls of the same colour is removed, and the removals chain. Return the fewest balls needed to clear the board, or −1 if it can’t be cleared.
In this video:
Brute force: try every ball from your hand at every position, recursively. The number of branches explodes, and the same states get explored again and again.
The key observation: a game state is just the pair (board, hand). With a sorted hand and a set of visited states, each state is only explored once.
BFS with pruning:
sort the hand, and skip a ball if it’s the same colour as the previous one
insert a ball only next to a ball of the same colour, or between two equal balls of a different colour
after each insert, collapse runs of 3+ and keep going until nothing more can be removed
the first time the board is empty, the BFS level is the answer
Edge cases: a board that can’t be cleared (−1), a board that’s already clearable with a single insert, and chains of removals.
Dry run on board “WWRRBBWW” with hand “WRBRW”. Inserting R gives WWRRRBBWW, and the Rs collapse to WWBBWW. Inserting B gives WWBBBWW, the Bs collapse to WWWW, and then the Ws clear. The answer is 2.
Complexity: exponential in the worst case, but the constraints keep it small (board length at most 16, hand at most 5), and the memo removes repeated states.
LeetCode 488, Zuma Game: https://leetcode.com/problems/zuma-game/
Related problems: #546 Remove Boxes. #1209 Remove All Adjacent Duplicates in String II. #752 Open the Lock (BFS over states). #773 Sliding Puzzle.
Earlier in the series: problems #1 to #487, in order.
Subscribe to Brute To Best for every problem, from the brute force to the best solution.
#leetcode #zumagame #bfs #backtracking #memoization #statesearch #hardproblems #dsa #coding #codinginterview #leetcodesolutions #brutetobest #algorithms #interviewprep #programming
