The question is kind of a follow up to my question here. I might add what I am trying to do in the first place: This is the level "Wiggle" in the game "Cogs" on Android.
It is quite easy to solve by just playing, and this is great fun, but that did not keep me from investigating using c# and mathematics. The solution to the puzzle is a wiggly diagonal line, alternating between four pieces from the upper corner with three from the lower. It's a line going up-right-up-right and so on till you reach upper right.
After establishing the number of possible positions on the board in the last question, I wonder if there is a way of establishing a reliable number (**) for minimum of moves needed to reach the(*) winning position.
The (*) is the first problem: How many winning positions are there? There is only one solution "for the eye", but in combination terms there are multiple. I need 4-of-6 from above, and 3-of-6 from below on 7 specific places, and 9 places do not matter at all with the solution.
Knowing a number to reach any winning position (**) would be great, because if you knew that, you could stop searching deeper in a brute force search tree.
For this level, all that is not necessary. My c# code, using out-of-the-box collection objects, took record of around 4 mill of the 6.7 mill positions in around 10 minutes with about 1 GB of memory, and it found at least 1.500 distict 14-move combinations to reach a solution (the first within 20 seconds). I would have exhausted the search in the next few minutes, but this is because this puzzle has so many exchangeable identical parts.
But still: How can you calculate the number of winning positions, and if possible, establish number of moves you need to make to guarantee you reach it?
I mainly ask, because after easily storming the level shown above, this level
withstands my approach of simply remembering all positions ever seen. I calculated about 1 billion positions using $\binom{16}{5}\binom{11}{3}\binom{8}{2}\binom{6}{2}\binom{4}{1}\binom{3}{1}\binom{2}{1}$, and there is no hope of solving this with an exhaustive search, remembering everything you have seen.
So depth search and backtracking is what I would try now, but I wonder at which depth to stop a search and may look in a different branch.
I have four different solutions for the puzzle "for the eye", but again no idea of how the estimate my chances before setting of an a search.