Java Calling method with timeout

Question

I have a program that uses state-space searching algorithms (A*, IDA*, etc.) to solve some problem. I would like to run ~30-50 test iterations to get some information (average runtime, expanded nodes, etc.), but my issue is, sometimes these algorithms can take a very long time to solve the problem. I'd like to have the option to set a timeout on the method calls to limit the execution time (so I can for example run the tests overnight and have them finish reliably).

Assume the Solvers (classes implementing the algorithms) are provided as-is and cannot be altered. They are utilised by calling their solve method, which returns a List<Integer>.

This is the relevant piece of the code I'm currently using, courtesy of a similar thread here on stackoverflow:

int nTests = 50;
long timeout = 120;
double[] expandedAvg = new double[solvers.size()];        // averages of expanded nodes for each solver
int[] fails = new int[solvers.size()];        // number of timeouts for each solver

for (int i = 1; i <= nTests; i++) {
    int[][] problem = createProblem();         // creates a random solvable problem
    int j = 0;
    for (Solver solver : solvers) {
        boolean success = true;
        List<Integer> solution = null;

        if (timeout > 0) {
            Callable<List<Integer>> task = new Callable<List<Integer>>() {
                @Override
                public List<Integer> call() {
                    return solver.solve(problem);
                }
            };
            Future<List<Integer>> future = Executors.newCachedThreadPool().submit(task);
            try {
                solution = future.get(timeout, TimeUnit.SECONDS);
            }
            catch (TimeoutException e) {
                success = false;
                System.out.println("FAIL");
            }
            catch (InterruptedException ignore) {}
            catch (ExecutionException e) {
                e.printStackTrace();
            }
            finally {
                future.cancel(true);
            }
        }
        else solution = solver.solve(problem);

        if (success) {
            // update the average
            expandedAvg[j] = expandedAvg[j] + (solver.expanded - expandedAvg[j]) / (i - fails[j]);
        }
        else fails[j]++;

        j++;
    }
}

What ends up happening, however, is that after the first failed solve attempt, all further attempts fail as well. The issue appears to be that future.cancel(true) does not actually stop the execution of the solver (I'm basing this guess on the fact that the entire application does not terminate after the end of the outer loop, which means something is still running in another thread), which then hogs all the resources, and the successive ones don't get any CPU time (and consequently fail). If it matters, I'm running this from Eclipse.

Is there a way to ensure the threads get stopped when timed out? Or is there maybe another way of implementing timeouts I should use?