zuma game

XXX. Zuma Game

Backtracking

Recursion

Problem Statement:

You are playing a Zuma Game where you need to clear a board of colored balls by inserting new balls into the board. Each insertion of a ball reduces the consecutive sequence of three or more balls of the same color. The goal is to find the minimum number of balls to insert to clear the board, or return -1 if it's impossible.

Algorithm:

The algorithm uses backtracking with recursion to explore all possible moves and determine the minimum number of balls needed to clear the board:

1. Represent the player's hand as a frequency count of available balls.
2. Define a recursive helper function that:
   • Removes consecutive balls of three or more from the board.
   • Tries all possible positions to insert balls and calculates the number of moves required.
   • Backtracks by restoring the board and hand count.
3. Use a base case to terminate recursion when the board is empty, returning the number of moves.
4. If the board cannot be cleared, return -1.

Complexity:

Time Complexity: O(n!), where n is the length of the board due to the recursive exploration of all possible moves.
Space Complexity: O(n + m), where n is the board size and m is the size of the player's hand, for recursion stack and auxiliary space.

Java Implementation:

class Solution {
    int MAXCOUNT = 6;   // The maximum balls needed will not exceed 6

    public int findMinStep(String board, String hand) {
        int[] handCount = new int[26];
        for (int i = 0; i < hand.length(); ++i) 
            ++handCount[hand.charAt(i) - 'A']; // Count the number of each ball in hand

        int result = helper(board + "#", handCount);  // Append "#" to simplify processing
        return result == MAXCOUNT ? -1 : result;
    }

    private int helper(String s, int[] handCount) {
        s = removeConsecutive(s);  // Remove consecutive balls from the board
        if (s.equals("#")) return 0; // Base case: board is cleared

        int result = MAXCOUNT, need;
        for (int i = 0, j = 0; j < s.length(); ++j) {
            if (s.charAt(j) == s.charAt(i)) continue;

            need = 3 - (j - i); // Balls needed to remove the current sequence
            if (handCount[s.charAt(i) - 'A'] >= need) {
                handCount[s.charAt(i) - 'A'] -= need; // Use balls from hand

                // Recurse with the updated board
                result = Math.min(result, need + helper(s.substring(0, i) + s.substring(j), handCount));

                handCount[s.charAt(i) - 'A'] += need; // Backtrack: restore hand count
            }
            i = j; // Move to the next group of balls
        }
        return result;
    }

    // Remove consecutive balls longer than 3
    private String removeConsecutive(String board) {
        for (int i = 0, j = 0; j < board.length(); ++j) {
            if (board.charAt(j) == board.charAt(i)) continue;

            if (j - i >= 3) // Found a sequence of 3 or more
                return removeConsecutive(board.substring(0, i) + board.substring(j));
            else 
                i = j; // Move to the next group
        }
        return board;
    }
}