A great problem, and probably something you can write a master thesis on.
* Edge and corner pieces are recognizable as such
* If two pieces fit together, we always know this.
* We cannot use any sort of pattern on the pieces. Apart from the previous two bullet points we have no idea where a piece belongs to.
Some initial thoughts:
You can make estimates based on the relative number of center (M) and edge (E) pieces, but different length to height ratios will lead to different E to M ratios. All you get that way is a lower limit on the size (corresponding to square puzzles, asymmetric puzzles will have the same ratio at a larger overall size). Corner pieces (C) help: There are just 4 of them, if you draw the first one it doesn't tell you much, but with the second one you can be reasonably confident that the puzzle is not too much larger than what you have already. The third and fourth will refine these estimates even more.
You know the length or height once you have a continuous connection between the corresponding edges (you don't need to have them in a straight line). This is a problem in [percolation theory](https://en.wikipedia.org/wiki/Percolation_theory
). In the limit of infinite puzzle size, you need on average half the puzzle pieces for this if I remember correctly.
There is another heuristic estimate, and one that will lead to a reliable (but not exact) estimate the fastest: Count the number of connections you found. I don't have an exact formula, but in a puzzle of N pieces (N>>1), the probability that two random pieces are next to each other is approximately 4/N. With sqrt(N) pieces drawn your expected number of connections is 2, while your expected number of corner pieces is 4. With 2sqrt(N) pieces drawn you expect 8 connections and 8 corner pieces. With 4sqrt(N) pieces drawn you expect 32 connections and 16 corner pieces. The number of connections grows much faster, with its inevitable sqrt(observed) scaling it gives a more reliable estimate than the corner pieces. In addition, its dependence on the overall puzzle shape is much smaller.
The absolute minimum number of pieces is the length and width minus 1 (L+W-1) which has to include at least 4 edge/corner pieces. In addition, there has to be a direct path from edge to edge connecting all 4 sides.
There are (2L-4)+(2W-4) or 2(L+W)-8 edge pieces (from here called E) and 4 corner pieces and N total pieces where N=L*W.
On the other hand the maximum number needed is (L-1)*(W-1)+4 pieces. Or N-E.
From this you can basically make a map of the probability the minimum requirement has been solved given a specified number of pieces drawn between the min and max. This will likely be something of a normal distribution. You are then in an N choose x scenario of possible draw combinations with y combinations that spell success. So Y/(N choose x) is the probability you have the answer. After (L+W-1) picks, the probability of success is LW/(N choose (L+W-1)) and so on. This will give you a plot that should exponentially level off and reach 1 at N-E. you can then do an expected value problem with this set of discreet points and get the expected number of selections before the size is known. This method doesn't really take into account the need for edge pieces, as its based on possible solutions as opposed to probability if picking adjacent pieces.