I was about to ask you this, haha. How long took you to notice?
I read a guide on how to solve 8-puzzle, and even with the guide I couldn't solve it. So I went to the math of it, and read an article[1] that gives a proof if a board is solvable or not.
Dumb me! The way I was creating the board I would make it unsolvable with a even board (4x4). The 3x3 and 5x5 were fine.
The bug is fixed. Sorry about that. I'm laughing so hard because even I couldn't solve any 4x4 games.
I solved all of them except last 2 pieces, next 15-20 minutes made me sure that something has gone wrong. I decided to read more about these puzzles and knew that they're unsolvable in 50% cases.