Sally wants more apples!

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 
 * @author Sergio Tomas (@Disruption)
 *
 */
public class SallyBetter {
    private static final int ROWS = 5;
    private static final int COLUMNS = 5;
    private static final int CACHE_SUB_NODE_MAX_SIZE = 6;

    //  0  1  2  3  4
    //  5  6  7  8  9
    // 10 11 12 13 14
    // 15 16 17 18 19
    // 20 21 22 23 24


    public static void main(String[] args) {
        long startTime = System.currentTimeMillis();
        List<Integer> availablePositions = new ArrayList<Integer>();
        Map<Integer, List<Integer>> nextAvailablePositions = new HashMap<>();
        Map<Integer, Map<List<Integer>, Integer>> cache = new HashMap<>();
        for (int i = 0; i < 25; i++) {
            // Available positions will be 0 to 24
            availablePositions.add(i);
            // Every node will know where it can go, so we avoid doing that calculations again and again and again..
            nextAvailablePositions.put(i, calculateNextPositions(i));
        }
        // We start from the center, position 12, so it's never available
        availablePositions.remove(12);

        // Branch starting from next node 17
        availablePositions.remove((Integer) 17);

        // Subbranch node 18, axial symmetry, so result must be multiplied by 2
        availablePositions.remove((Integer) 18);
        int result = 2*calculatePossiblePaths(18, availablePositions, nextAvailablePositions, cache);
        availablePositions.add((Integer) 18);

        // Subbranch node 13, axial symmetry, so result must be multiplied by 2
        availablePositions.remove((Integer) 13);
        result += 2*calculatePossiblePaths(13, availablePositions, nextAvailablePositions, cache);
        availablePositions.add((Integer) 13);

        // Subbranch node 23, axial symmetry, so result must be multiplied by 2
        availablePositions.remove((Integer) 23);
        result += 2*calculatePossiblePaths(23, availablePositions, nextAvailablePositions, cache);
        availablePositions.add((Integer) 23);

        // Subbranch node 22, no symmetry
        availablePositions.remove((Integer) 22);
        result += calculatePossiblePaths(22, availablePositions, nextAvailablePositions, cache);
        availablePositions.add((Integer) 22);

        // Base node switched from 17 to 18
        availablePositions.add((Integer) 17);

        // Process branch from node 18
        availablePositions.remove((Integer) 18);

        // Subbranch node 17, axial symmetry, so result must be multiplied by 2
        availablePositions.remove((Integer) 17);
        result += 2*calculatePossiblePaths(17, availablePositions, nextAvailablePositions, cache);
        availablePositions.add((Integer) 17);

        // Subbranch node 14, axial symmetry, so result must be multiplied by 2
        availablePositions.remove((Integer) 14);
        result += 2*calculatePossiblePaths(14, availablePositions, nextAvailablePositions, cache);
        availablePositions.add((Integer) 14);

        // Subbranch node 19, axial symmetry, so result must be multiplied by 2
        availablePositions.remove((Integer) 19);
        result += 2*calculatePossiblePaths(19, availablePositions, nextAvailablePositions, cache);
        availablePositions.add((Integer) 19);

        // Subbranch node 24, no symmetry
        availablePositions.remove((Integer) 24);
        result += calculatePossiblePaths(24, availablePositions, nextAvailablePositions, cache);

        System.out.println(4 * result);
        long time = System.currentTimeMillis() - startTime;
        System.out.println(time + " ms. " + (time / 1000) + " s.");

    }

    public static int calculatePossiblePaths(int currentPosition, List<Integer> availablePositions, Map<Integer, List<Integer>> nextAvailablePositions, Map<Integer, Map<List<Integer>, Integer>> cache) {
        // Base case, when we have an empty positions list, we found a combination
        if (availablePositions.size() == 0) {
            return 1;
        }

        int result = 0;
        List<Integer> candidates = nextAvailablePositions.get(currentPosition);

        for (Integer candidate : candidates) {
            if (availablePositions.contains(candidate)) {
                availablePositions.remove(candidate);
                Map<List<Integer>, Integer> subPaths = null;
                // Check if we have this subpath cached. If it is, add it's subresult and continue with the next candidate
                if (availablePositions.size() <= CACHE_SUB_NODE_MAX_SIZE && availablePositions.size() > 0) {
                    subPaths = cache.get(candidate);
                    Integer subResult = subPaths != null ? subPaths.get(availablePositions) : null;
                    if (subResult != null) {
                        result += subResult;
                        availablePositions.add(candidate);
                        continue;
                    }
                }
                int subresult = calculatePossiblePaths(candidate, availablePositions, nextAvailablePositions, cache);
                // If we are below or on the cache limit, cache this result so we don't recalculate this subtree anymore
                if (availablePositions.size() <= CACHE_SUB_NODE_MAX_SIZE) {
                    List<Integer> subNodes = new ArrayList<>();
                    subNodes.addAll(availablePositions);
                    if (subPaths != null) {
                        subPaths.put(availablePositions, subresult);
                    } else {
                        subPaths = new HashMap<>();
                        subPaths.put(availablePositions, subresult);
                        cache.put(candidate, subPaths);
                    }
                }
                result += subresult;
                availablePositions.add(candidate);
            }
        }

        return result;
    }

    // Calculates what positions can be reached from position i
    private static List<Integer> calculateNextPositions(int i) {
        int currentRow = i / COLUMNS;
        int currentColumn = i % COLUMNS;
        List<Integer> neighbours = new ArrayList<>();
        for (int col = -1 ; col < 2; col++) {
            for (int row = -1 ; row < 2; row++) {
                if (row != 0 || col != 0) {
                    int newRow = currentRow + row;
                    int newColumn = currentColumn + col;
                    if (newRow >= 0 && newRow < ROWS && newColumn >= 0 && newColumn < COLUMNS) {
                        neighbours.add(newRow * COLUMNS + newColumn);
                    }
                }
            }
        }
        return neighbours;
    }

}