Zuma Game

hard string backtracking bfs

Problem

You have a row of coloured balls (board) and a multiset of balls in hand. On each move insert one ball; any consecutive run of ≥3 same-colour collapses (cascading). Return the minimum balls you must insert to clear the board, or −1.

Inputboard = "WRRBBW", hand = "RB"

Output-1

Try every (position, hand colour); recurse on the collapsed state with one fewer hand ball.

board

hand

def find_min_step(board, hand):
    from collections import Counter
    def reduce(b):
        i = 0
        while i < len(b):
            j = i
            while j < len(b) and b[j] == b[i]: j += 1
            if j - i >= 3: return reduce(b[:i] + b[j:])
            i = j
        return b
    seen = {}
    def go(b, h):
        if not b: return 0
        key = (b, tuple(sorted(h.items())))
        if key in seen: return seen[key]
        best = float("inf")
        for i in range(len(b) + 1):
            for c in list(h):
                if h[c] == 0: continue
                nb = reduce(b[:i] + c + b[i:])
                h[c] -= 1
                r = go(nb, h)
                if r != float("inf"): best = min(best, r + 1)
                h[c] += 1
        seen[key] = best
        return best
    ans = go(board, Counter(hand))
    return -1 if ans == float("inf") else ans

function findMinStep(board, hand) {
  function reduce(b) {
    let i = 0;
    while (i < b.length) {
      let j = i;
      while (j < b.length && b[j] === b[i]) j++;
      if (j - i >= 3) return reduce(b.slice(0, i) + b.slice(j));
      i = j;
    }
    return b;
  }
  const seen = new Map();
  function go(b, h) {
    if (!b) return 0;
    const key = b + "|" + h;
    if (seen.has(key)) return seen.get(key);
    let best = Infinity;
    for (let i = 0; i <= b.length; i++)
      for (const c of new Set(h)) {
        const nh = h.replace(c, "");
        const r = go(reduce(b.slice(0, i) + c + b.slice(i)), nh);
        if (r !== Infinity) best = Math.min(best, r + 1);
      }
    seen.set(key, best);
    return best;
  }
  const ans = go(board, hand);
  return ans === Infinity ? -1 : ans;
}

// Memoize on (board, sorted-hand). For each gap × each colour, insert, collapse runs of 3+, recurse.
class Solution {
    Map seen = new HashMap<>();
    public int findMinStep(String board, String hand) {
        char[] h = hand.toCharArray(); Arrays.sort(h);
        int ans = go(board, new String(h));
        return ans >= 1_000_000 ? -1 : ans;
    }
    int go(String b, String h) {
        if (b.isEmpty()) return 0;
        String key = b + "|" + h;
        if (seen.containsKey(key)) return seen.get(key);
        int best = 1_000_000;
        for (int i = 0; i <= b.length(); i++)
            for (int k = 0; k < h.length(); k++) {
                if (k > 0 && h.charAt(k) == h.charAt(k-1)) continue;
                String nb = reduce(b.substring(0, i) + h.charAt(k) + b.substring(i));
                String nh = h.substring(0, k) + h.substring(k+1);
                int r = go(nb, nh);
                if (r + 1 < best) best = r + 1;
            }
        seen.put(key, best);
        return best;
    }
    String reduce(String b) {
        int i = 0;
        while (i < b.length()) {
            int j = i;
            while (j < b.length() && b.charAt(j) == b.charAt(i)) j++;
            if (j - i >= 3) return reduce(b.substring(0, i) + b.substring(j));
            i = j;
        }
        return b;
    }
}

// DFS + memo on (board, sorted hand). Try every gap × distinct colour; collapse 3+ runs after each insert.
unordered_map seen;
string reduceBoard(string b) {
    int i = 0;
    while (i < (int)b.size()) {
        int j = i;
        while (j < (int)b.size() && b[j] == b[i]) j++;
        if (j - i >= 3) return reduceBoard(b.substr(0, i) + b.substr(j));
        i = j;
    }
    return b;
}
int go(string b, string h) {
    if (b.empty()) return 0;
    string key = b + "|" + h;
    if (seen.count(key)) return seen[key];
    int best = INT_MAX;
    for (int i = 0; i <= (int)b.size(); i++)
        for (int k = 0; k < (int)h.size(); k++) {
            if (k && h[k] == h[k-1]) continue;
            string nb = reduceBoard(b.substr(0, i) + h[k] + b.substr(i));
            string nh = h.substr(0, k) + h.substr(k+1);
            int r = go(nb, nh);
            if (r != INT_MAX) best = min(best, r + 1);
        }
    return seen[key] = best;
}
int findMinStep(string board, string hand) {
    sort(hand.begin(), hand.end());
    int ans = go(board, hand);
    return ans == INT_MAX ? -1 : ans;
}

Explanation

This is a search problem: each move inserts one hand ball somewhere on the board, runs of three or more same-coloured balls pop (which can chain), and we want the fewest inserts to clear everything. We explore moves with recursion and memoize repeated states.

The reduce helper does the popping. It scans for a run of equal colours; if a run has length >= 3 it removes it and calls itself again, so cascading collapses are handled automatically until the board is stable.

The main function go(b, h) returns the minimum inserts to clear board b using hand h. It tries every gap × every available colour: insert the ball, collapse with reduce, spend one hand ball, and recurse on the new state, taking 1 + the best result.

Because many move orders lead to the same (board, hand) situation, we cache answers in seen keyed by that pair. If no sequence clears the board, the result stays infinite and we return -1.

Example: board = "WRRBBW", hand = "RB". With only one extra R and one B, you can never build a run of three anywhere, so the board can't be cleared and the answer is -1.

Time: O((B+H)! · ...) Space: O(states)