Find a more robust way of generating a board

[meszaros-lajos-gyorgy]

Currently the level generation is quite random, I'm essentially keep swapping tiles until I get a solved board. I need to find an algorithm that can generate a board without unnecessary tries.

Current algorithm:

1. generate a checkerboard pattern
2. swap 2 tiles randomly 100x times
3. set number of retries to 10k
4. keep swapping 2 tiles randomly and after every swap check if the number of incorrect fields is decreasing. If not, then undo swapping and decrease number of retries by 1
5. if we have a solved pattern then we're good to go, else if the number of retries > 0 then goto 4
6. if there are no more retries and the board is still not solved, then start over by going to 1

This algorithm gets really slow even at as low as 12x12