10651 – Pebble Solitaire (UVa)

by afruizc

The problem statement can be found here.

Problem description:
This problem is a particularization of the pebble game. In this problem you have a set of marbles and play according to some established rules. Suppose there two marbles: one at position i and the other at position i+1. You can eliminate the marble at position i+1 by hopping the marble at position i over it. Hopping  marble means moving the one that is in position i to position i+2 (i+1 is the position of the other marble). In this problem you are given a description of this game consisting of 12 spaces and some of them are filled with marbles. You should determine the minimum number of marbles that will be left after a series of movements of the marbles. A marble can hop either left or right, if there is another adjacent at marble i-1 or i+1, respectively.

Analysis:
Suppose there is a marble at position i and another marble at position i+1. Also suppose that positions i-1 and i+2 are valid positions. In this case, there are two possible movements, every movement will left one marble in the board. You can either move the marble located at i to position i+2, thus, eliminating the marble at position i+1, or you can move the marble at position i+1 to i-1, thus, eliminating the marble at position i.

Solution:
The solutions consist on using backtracking to solve the movement of the marbles. You should check for every marble, first if it can be moved. If a marble can be moved to both directions (left and right) try both possibilities, generating a new scenario for every move. That means, after performing one move (left or right), recurse so that you will get an answer based on that decision. Repeat this process for all the marbles that can be moved, and minimize the value at every ending state. i.e An ending state means that there aren’t anymore moves to perform.

Implementation:

#include <cstdio>
#include <algorithm>

using namespace std;

char line[13];
int T, p;

bool can() {
    for (int i=0 ; i<11 ; i++)
        if (line[i] == 'o' && line[i+1] == 'o') return true;
    return false;
}

int solve(int q) {
    if (!can()) {
        // puts(line);
        // printf("%d\n", q);
        return q;
    }
    else {
        int mn, izq, der;
        mn = p;
        for (int i=0 ; i<11 ; i++) {
            if (line[i] == 'o' && line[i+1] == 'o') {
                izq = der = p;
                if (i-1 >= 0 && line[i-1] == '-') {
                    line[i-1] = 'o';
                    line[i] = '-';
                    line[i+1] = '-';
                    izq = solve(q-1);
                    line[i-1] = '-';
                    line[i] = 'o';
                    line[i+1] = 'o';
                }
                if (i+2 < 12 && line[i+2] == '-') {
                    line[i+2] = 'o';
                    line[i+1] = '-';
                    line[i] = '-';
                    der = solve(q-1);
                    line[i+2] = '-';
                    line[i+1] = 'o';
                    line[i] = 'o';
                }

                mn = min(mn, min(izq, der));
            }
        }
        return mn;
    }
}

int main() {
    scanf("%d\n", &T);
    while (T--) {
        gets(line);
        p=0;
        for (int i=0 ; i<12 ; i++) if (line[i] == 'o') p++;
        printf("%d\n", solve(p));
    }
}