Hi together,
well, you may improve the algorythem further and solve such puzzeles with up to 64x64 (or 128x128 if your comp supports a 128 bit unit , like AltiVec, etc.) field size in a few minutes.
Your one-field approach was a good idea but why not checking against a whole line? Beginning with the last line and as few shapes as possible...
To do this FAST you need to convert the field and the shapes into liniar binary data.
Your field (from the picture) will become: 100110101 - where 1 needs a odd number of convertions and 0 and even number (or null).
Pos 1 is left like: pos 1 was x=0,y=0, pos 2 was x=1,y=0, etc.
Now the shapes:
Shape 1: 11010
Shape 2: 01011
Shape 3: 01011001 and so on...
You need to fill in Zeros up to the X field size. E.g. shape 1 has a width of 2, the field X size is 3, so you need to add 1 Zero to each line, except the last line. You still need to keep possible positions for each shape but this time you need it as offset for the field data - just a single byte per pos.
Now you can simply use bit operators to check against the field and other shapes by using XOR and positioning the sahpes by shifting the bits.
To keep things simple, starting checking against the last line, solve it and move up line by line. In your example the last line is only 3 bits: 101
As you can see field 1 and 3 of the line needs to be transformed, now find the right shapes - try with as few as possible...
If you have a puzzle with 3 or more items, convert them the same way and check for a correct tranformation only if a solution matches the bit field...
This way you can compare around 20 mil. positions of 20 shapes per second as long as the field width is less than 64 blocks (or 128).
Another improvement would be to find shape combinations that wipe out each other to reduce the number of shapes...but you may end up with no solution this way...However, it worked for me for most tests.
Hope that's fast enough
Cheers,
Twilight