I am trying to write an algorithm for solving RUBIK Race. It is a 5 * 5 board with each cell either having a color RED, WHITE, YELLOW, GREEN, BLUE, ORANGE or an EMPTY cell. ie, There will be 4 cells for each color, and 1 EMPTY cell. The cells on LEFT, RIGHT, TOP, BOTTOM of the EMPTY cell can be moved to the place of EMPTY cell, and thats how a change is made to the current arrangement of 5 * 5 board. Also there will be a 3 * 3 board which has a cube with the above mentioned colors in each of its cells. This 3 * 3 board is shuffled and the 5 * 5 board has to rearranged so that the center 3 * 3 sub matrix of 5 * 5 board must be equal to the 3 * 3 board. The RUBIK race is played between 2 players , and the first person to solve wins.
The detailed game rules are find below. This is the link for RUBIK's race https://www.rubiks.com/en-us/rubik-s-race.html
I started with a simple brute force algorithm which checks all possible states and when the desired state is reached it finds the list of movements made to the initial state of board. I have defined 4 types of movements for each state of 5 * 5 board. They are move LEFT, RIGHT, TOP, BOTTOM. The below picture will explain my algorithm.
As it is evident that this solution is absolutely inefficient. It checks all the possibilities. ie, for a 5 * 5 board possibilities are close to (25!)/ (4! * 4! * 4! * 4! * 4! * 4!).
I tried giving ranks to each child possibilities and consider only the possibility which has greater rank. Even that approach is also ineffecient.
What kind of optimisations are possible for this particular problem?