Mortal Coil is a fun programming challenge at hacker.org
Rules of play
- You are given a maze - a grid with some open and some filled spaces. Pick any point to start, and walk around the maze until every open space is filled.
- You are not allowed to cross your path
- Once you are moving, you are not allowed to stop moving until you hit a wall.
- Initially you can play in the UI on the site
- Once the levels get big, you'll be tempted to write a solver, which will get you pretty far (about level 50 for naive solvers)
- Then you'll want to solve it
Interactions
- Download the level
- Parse the board
- post the solution which has a start point, and a list of directions (RURDLU... etc)
Solution methods
- Basic structure Brute force with backtracking. This is guaranteed to eventually try every possibility
- pruning methods - "board split", "too many deadends", etc.
- There are other ways to solve levels involving percolation of available sub-board configurations which get synthesized into a complete solution.
Level design
- Official coil levels are usually around ~60% empty.
- It's possible to generate much more sparse levels. Open question how these interact with solvers.
- For small levels there are often multiple solutions. Big levels typically have only one or a few related solutions.
Links
Explanation of the image
- This is a filled in solution for a level.
- The red square is the end; green is the start
- When you hit a wall, and have a choice, there is a color. Green means that although you have a decision, one of the directions results in immediately creating a dead end; for most algorithms, these decisions are very easy. A red square means that the decision is slightly harder.
- Most (80%+) of the time you hit a wall, you don't actually have a decision (since there is only one way to go).
- Speculation: having a high decision percentage results in harder levels.
- The stats below are the coverage percent, percent of squares with an easy/hard decision.
Image
