title: Rubik race solving algorithm
body: <p>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.</p>
  <p>The detailed game rules are find below.
  This is the link for RUBIK's race <a href="https://www.rubiks.com/en-us/rubik-s-race.html" rel="nofollow noreferrer">https://www.rubiks.com/en-us/rubik-s-race.html</a></p>
  <p>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.</p>
  <p><a href="https://i.stack.imgur.com/uuVdD.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/uuVdD.png" alt="enter image description here" /></a></p>
  <p>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!).</p>
  <p>I tried giving ranks to each child possibilities and consider only the possibility which has greater rank. Even that approach is also ineffecient.</p>
  <p>What kind of optimisations are possible for this particular problem?</p>