How to apply backtracking for this type of problem?

My program solves a 4x5 sliding matrix puzzle with 10 pieces. (Print the solution, number of movements, time traveled, and parts path.)

Code:

importtimestart_time=time.time()importrandomclassPeca:def__init__(self,iniX,iniY,w,h):self.x=iniXself.y=iniYself.h=hself.w=wdefocupado(self):blocos=[]foriinrange(self.w):forjinrange(self.h):blocos.append([self.x+i,self.y+j])returnblocos#up,down,left,rightdefmoves_validos(self):valido=[]ifself.is_possible("U"):
        valido.append("U")
    if self.is_possible("D"):
        valido.append("D")
    if self.is_possible("L"):
        valido.append("L")
    if self.is_possible("R"):
        valido.append("R")

    return valido

def is_possible(self, sentido):
    possible = True
    self.move(sentido)
    for i in grid:
        for k, j in enumerate(i.ocupado()):
            if j in self.ocupado() and i != self:
                possible = False

    if self.x < 0 or self.x >= gridW:
        possible = False
    if (self.x + self.w) > gridW:
        possible = False
    if (self.y + self.h) > gridH:
        possible = False
    if self.y < 0 or self.y >= gridH:
        possible = False
    self.desfazer(sentido)

    return possible

def desfazer(self, sentido):
    if sentido == "U":
        self.y += 1
    elif sentido == "D":
        self.y -= 1
    elif sentido == "L":
        self.x += 1
    elif sentido == "R":
        self.x -= 1

def move(self, sentido):
    if sentido == "U":
        self.y -= 1
    elif sentido == "D":
        self.y += 1
    elif sentido == "L":
        self.x -= 1
    elif sentido == "R":
        self.x += 1

   gridW = 4
   gridH = 5
   grid = []
   grid.append(Peca(0, 0, 1, 2))
   grid.append(Peca(1, 0, 2, 2))
   grid.append(Peca(3, 0, 1, 2))
   grid.append(Peca(0, 2, 1, 2))
   grid.append(Peca(1, 2, 2, 1))
   grid.append(Peca(3, 2, 1, 2))
   grid.append(Peca(1, 3, 1, 1))
   grid.append(Peca(2, 3, 1, 1))
   grid.append(Peca(0, 4, 1, 1))
   grid.append(Peca(3, 4, 1, 1))

   def goal_reached():
   # square 2x2 at 1,3
   if [grid[1].x, grid[1].y] == [1, 3]:
    return True
   return False

   def print_grid(g):
   print("\n")
   for i in range(gridH):
    for j in range(gridW):
        for k, p in enumerate(g):
            if [j, i] in p.ocupado():
                print('[', k, ']', end='')
                break
            elif k == (len(grid) - 1):
                print('[ * ]', end='')
    print('\n', end='')

   def reset_grid():
   global grid
   grid = []
   grid.append(Peca(0, 0, 1, 2))
   grid.append(Peca(1, 0, 2, 2))
   grid.append(Peca(3, 0, 1, 2))
   grid.append(Peca(0, 2, 1, 2))
   grid.append(Peca(1, 2, 2, 1))
   grid.append(Peca(3, 2, 1, 2))
   grid.append(Peca(1, 3, 1, 1))
   grid.append(Peca(2, 3, 1, 1))
   grid.append(Peca(0, 4, 1, 1))
   grid.append(Peca(3, 4, 1, 1))

   print("Movendo as peças aleatoriamente...(please wait)")

   solucao = []
   while True:
   x = random.randint(0, len(grid) - 1)
   if len(grid[x].moves_validos()) > 0:
    y = random.randint(0, len(grid[x].moves_validos()) - 1)
    solucao.append([x, grid[x].moves_validos()[y]])
    grid[x].move(grid[x].moves_validos()[y])

    if goal_reached():
        print_grid(grid)
        print()
        print("Quantidade de movimentos:", len(solucao))
        print()
        print("Tempo: {:.2f}s".format(time.time() - start_time))
        print()
        print("Caminho para a solução:", solucao)
        solucao = []
        break

    """ posição inicial
    [ 0 ][ 1 ][ 1 ][ 2 ]
    [ 0 ][ 1 ][ 1 ][ 2 ]
    [ 3 ][ 4 ][ 4 ][ 5 ]
    [ 3 ][ 7 ][ 8 ][ 5 ]
    [ 6 ][ * ][ * ][ 9 ]
    """ 

Running on repl: link

The method I used was the "random walk", but I see that it is not as efficient as a puzzle like this in that the exact solution is 81 movements only, starting from the concept that each piece can move more than once and will only count 1 movement, (without this rule the exact amount of movements would be 118.) the program finds the solution with a much larger range of movements than expected ...

Some examples of solutions:

Movements: 700 thousand
movements: 300 thousand
movements: 80 thousand
movements: 40 thousand

The solution time of the program is between 5 to 10 minutes ...
I would like the program to be solved in a faster way.