Solving noodles puzzles
Haven't noodled yet? Download noodles here!
Shortly after building the prototype I realized that testing would not be fun if there's a 2-5 minute gap before testing some level-complete code. I needed the phone to solve the puzzles for me.
Before I start, I will say this: There may be a specific algorithm to solve this, something elegant from graph theory. I don't know it. Drop me a line if you do.
ATTEMPT 1: Brute Force!
- Result: Ha! 10 minutes per solve, slower than I am.
ATTEMPT 2: Brute force with backtracking & smart pruning
- Start at (0,0). Set the piece to point North.
- Check if the orientation is valid. If the current piece now points off an edge of the puzzle, no good. If the piece points at an earlier piece (earlier row or same row, earlier column), and only one of the pieces points at the other, no good.
- If the orientation is invalid, rotate the piece once clockwise and try again.
- If the orientation is possible, move on to the next piece in the puzzle and try to set that.
- If none of the orientations is possible, back up a step to the piece before.
- On the last piece of the puzzle, check if every piece is connected (using our BFS).
- Connected? Done. Not connected? Back up a step.
- Result: This really depended on the specific puzzle, but it wasn't fast. Anywhere from about 10 seconds to 2 minutes per solve.
ATTEMPT 3: Possibility sets
- For each piece, mark the possible orientations (every direction, to start).
- GOTCHA: Some pieces have multiple orientations that are the same. For example, a straight line can point north or south and both would be a valid solution. This confuses the possibility sets, so you have to eliminate duplicates in step 1.
- Piece by piece, remove impossible orientations from the possibility set for that piece, using the same rules as above.
- Once a piece has only one possibility, it's "locked" and we know the final orientation. Then the piece can be used to eliminate possibilities from its neighbours.
- Cycle through the pieces until you have a solution, or until you're stuck. It will take many passes.
- If you're stuck (you've gone a full pass without making any changes to sets) then use brute force on the remaining unlocked pieces.
- Result: Much better. Most puzzles, and all smaller puzzles, take < 1s. Sometimes larger puzzles can take 10s or so, but it's less common.
ATTEMPT 4: Possibility sets with smarter ordering.
- Do attempt 3, but instead of going through in piece order, start at the edges of the puzzle where you are most likely to lock pieces immediately.
- Result: This saves a little bit of time, but nothing to write home about.
So after 4 attempts, we've got a reasonable solve that worked for testing. Since it was debug-only I didn't worry too much about it. But there are certain features we're thinking of adding that would require knowing the solution, and I can't have a 10 or 20 second delay to find it.
And as sometimes happens, I bailed on an algorithmic solve, and did what I should have done in the first place:
ATTEMPT 5: Just store the solutions with the damn puzzles.
When I generate the puzzles they are all connected anyways, so it's just a matter of recording the orientations and putting them in the json.
- Result: Instantaneous solve, and a bit of shame for previous wasted time.
One small catch: I already generated the puzzles, and already submitted a build to Apple, so I really didn't want to re-generate puzzles. For anyone who had played the game already, their best scores would be all messed up.
So for all the game packs, I wrote a small bit of code to load the pack's puzzles in json, called solve() for each game, and wrote the solution back to the puzzle json. Levels stay the same, and I just add solutions to each of them. So my little solve() method got production use after all...