patternjavaMinor

Java exhaustive solution

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

exhaustivesolutionjava

Problem

This is a take on Pebble Solitaire. The user inputs n number of games and after that inputs a strings of length 23 that contains a combinations of only 'o' (pebble) and '-' (empty space). If there are 2 adjacent pebbles and an empty space on either side, ie (oo- OR -oo), then you remove the middle pebble and you swap other two pieces with each other, ex 'oo-' will turn into '--o'.

My current approach is pretty much an exhaustive approach where it tries out every possible move and results the move set with the least number of pebbles left.

My program is working fine, in terms of output, but for some of my test cases it takes too long to find an answer (sometimes taking 18 seconds). I would like to know how I can improve the performance of my code without making it multithreaded.

```
package Pebble;

import java.util.Scanner;

public class PebbleSolitaire {

public static void main(String[] args){

Scanner input = new Scanner(System.in);
int numOfGames = Integer.parseInt(input.nextLine());

while (numOfGames > 0){

char[] values = input.nextLine().toCharArray();
long startTime = System.nanoTime();
System.out.println(solve(values));
System.out.println("Time to finish in ms: " + (System.nanoTime() - startTime) / 1000000);
numOfGames--;
}
input.close();
}

private static int solve(char[] game){

if(game != null && game.length == 0){
return -1;
}

int result = 0;

for (int i = 0; i = 0 && temp[i] == '-' && temp[i-2] == 'o' && temp[i-1] == 'o'){//move pebble forwards
temp[i-1] = temp[i-2] = '-';
temp[i] = 'o';
result = Math.min(result, solve(temp));
}

copyArray(temp, game);

if(i+2 < temp.length && temp[i] == '-' && temp[i+1] == 'o' && temp[i+2] == 'o'){//move pebble backwards
temp[i+1] = temp[i+2] = '-';

Solution

Don't copy the array

A lot of the time spent in your program is just making copies of the game array. Instead of copying the array, just use the same one. All you need to do is to undo the move you made after you are done recursing on it. In other words:

Make the move

Recursively solve

Undo the move

Don't count the number of o's

Another time waster is the part where you count the number of o's on every recursive call. Instead of doing that, just count the number once, at the very beginning. Then when you recurse, pass in the new count. The new count is always one less than the previous count because each move removes one o from the board.

Error check should only happen once

Similarly, this error checking:

if(game != null && game.length == 0){
        return -1;
    }

only needs to be done once. Having that code be in every recursive call is just slowing things down.

Memoization

Another thing that could be slowing your program down is the possibility that you are solving the same game states multiple times. For example, from the starting position, making move A followed by move B might end up in game state S1. But making move B followed by A might end up in the same state S1. Right now your program would solve the S1 state twice.

What you could do is to create an array (or Map) to record the answers to any state you have already solved. Since there are 23 spots, there are \$2^{23}\$ possible game states, or around 8 million. You can number each game state based on the binary number you get from the board, where - is a 0 and o is a 1. For example, --------------------o-o would translate to the binary number 00000000000000000000101, or 5. That would be the "index" of your game state.

After solving for a game state, you record the result in your array or Map. At the beginning of your function, you check the array/Map to see if the current position has already been solved, and just return the result if it has.

Also you can use bit tricks to compute the new game state index from the previous game state index, so you don't have to recompute it every time. For example, if the index is index, and you are making a move starting at index i, then the new game state index would be index ^ (0x7 Original program : 41000 ms
JS1 (no memo) : 1460 ms (28x faster)
JS1 (with memo) : 3 ms (480x faster than no memo)
`

Code Snippets

if(game != null && game.length == 0){
        return -1;
    }

import java.util.HashSet;
import java.util.Scanner;

public class pebble {
    private static final int MAX_GAME_LENGTH = 31;

    public static void main(String[] args)
    {
        Scanner input = new Scanner(System.in);
        int numOfGames = Integer.parseInt(input.nextLine());

        while (numOfGames > 0) {
            char[] values = input.nextLine().toCharArray();

            if (values.length > MAX_GAME_LENGTH) {
                System.out.println("Skipping game: too large");
                continue;
            }
            long startTime = System.nanoTime();
            System.out.println(solve(values));
            System.out.println("Time to finish in ms: " +
                    (System.nanoTime() - startTime) / 1000000);
            numOfGames--;
        }
        input.close();
    }

    private static int solve(char[] game)
    {
        int              gameState = 0;
        int              score     = 0;
        HashSet<Integer> visited   = new HashSet<Integer>();

        // Compute initial game state and score.
        for (int i=0;i<game.length;i++) {
            gameState <<= 1;
            if (game[i] == 'o') {
                gameState |= 1;
                score++;
            }
        }

        return solveHelper(gameState, score, visited, game.length);
    }

    private static int solveHelper(int gameState, int score,
            HashSet<Integer> visited, int gameLength)
    {
        int bestScore = score;

        visited.add(gameState);
        for (int i = gameLength-3; i >= 0; i--) {
            int trio = (gameState >> i) & 0x7;
            if (trio == 0x6 || trio == 0x3) {
                // 0x6: oo- -> --o
                // 0x3: -oo -> o--
                int mask         = ~(0x7 << i);
                int newGameState = (gameState & mask) | ((trio ^ 0x7) << i);
                if (!visited.contains(newGameState)) {
                    int ret = solveHelper(newGameState, score-1, visited,
                                            gameLength);
                    if (ret < bestScore)
                        bestScore = ret;
                }
            }
        }
        return bestScore;
    }
}

Context

StackExchange Code Review Q#148933, answer score: 4

Revisions (0)

No revisions yet.