We had this question at our Internship test
Given a matrix 3 by 3 considering of numbers from 1 to 9 (all numbers are present and randomly arranged)
Example
2 5 7
1 4 3
6 8 9

Convert this matrix into the below matrix

1 2 3
4 5 6
7 8 9

You are allowed to swap adjacent tiles (tiles that share a common side), but only on the condition that sum of the numbers on the tiles should be prime
For example: In above example you can swap tile with 2 and tile with 5 with each other, but tile with 6 and tile with 8 can't be swapped with each other
Find the minimum number of steps needed to get to the desired state

I was thinking of something along the lines of Backtracking but couldn't come up with a correct solution, how would you approach it?