Quote:

Unicursal: A unicursal Maze means one without any junctions. Sometimes the term Labyrinth is used to refer to constructs of this type, where "Maze" means a puzzle where choices are involved. A unicursal Maze has just one long snake-like passage that coils throughout the extent of the Maze. It's not really difficult unless you accidentally get turned around half way through and make your way back to the beginning again.

Quote:

Original post by Hodgman The first thing I thought of is simply to brute force it. Pick a start location, randomly choose a valid direction, repeat. If no valid direction can be chosen, then you're at the end. If there are blank spaces still (cells that aren't visited by the path), then you fail, so start the whole process again. Eventually, chance will give you a valid path. According to this page, a term to search for might be "Unicursal maze". Quote: Unicursal: A unicursal Maze means one without any junctions. Sometimes the term Labyrinth is used to refer to constructs of this type, where "Maze" means a puzzle where choices are involved. A unicursal Maze has just one long snake-like passage that coils throughout the extent of the Maze. It's not really difficult unless you accidentally get turned around half way through and make your way back to the beginning again.

Quote:

Unicursal: One way to create a random unicursal Maze is to take a perfect Maze, seal off the exit so there's only the one entrance, then add walls bisecting each passage. This will turn each dead end into a U-turn passageway, and there will be a unicursal passage starting and ending at the original Maze's beginning, that will follow the same path as someone wall following the original Maze. The new unicursal Maze will have twice the dimensions of the original perfect Maze it was based on. Small tricks may be done to have the start and end not always be next to each other: When creating the perfect Maze, never add segments attached to the right or bottom walls, so the resulting Maze will have an easy solution that follows that wall. Have the entrance at the upper right, and after bisecting to create the unicursal routing, remove the right and bottom wall. This will result in a unicursal Maze that starts at the upper right and ends at the lower left.

Quote:

Original post by Umbrae Perhaps an idea is to start with a straight line from start to finish then continually look for ways to put 'kinks' in it, look at two adjacent empty squares and bend the path into it. Keep running this algorithm over the path until it's bent out of shape. Not only do you want to make additions to the path, but also move it for some modifications. The key is to always have a valid path so you never have to validate it and try to solve.

Quote:

Original post by Pseudokai I'd recommend looking at Hamiltonian paths. If you treat each square in the grid as a vertex then it should be exactly what you're looking for.