Grid Puzzle Split Algorithm
A possible technique to generate random tilings is:


Represent all possible solutions as a Zero Suppressed BDD (see for example The Art of Computer Programming volume 4, chapter 7.1.4, or this page). Every way to place any piece on the board corresponds to a variable in the ZDD. The constraints are that every tile is covered exactly once, which can be done by making an "exactly once"-ZDD for every tile, and then intersecting all those ZDDs. An "exactly once"-ZDD is easy to make, it's a single chain of nodes where a constrained variable (a piece-placement that covers this tile) corresponds to a node with a HI branch to TOP and a LO branch to the next node, and an unconstrained variable has both LO and HI going to the next node.
For each node in the ZDD, count how many solutions it leads to. Runs in time proportional to the size of the ZDD (not the number of solutions) if memoization is used.
Then, top down, randomly choose between the two children of a node using the ratio of solution counts as threshold. That would uniformly choose a random solution from the space of solutions. Runs in time proportional to the number of variables (depth of the ZDD).