Here's a solver for the puzzle (uses the clingo ASP solver): http://www.takingthefun.com/2015/02/0hn0com-solver.html

Using the solver, I calculated that an empty 2x2 puzzle can be solved in 10 different ways, an empty 3x3 puzzle can be solved in 250 different ways, and an empty 4x4 puzzle can be solved in in 22946 different ways.