All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > General
Mensa Maze (Posted on 2009-10-07) Difficulty: 3 of 5
You can navigate the grid below from the top-left yellow circle to the bottom-right yellow square by making only orthogonal (not diagonal) moves, going from one position to the next only if the shape and/or the color of the shape in the entered cell is the same as that of the cell you are leaving.

  • What path has the minimum number of moves without going through the same cell twice?
  • What path has the maximum number of moves without going through the same cell twice?

See The Solution Submitted by Charlie    
Rating: 3.0000 (3 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
GraphTraverser | Comment 7 of 20 |

I found the simplest approach to be to draw a simple graph using the midpoints of each square.  Connect orthogonally adjacent squares if the conditions are met (same color or same shape), otherwise no connection.  From this diagram it it obvious that only a few paths exist from upper left to lower right.

It only takes a minute or so of inspection to note that the shortest path is 18 viz  (1,1)(2,1)(3,1)(3,2)(4,2)(4,1)(5,1)(5,2)(6,2)(6,3)(5,3)(5,4)(4,4)(3,4)(3,5)(4,5)(5,5)(6,5)(6,6).

For the longest path, using the same graph, remove the segments which have only a single segment (both 1,1 and 6,6 have two; any square with only a single segment entering is excluded because to enter and leave would require visiting the same square twice.

There is a cut point from 1,1 to 3,2: the longest way to reach 3,2 is [(1,1)(1,2)(1,3)(1,4)(2,4)(2,3)(3,3)(3,2)] entering 7.

From 3,2 to 3,5 there is only a single path [(3,2)(4,2)(4,1)(5,1)(5,2)(6,2)(6,3)(5,3)(5,4)(4,4)(3,4)(3,5)] entering 11 (this is part of the shortest path).

From 3,5 to 5,5 there are only two paths, the longer of which is [(3,5)(2,5),(2,6),(3,6)(4,6)(5,6)(5,5)] entering 6.

From 5,5 to 6,6 you may choose either [(5,5)(5,6)(6,6)] or [(5,5)(6,5)(6,6)] entering 2.

Hence the longest path meeting the qualifications is 26.  This all seems straightforward: working with the graph seemed much simpler for visualization than working repeatedly with the shapes and colors per se.  Unless I was careless with my graph, this seems quickly to solve both tasks.  No computer needed!

 


  Posted by ed bottemiller on 2009-10-07 19:56:48
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (14)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information