You could start from a pre-made template - for instance the one you posted - then start randomly moving and swapping pieces to different (random but valid) locations. This would be similar in concept...