Java exhaustive solution 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 &gt; 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 &amp;&amp; game.length == 0){
            return -1;
        }

        int result = 0;

        for (int i = 0; i &lt; game.length; i++){
            if(game[i] == 'o'){
                result++;
            }
        }

        //print(game);

        for (int i = 0; i &lt; game.length; i++ ){

            char[] temp = new char[game.length];
            copyArray(temp, game);

            if (i-2 &gt;= 0 &amp;&amp; temp[i] == '-' &amp;&amp; temp[i-2] == 'o' &amp;&amp; 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 &lt; temp.length &amp;&amp; temp[i] == '-' &amp;&amp; temp[i+1] == 'o' &amp;&amp; temp[i+2] == 'o'){//move pebble backwards
                temp[i+1] = temp[i+2] = '-';
                temp[i] = 'o';
                result = Math.min(result, solve(temp));
            }
        }
        return result;
    }

    private static void copyArray(char[] copy, char[] og){
        for(int x = 0; x &lt; copy.length; x++){
            copy[x] = og[x];
        }
    }
    private static void print(char[] c){
        for(char ch: c){
            System.out.print(ch);
        }
        System.out.println();
    }
}


My sample input and output:



2
-o----ooo----o----ooo--
6
Time to finish in ms: 0
oooooooooo-ooooooooooo-
4
Time to finish in ms: 18149
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 &amp;&amp; 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 &lt;&lt; (20-i)).  This is because you are flipping the board positions at the three bits starting at 20-i.

This memoization is probably going to help speed up your program more than the other tips, because it will cut entire branches off your search space instead of just speeding up your program by a flat percentage.

Sample rewrite

I used the ideas above to rewrite your program.  For the memoization part, I chose to use a HashSet to remember which game states were already visited.  I found that there was no need to actually remember the score for previously visited states (hence the Set and not a Map).

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 &gt; 0) {
            char[] values = input.nextLine().toCharArray();

            if (values.length &gt; 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&lt;Integer&gt; visited   = new HashSet&lt;Integer&gt;();

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

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

    private static int solveHelper(int gameState, int score,
            HashSet&lt;Integer&gt; visited, int gameLength)
    {
        int bestScore = score;

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


Optimizations helped a lot

I ran three programs to solve the difficult board.  The first was the original program.  The second was a variant of my program with the visited set removed to test how much of a difference the memoization made.  The third was my sample rewrite program unmodified.  Here are the results:

Original program : 41000 ms
JS1 (no memo)    :  1460 ms (28x  faster)
JS1 (with memo)  :     3 ms (480x faster than no memo)