I downloaded a game on android called Walkabout. You walk along a grid, and every block you step on falls out from under you and some blocks MUST BE STEPPED ON (have a star to collect)

This got me started on wondering what's the best way to computationally solve these levels? There is a level where every block that can be stepped on must be stepped on.

I don't know how I'd apply rules to a solution, but I know the levels could be bruteforced.

I would put together an interpreter to parse handmade level codes (something like _ for spot you can step on, * for a star to collect, and # for an obstacle, o for starting position) and then have the program identify any locations from the start that are like this:
because you cannot get out from that location, it would have to be the last star you collect.

The level that got me thinking about this would be layed out like this:


I can't figure this out, but if you go anyway other than right from the start, I don't know how you could get back there to finish up those stars. I've gotten all but one star once.

Anyone want to give input on how someone would make a solver for levels like that (that could even possibly recognize impossible levels like this one)


Aww heck, I'll make a quick java applet version of it maybe, without graphics most likely, in the next couple of days. I think the easiest thing to do would almost be a maze generator kind of thing.

Well the naive algorithm would be depth-first search which I would probably implement via recursion. I suspect the runtime will be too high to be useful on the large levels though.

If there were no obstacles a Hilbert Space Filling Curve would solve every puzzle: http://en.m.wikipedia.org/wiki/Hilbert_curve

With obstacles I would examine options like A* (http://en.m.wikipedia.org/wiki/A*_search_algorithm) or variations. You'll probably have to run the algorithm from one required space to the next and then use backtracking (use recursion) to find the proper order you should visit the goal tiles.

It might be that the levels are small enough and your computer fast enough that you can tolerate runtimes such as O(N^3).

Very interesting. I think the best way to represent these levels would be to use graphs, where each vertex can only be visited once (and consequently, you can only visit each edge at most one time). Solving a puzzle where all stepping plates are starred would be equivalent to finding a Hamiltionian Path.
Finding a Hamiltonian Path is NP-complete, so there is no known efficient solution. I think the same is true if not all plates are starred (an argument for this is that it is possible to design a level where all plates but one are starred, and you're forced to step on the one that is not starred by the geometry of the level) so it's unlikely that there's a solution more efficient than brute-forcing.

This puzzle was introduced in Pokemon Ruby and Sapphire versions before it became a standalone mini-game. Off topic detail.

What is on topic is that a maze solving algorithm may be used for this style puzzle. Tug left the whole time, where if it can go left, turn left. If not, then go straight. If it can't do either of those, go right. If it can't move, it's either at the start or at the end. If not at the end, then automatically throw stating that it's impossible.

Else, if there's a place where it can make a right, then double left, then a right again and return back to its path, do that. If there is an obstacle, put a holder in the path and tug right until it returns to the holder.

This should solve possible mazes. I'm not sure of its efficiency though because it would have to be recursive to find the end, then recursively recurse the path searching for possible forks.