Number of correct Solutions of a 15 puzzle

Question

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.

Answer 1

As you know, this is related to the $15$-puzzle, which has a long history of computer attempts. I'm not sure I understand this game, but it seems to me that there are a number of winning positions. I don't know how much that would affect the problem.

Af far as I am aware, the most successful attempts at the $15$-puzzle used "best-first" search, using a heuristic for ordering the search. The best heuristic turned out to be the taxicab distance. There is a discussion here. My knowledge of this comes from a long time ago, and my recollection may be incorrect. Also, for all I know, someone has done better by now with neural nets. I've tried to find a paper that discusses this problem, and to remember where I read about it, but with no success. If I recall it, I'll update this answer.

It isn't clear to me whether you are looking for the shortest path from a given starting point to any solution, or to a specific solution. In either event, I would think that finding all possible solutions is the first thing to do.

Also, I would mention that depth-first search with iterative deepening may be a better approach than breadth-fist search, if you run into memory problems. (Of course, I mean the heuristic variants of these.) You mention depth-fist search and backtracking, but that is not an effective approach to finding the shortest solution.

Good luck.