Sorting Game

Given a random matrix of number, sort the matrix by moving only one block. The block that can be moved should be adjacent to empty block (denoted by 0) and the move direction has to be towards empty block. Valid moves can be up, down, left and right within the boundaries of matrix.

e.g.

Initial state

1	2	3
4	8	5
7	6	0

Result State

1	2	3
4	5	6
7	8	0

Matrix can be of size 3X3 or 4X4

Requirements

Expose a POST method with endpoint /sorting-game
Return an array of integers that represents each move in sequence that you have made to reach the final state
Call to your endpoint will timeout after 40 seconds
Only one block adjacent to 0 (empty block) can be moved (towards the empty block).
There can be multiple paths to solve the problem. Final score will depend on how far your solution is from the optimal solution. For a successful solution you will at least get a score of 10.

Input description

The HTTP POST request will come with a body of Content-Type: application/json

Sample Input and output

Input

{
  "puzzle":[
            [1,2,3],
            [4,8,5],
            [7,6,0] 
          ]
    }

Output

{
    "result": [6, 8, 5, 6]
}