Hmm, maybe you have overseen one aspekt of my last post - the row by row thing. This highly reduces the number of possible tries and solutions for the remaining lines.
Usually the last row requires the fewest number of shapes to solve than any other row. Once a row is solved, try to solve the next row with the remaining shapes.
Let's take a 8x8 blocks field with 20 shapes. Beginning with the last row, even if the last line requires 14 shapes to be solved, you only have to check, possible shape postions (you only need to multiply all possible x-positions of each shape),e.g.:
2 x 4 x 4 x 8 x 2 x 3 x 4 x 5 x 8 x 3 x 5 x 4 x 6 x 3 = 265.420.800
Why only 14? Easy the 6 remaining shapes are not enough to cover all remaining fields that need to be turned (this may be an additional check in your routine).
I guess, you can imagine that is it very unlikely that you need 14 images to solve the last row. In practice you need around numOfShapes/4, with our 20, this would mean 5 shapes to solve the last line...
With each solved row you GREATLY reduce further calculations, because both, field size and number of shapes to be tested against are reduced.
Just think about it another second...
The bit-mask is in fact only a bonus. I've written a small c-prog for that, it checks around 100mil pos/sec.
|