We had this question at our Internship test

Given a matrix 3 by 3 consisting 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?

Auto comment: topic has been updated by kstheking (previous revision, new revision, compare).https://www.codechef.com/problems/H1 i think u are talking about thisYour text to link here...

It is possible to binary search the answer and use brute-force to check whether the answer exists.

Isn't this the problem H1 from codechef? https://youtu.be/Sws3RFteHzo