solving 4 puzzle with tree

Question

I am trying to solve the 4 box puzzle problem. My logic according to my experience is every number is swap with space and then reaches to correct position.

i have this:

1 3
2

my goal state:

1 2
3

what am using the approach: (Key:R-> right, D->down; up->up; L->left)

                    1 3
                    2
                 R/         D|  up\   \L
                 /           |     \   \
               1 3          1      (not possible boundary exists)    
                 2          2 3

         R/  D|  up\   \L
         /    |     \   \ 
                3       1 3
              1 2       2
         ...............
        .................

Here is what i am doing but i am getting every time in some tree same state but not correct goal state. If i am using wrong tree approach or algorithm please tell me. Because i am implementing this sort of tree after studying through internet.

Answer 1

There is nothing wrong with algorithm. There just isn't a solution. There is no way to get from your initial situation to the end situation.

Answer 2

Not all instances of 4 puzzles will be solvable, the following figure shows the state-graph and as can be seen there are 2 connected components.

As shown in the above figure, the goal state (encoded as 0123) belongs to one of these components, all instances in this component will be solvable. From the other component, the goal state can't be reached, so none of those instances will be solvable.

We can solve 4-puzzle with Q-learning too, the above figure also shows the rewards formulation for the problem. More details can be found at https://sandipanweb.wordpress.com/2017/03/24/solving-4-puzzles-with-reinforcement-learning-q-learning-in-python/?frame-nonce=8531adb87d