kstheking's blog

Cisco Internship Question — Arrange the matrix
By kstheking, history, 4 years ago, In English

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?

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

https://www.codechef.com/problems/H1 i think u are talking about thisYour text to link here...

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply