Comment puis-je accélérer le processus sans le rendre multithread? - java, performance

Mon programme fonctionne bien, en termes de sortie,mais pour certains de mes cas de test, il faut trop de temps pour trouver une réponse (prenant parfois 18 secondes). J'aimerais savoir comment améliorer les performances de mon code.

Qu'est-ce que mon code fait: C'est une prise sur Galet solitaire. L'utilisateur entre n nombre de jeux et aprèsqui entre une chaîne de longueur 23 contenant une combinaison de "o" (caillou) et de "-" (espace vide). S'il y a 2 cailloux adjacents et un espace vide de chaque côté, c'est-à-dire (oo ou -oo), vous retirez le caillou du milieu et vous échangez les deux autres pièces l'une avec l'autre, ex "oo-" se transformera en "- o ".

Mon approche actuelle est plutôt une approche exhaustive, qui consiste à essayer chaque mouvement possible et à obtenir le jeu défini avec le moins de cailloux possible.

J'aimerais savoir comment améliorer cette solution sans la rendre multithread.

Voici ce que j'ai

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 < game.length; i++){
if(game[i] == "o"){
result++;
}
}

//print(game);

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

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

if (i-2 >= 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] = "-";
temp[i] = "o";
result = Math.min(result, solve(temp));
}
}
return result;
}

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

Mon exemple d'entrée et de sortie:

2
-o----ooo----o----ooo--
6
Time to finish in ms: 0
oooooooooo-ooooooooooo-
4
Time to finish in ms: 18149

EDIT: Le fait de rendre cette opération complètement itérative améliorerait-il considérablement les performances?

Réponses:

Peut-être que vous pouvez améliorer ce parte:

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

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

if (i-2 >= 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] = "-";
temp[i] = "o";
result = Math.min(result, solve(temp));
}
}

à:

    for (int i = 0; i < game.length; i++ ){
char[] temp = null;

if (i-2 >= 0 && game[i] == "-" && game[i-2] == "o" && game[i-1] == "o"){//move pebble forwards
temp = new char[game.length];
copyArray(temp, game);
temp[i-1] = temp[i-2] = "-";
temp[i] = "o";
result = Math.min(result, solve(temp));
}



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

if(temp == null) temp = new char[game.length];

copyArray(temp, game);
temp[i+1] = temp[i+2] = "-";
temp[i] = "o";
result = Math.min(result, solve(temp));
}
}

Fondamentalement, créer seulement et "copyArray (temp, jeu);" lorsque cela est strictement nécessaire.