Breadth First Search Causing Heap Memory Error With exponentially growing graph

Question

I am writing a breadth first search to find a winning move for a block slider board game (image of example below)

The game aims to move pieces out of the way so the red piece can exit the stage.

This is for demonstration purposes, and I have already implemented a depth first approach.

I am fine with only being able to retrieve the winning sequence of moves once the "winning" move has been found.

The problem with the approach shown below is that I get a heap memory error (I have allocated 8gb in Intellij). The scale of the problem is quite large. I don't know how to reduce the number of objects created throughout the program, as its evident that this scales quite quickly with an average number of movements available per "turn" being 10, so with a max depth of 10 its more than 10^10 objects being created worst-case which is quite substantial.

This game presents many options for movements. I have chosen to represent these movements with the following class:

public class MadeMove {

private BoardPiece[][] boardState; // usually a copy of a stored board, including all the pieces inside it
private BoardPiece pieceMoved; // usually a copy 
private MovementCoordinate movementMade; // contains information about whether the move is a "winning" move aka red slider moves out of box.
private boolean initialMove = true; // is the first move
private int boardSize; // for searching purposes
private MadeMove lastMove; // the last move made before this one, forms a chain

public MadeMove(BoardPiece[][] board, int boardSize, BoardPiece pieceMoved, MovementCoordinate movementMade) {
    this.boardSize = boardSize;
    this.pieceMoved = pieceMoved;
    this.movementMade = movementMade;
    boardState = board;
}

public MadeMove(BoardPiece[][] board, int boardSize, BoardPiece pieceMoved, MovementCoordinate movementMade, MadeMove lastMove) {
    this.boardSize = boardSize;
    this.pieceMoved = pieceMoved;
    this.movementMade = movementMade;
    boardState = board;
    initialMove = false;
    this.lastMove = lastMove;
}

}

This is the main building block for my breadth first algorithm which is as follows:

public class BreadthFirstSolver {


public Optional<MadeMove> solveForWinningMove(BlockSliderBoardHandler handler, int maxDepth){
    return breadthFirstSearchStart(handler,maxDepth);
}

private Optional<MadeMove> breadthFirstSearchStart(BlockSliderBoardHandler handler, int maxDepth){
    Set<BoardPiece> moveablePieces = handler.getMoveablePieces();

    HashMap<BoardPiece, List<MovementCoordinate>> pieceToMovements = new HashMap<>();

    for (BoardPiece piece : moveablePieces) {
        pieceToMovements.put(piece, handler.getPossibleMovements(piece));
    }

    Queue<MadeMove> moveQueue = new ArrayDeque<>();

    BoardPiece[][] initialBoardState; // for resetting the board if altered
    // this initialises the breadthFirstSearch
    for (Map.Entry<BoardPiece, List<MovementCoordinate>> entry : pieceToMovements.entrySet()) {
        for (MovementCoordinate movement : entry.getValue()) {
            initialBoardState = handler.copyBoardStateEntirely(); // makes sure the initial board state is forever fresh
            BoardPiece pieceCopy = entry.getKey().getCopy();
            assert (entry.getKey().equals(pieceCopy));
            handler.movePiece(pieceCopy, movement);
            MadeMove tempMove = new MadeMove(handler.copyBoardStateEntirely(), handler.getBoardSize(), pieceCopy, movement);

            moveQueue.add(new BreadthMadeMoveAssistor(tempMove));
            handler.setNewBoard(initialBoardState);
        }
    }

    while (!moveQueue.isEmpty()){
        MadeMove tempMove = moveQueue.remove();

        if (!tempMove.isInitialMove()){
            int depthCount = 0;
            MadeMove moveIteration = tempMove.getLastMove();
            while (!moveIteration.isInitialMove()){
                depthCount++;
                if (depthCount >= maxDepth-1){
                    return Optional.empty();
                }
                moveIteration = moveIteration.getLastMove();
            }
        }


        if (tempMove.isWinningMove()){
            return Optional.of(tempMove);
        }
        moveQueue.addAll(breadthFirstSearch(handler,tempMove));

    }
    return Optional.empty();
}

private List<MadeMove> breadthFirstSearch(BlockSliderBoardHandler handler, MadeMove lastMove){
    handler.setNewBoard(lastMove.getBoardState());
    Set<BoardPiece> moveablePieces = handler.getMoveablePieces();

    HashMap<BoardPiece, List<MovementCoordinate>> pieceToMovements = new HashMap<>();

    for (BoardPiece piece : moveablePieces) {
        pieceToMovements.put(piece, handler.getPossibleMovements(piece));
    }

    List<MadeMove> nextMoves = new ArrayList<>();

    BoardPiece[][] initialBoardState;
    for (Map.Entry<BoardPiece, List<MovementCoordinate>> entry : pieceToMovements.entrySet()) {
        for (MovementCoordinate movement : entry.getValue()) {
            initialBoardState = handler.copyBoardStateEntirely(); // makes sure the initial board state is forever fresh
            BoardPiece pieceCopy = entry.getKey().getCopy();
            assert (entry.getKey().equals(pieceCopy));
            handler.movePiece(pieceCopy, movement);
            MadeMove tempMove = new MadeMove(handler.copyBoardStateEntirely(), handler.getBoardSize(), pieceCopy, movement, lastMove);
            nextMoves.add(tempMove);
            handler.setNewBoard(initialBoardState);
        }
    }

    return nextMoves;
}

}