How to find an algorithm for solving Shishnashka's puzzle?

Question

Android

I made an android clone of the Shishnashka game - habrahabr.ru/post/269391 , but I just can’t figure out how to solve the puzzle. Sometimes it turns out to collect, but not all layouts. The problem with the permutation of two numbers also cannot be solved (problem 1 in the article), but just such a situation occurs in the end most often.
The only thing that comes to mind is to go through all the permutation options, somehow remember the sequence for each option and compare the current layout with a table of ready-made solutions. But it seems to me that the volume of all this will be somehow unrealistic. Surely there is a better solution. Is it possible to go through the options for solving not all the tiles, but only half of them?...
I want to finish the game, but without the hint function, the game turns out to be inferior.

Answer 1

So there are only two layout options and they do not go into each other in any way