1
$\begingroup$

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.

Wiggle

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

Leaks

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.

$\endgroup$
  • $\begingroup$ So, you have to get a closed line of pipes connecting the steam leak at the lower left to the outlet at the upper right, correct? Is it required to use all the pipes? This paragraph, "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," is incomprehensible to me. What does $4-of-6 from below" mean, for example? What is the "eye"? $\endgroup$ – saulspatz Jun 30 at 13:43
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.