CareerCup

After googling few helpful links;
1) https://stackoverflow.com/questions/32442837/minimum-number-of-steps-to-sort-3x3-matrix-in-a-specific-way
2) https://en.wikipedia.org/wiki/A*_search_algorithm
3) https://en.wikipedia.org/wiki/15_puzzle
Basically it is a modification of Dijkstra algorithm, every move of empty box at every stage will give at max 4 new states -- consider these states as neighbours. Thus every state has max 4 neighbours and we can then do a BFS on them to find the state which is sorted and combined with Dijkstra logic will give us minimum steps.

public class Solution {
  public List<Point> getPathToSort(Integer[][] matrix) {
    Point p = new Point();
    p.row = matrix.length - 1;
    p.col = matrix[0].length - 1;
    Board initialBoard = new Board(matrix, null, p);

    Set<Board> closedSet = new HashSet<>();
    // it must be a min priority queue since the board with minimum cost should be first
    PriorityQueue<Board> minQueue = new PriorityQueue<>(new BoardComparator());
    minQueue.add(initialBoard);
    // most important part of the program as this has the main logic, very similar to BFS
    while(!minQueue.isEmpty()) {
      Board b = minQueue.dequeue();
      closedSet.add(b);
      List<Board> neighbours = this.getAllAdjacentBoards(b);
      // Iterate throught all the neighbours and add them to the queue or replace the existing board with new minimum
      // cost board.
      for(Board neighbour : neighbours) {
        if(neighbour.isSolved()) {
          return neighbour.getPath();
        }
        else if(closedSet.contains(neighbour)) {
          continue;
        }
        else if(!minQueue.contains(neighbour)) {
          minQueue.add(neighbour);
          continue;
        }
        // This means we have seen this board before thus find if this neighbour has less cost or existingItem and
        // replace if neccessary
        int newCost = neighbour.getBoardCost();
        Board existingItem = minQueue.remove(neighbour);
        int existingCost = existingItem.getBoardCost();
        minQueue.add(existingCost < newCost ? existingItem : neighbour);
      }
    }
    return null;
  }

  private List<Board> getAllAdjacentBoards(Board b) {
    List<Board> result = new ArrayList<>();
    Board b = this.getBoardAfterMove("left", b);
    if(b != null) {
      result.add(b);
    }
    b = this.getBoardAfterMove("top", b);
    if(b != null) {
      result.add(b);
    }
    b = this.getBoardAfterMove("right", b);
    if(b != null) {
      result.add(b);
    }
    b = this.getBoardAfterMove("bottom", b);
    if(b != null) {
      result.add(b);
    }
    return result;
  }

  private Board getBoardAfterMove(String direction, Board b) {
    Point newEmptyBoxPoint = b.emptyBoxPosition.getAdjacentPoint(direction, b.matrix);
    if(newEmptyBoxPoint == null) {
      return null;
    }
    Integer[][] newState = this.swapPositions(b.matrix, b.emptyBoxPosition, newEmptyBoxPoint);
    Board b = new Board(newState, b, newEmptyBoxPoint);
    return b;
  }

  private Integer[][] swapPositions(Integer[][] matrix, Point p1, Point p2) {
    Integer[][] newState = new Integer[matrix.length][matrix[0].length];
    for(int i = 0; i < matrix.length; i++) {
      for(int j = 0; j < matrix[0].length; j++) {
        if(i == p1.row && j == p1.col) {
          newState[i][j] = matrix[p2.row][p2.col];
        }
        else if(i == p2.row && j == p2.col) {
          newState[i][j] = matrix[p1.row][p1.col];
        }
        else {
          newState[i][j] = matrix[i][j];
        }
      }
    }
    return newState;
  }

  ////////////////////////////////////////////////////////////////////////////////////////
  public static class Board {
    public Board previousBoard;
    public Integer[][] matrix;
    public Point emptyBoxPosition;
    public int stepsTakenSoFar;
    public Board(Integer[][] newState, Board oldBoard, Point emptyBoxPosition) {
      this.previousBoard = oldBoard;
      this.matrix = newState;
      this.stepsTakenSoFar = oldBoard == null ? 0 : this.previousBoard.stepsTakenSoFar + 1;
      this.emptyBoxPosition = emptyBoxPosition;
    }

    public List<Point> getPath() {
      List<Point> path = new ArrayList<>();
      while(previousBoard != null) {
        path.addAll(previousBoard.getPath());
      }
      path.add(emptyBoxPosition);
      return path;
    }

    public boolean equals(Object o) {
      if(o == null || !(o instanceof Board)) {
        return false;
      }
      Board b = (Board)o;
      for(int i= 0; i < matrix.length; i++) {
        for(int j = 0; j < matrix[0].length; j++) {
          if(matrix[i][j] != b.matrix[i][j]) {
            return false;
          }
        }
      }
      return true;
    }

    public int hash() {
      return this.matrix.hash();
    }

    public boolean isSolved() {
      return this.getNumbersOfBlockInWrongPosition() == 0;
    }

    public int getNumbersOfBlockInWrongPosition() {
      for(int i= 0; i < matrix.length; i++) {
        for(int j = 0; j < matrix[0].length; j++) {
          if(matrix[i][j] != i*j + j) {
            count++;
          }
        }
      }
      return count;
    }

    public int getBoardCost() {
      return this.getNumbersOfBlockInWrongPosition() + this.stepsTakenSoFar;
    }
  }

  ////////////////////////////////////////////////////////
  public static class Point {
    public int row;
    public int col;

    public Point getAdjacentPoint(String direction, Integer[][] matrix) {
      Point p  = new Point();
      p.row = this.row;
      p.col = this.col;
      switch(direction) {
        case "top":
        if(p.row >= 1) {
          p.row--;
          return p;
        }
        break;
        case "right":
        if(p.col <= matrix[0].length - 2) {
          p.col++;
          return p;
        }
        break;
        case "bottom":
        if(p.row <= matrix.length - 2) {
          p.row++;
          return p;
        }
        break;
        case "left":
        if(p.col >= 1) {
          p.col--;
          return p;
        }
        break;
        default: return null;
      }
      return null;
    }
  }

  //////////////////////////////////////////////////////
  public static class BoardComparator implements Comparator<Board> {
    public int compare(Board b1, Board b2) {
      return b1.getBoardCost() - b2.getBoardCost();
    }
  }
}

Solution in python. Cost O(k^n).
This is a brute force solution with no heuristics so it is not very efficient, make sure there is a solution or it will loop forever.
Some heuristics may include don't make a movement if you are increasing the total number of disordered pieces or putting adjacent numbers together even if they are not in the right posisition
Example:
solveMaze([[2,3], [1, 'x']])
([[1, 2], [3, 'x']], [(1, 1), (0, 1), (0, 0), (1, 0), (1, 1)])

from itertools import chain
    
def isSolution(m):
    x = list(chain.from_iterable(m))
    for p in xrange(len(x)-1):
        if x[p] > x[p+1]:
            return False
    return True

def swapMatrix(m, s1, s2):
    temp = m[s1[0]][s1[1]]
    m[s1[0]][s1[1]] = m[s2[0]][s2[1]]
    m[s2[0]][s2[1]] = temp
    
def computeSuccessors(s1, top, l):
    res = []
    for p in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
        s = (s1[0] + p[0], s1[1] + p[1])
        if s[0] < 0 or s[0] >= top or\
            s[1] < 0 or s[1] >= top or s == l:
                continue
        res.append(s)
    return res
    
def solveMaze(m):
    frontier = [(m, [(len(m) -1, len(m) - 1)], (len(m) -1, len(m) - 1))]
    while len(frontier):
        m, s, l = frontier.pop(0)
        s1 = s[-1]
        if isSolution(m):
            return (m, s)
        for s2 in computeSuccessors(s1, len(m), l):
            swapMatrix(m, s1, s2)
            frontier.append(([r[:] for r in m], s[:] + [s2], s1))
            swapMatrix(m, s1, s2)
    
    return None