Algorithms (methods) to solve a particular puzzle

[Gabry501]

Hello everyone, I'm new here and I just sign up cause I thought this would be the best place to solve my doubt.
If that's the wrong section or wrong place at all, just point it out and maybe give me some directions.

I'v been developing a simple game that consists of a game similar to a sliding puzzle.
I create a matrix (actually a table) of numbers, shuffle and re-order them using few restrictions.

To order them:
I allow placing an external element beside another side-element of the matrix (or even on top/bottom)
Then pushing it and letting the element on the opposite side going out
E.g. on a 3x3 matrix
external = X
7 8 9
4 5 6
1 2 3
Placing and pushing the X beside the 7:
x 7 8
4 5 6
1 2 3
external = 9

Till now I realized that some situations are not possible to solve if I simply shuffle the numbers.
I was wondering if it would be possible to get an algorithm to find if a puzzle has a solution, or to find out how to achieve a specific movement.
Eg.
from
12
34
How can I obtain:
14
32

I tried looking around for similar puzzles without achieving much. I guess I don't have enough mathematical competencies but I would like to find out more about it.

P.s. If I was not clear enough, and I'm allowed to post links without spamming you can have a look at the images of the real game here which are not represented by numbers, but by parts of an image.

 

[mDiPalma]

you are right, there are a couple of impossible permutations in the puzzle you describe. on your 2x2 example, every swap you do is a 3-cycle (3 numbers are being swapped, eg: X goes to 1 which goes to 2 which goes to X). and in a general NxN puzzle, every swap you do is an "N+1 cycle."

when you are asking to switch numbers 4 and 2, in your example, that is a 2-swap (2 goes to 4 and 4 goes to 2), and no combination of the 3-cycles you defined can create that position. there is a similar problem on a rubik's cube - where a 2-swap of corners is impossible.

you need to add more operations to make these impossible states solvable. maybe some mirror operation (flip the order of a row or a column) would be sufficient. not sure... trial and error might be the easiest way to find out.

good luck!

also, instead of checking if a random shuffle is solvable - why don't you just shuffle the solved picture to a scrambled state? then it will always be solvable. that is probably what you already do

 

[Gabry501]

Thanks for the answer,
Right now, the shuffling operation consists of moving the tiles emulating one of the allowed movement.
Playing the game, however, I found myself in 3x3 or 4x4 puzzles in situations in which I needed a 2-swap movement and I didn't manage to do it, even if for sure it was possible. Thus, I would like to know if there is a possible algorithm to achieve such kind of swaps.

P.s. It would be interesting to know if such a similar puzzle already exists, I didn't manage to find one, but it's not something too complex.

 

[mDiPalma]

what is the method for solving this type of puzzle? solving in rows until the last section?

and what type of 2-swap cases do you get on a 3x3? can you show me an example?


a similar puzzle would be this: https://en.wikipedia.org/wiki/15_puzzle but it doesn't have your external element, and the moves are slightly different

 

[Gabry501]

I usually solve it by columns (or rows) but always some elements are misplaced in the last column.
Here some examples:

Spoiler: Examples

Here I need to swap the external element (the boat) with the right-bottom.

Or here instead, the top left corner with the top center one. (The external is the "drag me")