Subscription

Books
Shop
About

Tuesday, January 25, 2011

Barrier Method to solve a maze

Can you help these butterflies reach the flower?

Try to solve the maze. You can print it first.

Check back to see how a barrier method helped me solve it.

By the way, I got the second picture by using the command Sharpen[ ] in Mathematica software.

One week later: This is my solution
Long time ago, when I first tried to solve this maze, I kept getting tangled up in loops and couldn't solve it. Then I remembered something from my friend's research on Barrier Certificates. It seems like common sense, actually - to prove that there is no possible path, you show that there is a wall/barrier.
I thought to myself, "what if this maze can't be solved?" So I tried to find a wall across the maze. (If I had found one, then that would have been proof of a bad "unsolvable" maze.) I couldn't find a complete wall, but I found a broken wall.


The broken wall is a great help in solving the maze. We know there is no path through the wall; if there's any path from butterfly to flower, then it passes through the crack in the wall. So search backwards from the crack to the flower and from the crack to the butterflies. Like this:

Here are some more mazes that you can solve more easily using barriers.

No comments:

Post a Comment

My Other Blogs

  • #Glocal #business #news bits - With these types of forums (Breakfast chats with seasoned founders and CEOs), we can share our experiences and fast track our growth - Deji Akinyanju (Fo...
    11 hours ago
  • Prizes - Top of the top: 10 Nobel Laureates Who Changed The World See all the Nobel Prizes. Advertisement: Read my books. - [image: Nobel Prizes in Physics,...
    2 days ago
  • Who Will You Marry? Answer in the comments :) - Really good quiz here, you answer 10 questions and it reveals 'who is the right person for you' :) I want to know what result you got, so comment. And ...
    5 days ago
  • o O ~ circles ~ O o - Want REALbubbler Membership? Want fine African Literature? (Preview) Nigerian Lifestyle A-Z at REALbubbler.blogspot.com
    2 weeks ago
  • Paradise Road - It was a morning like any other morning, on a road like any other road. 8 a.m. “Conductor, give me my change.” The dust, smoke, and everything were ma...
    4 weeks ago

About Me

Followers