The Dumbest Way To Solve A Maze - Numberphile

More links & stuff in full description below ↓↓↓

NUMBERPHILE

Videos by Brady Haran

[KasranFox]

finally, the maze-solving equivalent of bogosort

[superscatboy]

I once made a "rat with a terrible memory" maze-solving AI: It could do perfect A-star, but it only knew about walls it had "seen" (had a line of sight with), and at random it could forget a wall that it previously knew about.

[MuJoeTheMean]

Interestingly, this concept actually has real world application in the world of mechanical engineering. Labyrinth seals are a type of seal in which a fluid is contained simply by making the leak path very long and torturous for the fluid particle to escape out of. This simulation is a pretty good demonstration of how surprisingly difficult it can be for a particle to escape when it just has random collisions to guide it. You can imagine that if designed to be intentionally difficult (narrow, long passages with lots of turns), a maze like this could do an excellent job at stopping leaks.

They are most commonly used to seal spinning axels, where a normal seal may not be suitable due to friction or durability concerns. In these applications, the path usually makes many trips to and away from the axle so that centrifugal motion of the fluid can help prevent any leakage as well.

[hamjudo]

Long ago, my robotics club had a maze solving competition for small autonomous robots.

Before the contest began, I put a toy into the maze. It was a battery powered sphere with a picture of Santa Claus on it. There was a motor driven offset weight inside the Santa Ball. The Santa Ball would roll in a straight-ish line until it hit an obstacle. Then it would bounce in a random direction and continue on.

The actual robots moved much more slowly. Even though they didn't ever retrace their path, they were much slower.

Fortunately, the Santa Ball was disqualified. It was store bought, not built by a contestant. Thus one of the robot builders got the official first place prize.

[donaldasayers]

I have a 3D cube maze, it's in the form of a 5x5x5 cube, transparent and you roll a ball through it. But if you blow through it, the correct path steams up. This is exactly the same method.

[jeffreydemattos]

I like your idea of solving a maze with gas pressure. this is mathematically very simple to simulate, and even a bad simulation would be very fast. For example, you could assign a fixed pressure of 1 to the maze entrance and zero to the maze exit. All the other cells start with zero pressure. Then iteratively calculate the pressure for every cell as the average of the pressures of adjacent connected cells. The length of the shortest path is simply the number of iterations it takes for the cell adjacent to the exit to get some non-zero pressure. And the shortest path would simply be from the beginning to the cell with the next highest pressure for each step and so forth. For larger mazes, processing time could be saved by keeping a list of all the cells with some positive pressure and in each iteration, add to the list the cells adjacent to the ones that have already been calculated at least once. Unfortunately this is not much different than simply enumerating the entire maze search, with the exception that you only have to store one value (the pressure) for each cell.

[thecakeredux]

I love the merge between logic and programming and creativity. It's how I conceptualized creating code forever, but this illuminates that intersection so well. I'm amazed.

[shohamsen]

This problem of maze solving screams calculus of variation. The function that minimizes the distance between the beginning and the end point subject to the wall constraints. I would model the walls as lines (some thickness) of infinite potential. So that functions intersecting the walls have answer infinite. Im sure someone must have thought about it (it would be a shame if nobody tried this tool with 500 years of research backing it up).

[cyndicorinne]

This approach to solving problems is quite effective as it is interesting. In computer science there are many algorithms which emulate physical processes. It is always a pleasure watching Numberphile because of its closeness to the field. Thank you 🙏 for another awesome video!

[sol_x_dier]

2:24 Well, by definition, the dumbest way to solve a maze has to work because it would have to solve it, so this could still be the dumbest way. On the other hand, the dumbest approach to a maze would be to just stand still. That, however, can't be called the dumbest way to solve a maze, because it never solves the maze.

[HappyBeezerStudios]

How they are stuck in the first third and the density becomes progressively lower reminds me of mazes in Roller Coaster Tycoon. The way the pathfinding works causes the guests to practically get stuck (and walk back) on specific layouts with a very slim chance to move further.

[philippelepilote]

30 years ago, I had the idea to "inflate" a grid of walls with random strength in order to create a "simply connected" maze. I eventually wrote the algorithm in Visual Basic for Excel, associated to the "follow-the-right-hand-wall" solver. So happy to discover that somebody else finally blew into a maze !

[topilinkala]

No-one has mentioned it but the way only one sperm can enter the egg is that the instant it enters the electric charge on the surface of the egg changes to repel more sperm.

[gedstrom]

I still remember a maze generation program that I coded in Basic back in 1978...45 years ago! I had a lot of fun with it in my very first personal computer.

[anon]

Matt has the best job.
I love making simulations like this.

[kilimanjarocruz]

It's lovely that this 'demonstrates' both the pressure drop that a gas would have in such a flow and the statistical origin of the ideal gas law. Awesome.

[redryder]

It would be interesting to see what sort of maze design results in the Brownian motion taking the longest time to reach the exit. Would it simply be a zigzag path using 100% of the area of the maze or would it look more like a Tesla valve?

[cyndicorinne]

A-maze-ing demonstration of this physical approach to problem solving, which for me as a computer scientist is always cool to see.

[lucassippel]

Looks like they get halfway quite quickly. You could also diffuse gas from the exit and then check pairwise between particles from opposite ends for line of sight. Then stitch a forward path and backward path together for a complete solution. Pairwise checking might be inefficient so you could limit it to particles which are past some predefined halfway - like a vertical line down the middle of the maze.

This is the sort of thing that is only obvious when you have an appropriate visualization. Always love watching these animations!

[rianantony]

If you wanted to find the dumbest way, it'd be fun to wait for every single molecule gets out. And then highlight the path taken by the single last one to find the exit