If it is randomly generated, half of the puzzles are unsolvable.

Oh, it's totally solvable, but it's tricky! You kind of have to strategically "snake" the letters around a bit to sequentially place them in the right spots - you get less and less room to do so as you place more and more tiles.

Unfortunately it is not solvable. See this blog post on how to programmatically check for solvability:

https://datawookie.dev/blog/2019/04/sliding-puzzle-solvable/