Solving some kind of sequential move puzzle on 2D trapezoid grid

Question

I am trying to write a solver algorithm for the following puzzle.

I could not find a similar puzzle in the search. Probably such a puzzle already existed before, I will be grateful if someone tells me its name or in what direction to look.

The field is a hex-like grid with the number of cells in the bottom row FieldWidth and number of rows FieldHeight (hex grid). Each row above contains one cell less than the bottom row, e.g.:

       .   .   .   .
     .   .   .   .   .
   .   .   .   .   .   .
 .   .   .   .   .   .   .

where '.' is field cell

There are balls on the field, the number of colors NumberOfColors = FieldHeight: one ball of color 1, two balls of color 2, ... N balls of color N (N = NumberOfColors)

The ball can be on the bottom row or on top of two balls.

Puzzle example:

LEGEND
------

   . - empty cell
1..N - cell containing ball with specified color id

       .   .   .   .
     2   .   .   .   .
   3   4   .   .   1   .
 2   4   3   3   4   4   .

The objective of the puzzle is to assemble a triangle from balls, each row of which contains balls of the same color, obeying the following rules:

• Only one ball can be moved at a time.
• The ball can be moved if 2 adjacent cells from the row above are empty.
• The ball can be moved to a free cell in the bottom row or to a free cell if 2 adjacent cells of the lower row contain balls.
• After moving the ball from the extreme cell of the bottom row, it is destroyed and becomes inaccessible until the end of the game. After that, the same rules apply to the new extreme cells of the bottom row.

That is, the goal of the game is to arrange the balls in the following order:

       1
     2   2
   3   3   3
 4   4   4   4

Puzzle and solution example:

LEGEND
------

   . - empty cell
1..N - cell containing ball with specified color id
   x - destroyed cell
 [ ] - marking cells involved in move


THE INITIAL STATE
-----------------

       .   .   .   .
     2   .   .   .   .
   3   4   .   .   1   .
 2   4   3   3   4   4   .


SOLVING
-------

MOVE 1
       .   .   .   .
     2   .   .   .   .
   3   4   .   .  [.]  .
 2   4   3   3   4   4  [1]

MOVE 2
       .   .   .   .
    [.]  .   .   .   .
   3   4   .   .   .  [2]
 2   4   3   3   4   4   1

MOVE 3
       .   .   .   .
     .   .   .   .   .
  [.]  4   .   .  [3]  2
 2   4   3   3   4   4   1

MOVE 4
       .   .   .   .
     .   .   .   .  [3]
   .   4   .   .   3   2
 2   4   3  [.]  4   4   1

MOVE 5
       .   .   .   .
     .   .   .   .   3
   .  [.]  .   .   3   2
 2   4   3  [4]  4   4   1

MOVE 6
       .   .   .   .
     .   .   .   .   3
   .   .   .  [3]  3   2
 2   4  [.]  4   4   4   1

MOVE 7
       .   .   .   .
     .   .   .  [2]  3
   .   .   .   3   3   2
[x]  4   .   4   4   4   1

MOVE 8
       .   .   .   .
     .   .   .   2   3
   .   .   .   3   3   2
 x  [x] [4]  4   4   4   1

MOVE 9
       .   .   .   .
     .   .   .   2  [.]
   .   .  [3]  3   3   2
 x   x   4   4   4   4   1

MOVE 10
       .   .   .   .
     .   .  [2]  2   .
   .   .   3   3   3  [.]
 x   x   4   4   4   4   1

MOVE 11
       .   .  [1]  .
     .   .   2   2   .
   .   .   3   3   3   .
 x   x   4   4   4   4  [x]

My current algorithm is fairly straightforward and rough, in short it is like this:

• search for all options of the first move, the state is saved after each of them
• for each subsequent move, restore each state of the previous move and do all the possible moves, and save all the states
• field is checked for a solution after each move
• after the move, it is checked if such a state already existed before, then the search does not continue on this branch

This approach works acceptable for me for a field with a height of 4 and a width of 7 with 10 balls (as in the examples above), but already with a field of height 5 and a width of 9 with 15 balls, there is a problem of running out of RAM on my machine (32 GB) after about 13 move. Each state takes 2 long values ​​(128 bits).

I would be grateful for tips on the solution algorithm, probably there is a smarter way to do this.