Tetronimo Tiling with given tiles : How to eliminate early cases where no solution exist I've created a javascript block puzzle solver, that finds the solution to  tetronimo based block puzzle on a user-defined X*Y sized board. 
My issue is that I'd like to avoid calculation altogether if there is a mathematical formula or some approach that can quickly determine if the puzzle is solvable. 
There is no point in wasting computer power on running brute force process of testing all tetrominoes if the board has no solution. 
So, for example, in this case, I have selected 8 Blocks: J,J,L,L,O,O,O,O and board dimensions of 8 x 4. I've calculated the solution by going through all possible combination. Similarly, I'd like to know ahead of time that there is a solution. 
The puzzle is available on GitHub as open source code if someone wants to contribute directly to the code base:
https://github.com/JozefJarosciak/TetronimoPuzzleSolver

 A: In general tiling problems of this nature is computationally hard (there is no "quick" answer). I am not 100% sure there is not some criterion  for this exact problem, but I would be surprised if there is.
While you may not be able to know the answer completely in advance, you may be able to know it sooner, and at least chop off some execution time.
One idea is to use color invariants; I can't say how fruitful this approach would be, but I'd definitely investigate it. 
Let's say we have a $6 \times 6$ square, and we have 5 T tetrominoes (which orientation don't matter for now) and 4 squares.  
Now color the rectangle with the checkerboard coloring, and notice that a square always cover 2 white and 2 black cells, and a T tetromino covers either 3 white and one black or 1 black and 3 white. So we have two types of T tetromino, and one type of square. Now let the number of each of these three types in a tiling be denoted $T_1$, $T_2$ and $S$. We can now write a set of equations for the number of black and white squares in terms of these values:
$$W = 2S + 3T_1 + T_2$$
$$B = 2S + T_1 + 3T_2$$
But we know $S = 4$, and $W = B = 18$, so we get
$$18 = 8 + 3T_1 + T_2$$
$$18 = 8 + T_1 + 3T_2$$
Or after some algebra, 
$$T_1 = T_2$$
But we know that $T_1 + T_2 = 5$, so no tiling is possible (since $T_1$ and $T_2$ must be whole numbers).
In this case we are lucky and get an answer immediately. And this will also work if we replace the squares with any of the other tiles (all the other tiles cover 2 black and 2 white squares).
To see how this can speed up the algorithm, take the same problem, but let's say we choose 5 squares and 4 Ts instead. Now suppose the algorithm came up with this partial tiling:

Now we can prune positions where the T tetromino will fall to cover 3 black squares, since we know such tilings are impossible.
For example, we don't need to search for tilings where the next T tetromino will fall in the red positions marked below:

The trick is of course to come up with colorings that are useful for various tile sets, and then put them together in a cohesive algorithm. Another example of a potentially useful coloring is the following one, that can be used for a tile set that has bars and squares.

A square covers 1 black and 3 white, and there are two bars that cover either 4 white, or 2 of each. This gives us these equations:
$$W = 3S + 4B_1 + 2B_2$$
$$B = 1S + 2B_2$$
You will need to play around with various colorings to see which ones are useful. You can of course also find colorings that work for three or more tiles. However, you can also reduce search time using colorings for tilesets with two tiles if you place tiles of one type first. (Although this may impact the algorithm in other ways. For example, if you try all positions of a given tile, you may loose some of the benefit of the randomization speedup you get.)
There are also some other invariants you may try to speed things up. For example, all convex sides of a square tiling must have even length. (If you place all other tiles first, you can prune some branches of the search tree with this test.)
Although these type of colorings are usually regular in some sense, it is not strictly necessary. Using a pattern makes it easier to reduce the number of tile types, but you can also do this in other ways. (For example, you can use a coloring with the only restriction that all black cells have only white neighbors. With this scheme there are three types of squares: white only, one blac and three white, and two black and two white.) It may be interesting to see if random colorings with suitable restrictions give you a speedup; if it does you don't need to search for specific ones.
You may also check out this paper, which may have some further (and more) useful ideas: Ribbon Tile Invariants. 
