The hardest maze in the world

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

Calumnia
Posts: 13
Joined: Fri Jun 04, 2010 9:23 pm UTC

The hardest maze in the world

Postby Calumnia » Wed Jan 26, 2011 5:34 am UTC

snippet.GIF
This is a snippet of the upper left corner of the maze. The maze is constructed on a grid with six basic building blocks:
types.GIF
types.GIF (2.88 KiB) Viewed 6849 times
(The white strips represent passable paths; you can't pass through black.)

Our maze is laid out on a two-dimensional grid, with the origin square (Row number 0, Column number 0) in the upper left, extending infinitely downward and to the right. (Thus, the row numbers and column numbers are numbers 0, 1, 2, 3, etc.)

To determine what type of block is at a given location (Row number R, Column number C), apply the following pseudocode (stop following the code once you've determined the block type):

Code: Select all

if R=0:
   if C=0: Backward-slant
   else: Top-T
if C=0: Left-T
if C is even: Forward-slant
if C is odd:
   if C+2 is composite: Horizontal
   if (R,C)=(1,1), or 2R-1 is prime: Vertical
   else: Horizontal

Enter through the left side of square (0,0), and exit through the top of the same square.

If thou canst find, O Friend, a path through this maze, then go forth in triumph, for thou hast proven thyself worthy of everlasting glory.

lordatog
Posts: 84
Joined: Tue Feb 10, 2009 5:09 am UTC

Re: The hardest maze in the world

Postby lordatog » Wed Jan 26, 2011 7:12 am UTC

So, which open problem is this equivalent to?

Nitrodon
Posts: 497
Joined: Wed Dec 19, 2007 5:11 pm UTC

Re: The hardest maze in the world

Postby Nitrodon » Wed Jan 26, 2011 7:26 am UTC

Any solution must be of the following form:
Spoiler:
Let n be a counterexample to Goldbach's conjecture. From the left side of square (0, 0), go down to (n/2-1, 0), follow the path right and up to (0, n-2), then go left to reach the top of square (0, 0).

User avatar
WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: The hardest maze in the world

Postby WarDaft » Wed Jan 26, 2011 9:01 am UTC

I would argue that a maze must have an explicit solution known to the creator to be considered difficult, else we could construct mazes for which the solution is not only unknown, but demonstrably beyond the resources available in the observable universe to decide if they even have a solution.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3069
Joined: Sat May 09, 2009 11:55 pm UTC

Re: The hardest maze in the world

Postby Qaanol » Wed Jan 26, 2011 2:05 pm UTC

WarDaft wrote:I would argue that a maze must have an explicit solution known to the creator to be considered difficult, else we could construct mazes for which the solution is not only unknown, but demonstrably beyond the resources available in the observable universe to decide if they even have a solution.

While I agree with you in principle, your reasoning is unsound. It may well be true that (requiring the creator know a solution to the maze) is sufficient (to rule out those constructions demonstrably beyond the resources available in the observable universe to decide), but the former is not necessary for the latter.
wee free kings

User avatar
WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: The hardest maze in the world

Postby WarDaft » Thu Jan 27, 2011 9:58 am UTC

Actually, thinking about it, it's also not enough to actually guarantee that the maze actually is solvable given our resources.

Suppose we construct a thin diagonal swath such that finding the location of a path that successfully gets through it is equivalent to factoring a specific constant related to the maze - this could be as simple as a diagonal encoding of factors and having a hole in a single diagonal line located at the position that encodes the factorization of the maze's constant, and then simply wall up the rest of the maze according to a randomized spanning tree.

Pick two thousand digit primes and multiply them for the maze's constant, and you can solve your maze (well, algorithmically) but no one else currently has the resources to do so.

It would also look a lot more like a maze, rather than being a simple case of "go down until one of the paths to the right takes you to the topmost row" being all you need to solve the maze if it has any solution.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

Xami
Posts: 74
Joined: Tue Sep 29, 2009 8:29 pm UTC

Re: The hardest maze in the world

Postby Xami » Fri Jan 28, 2011 4:23 pm UTC

Decided to learn a bit of Python with this, it was fun, could probably do a lot of things better but that's not what this forum is about.

Findings
Spoiler:
R = starting row
wR = working Row
wC = working Column
Skipped even numbered columns
if working Column + 2 is prime AND (2*working Row - 1) is prime, then we hit a wall.
This is a printout of the furthest column reached, it doesn't look good as expected. Can post code with any hint of interest.
R = 2 wR = 2 wC = 1 Row % = 0.0000 Col % = 20.0000 Time: 2011-01-28 10:14:25.631000
R = 5 wR = 4 wC = 3 Row % = 20.0000 Col % = 27.2727 Time: 2011-01-28 10:14:25.670000
R = 14 wR = 12 wC = 5 Row % = 14.2857 Col % = 17.2414 Time: 2011-01-28 10:14:25.704000
R = 48 wR = 40 wC = 17 Row % = 16.6667 Col % = 17.5258 Time: 2011-01-28 10:14:25.763000
R = 109 wR = 99 wC = 21 Row % = 9.1743 Col % = 9.5890 Time: 2011-01-28 10:14:25.901000
R = 153 wR = 139 wC = 29 Row % = 9.1503 Col % = 9.4463 Time: 2011-01-28 10:14:26.037000
R = 277 wR = 255 wC = 45 Row % = 7.9422 Col % = 8.1081 Time: 2011-01-28 10:14:26.285000
R = 495 wR = 460 wC = 71 Row % = 7.0707 Col % = 7.1645 Time: 2011-01-28 10:14:26.646000
R = 1320 wR = 1270 wC = 101 Row % = 3.7879 Col % = 3.8243 Time: 2011-01-28 10:14:28.106000
R = 2685 wR = 2617 wC = 137 Row % = 2.5326 Col % = 2.5507 Time: 2011-01-28 10:14:30.675000
R = 3712 wR = 3627 wC = 171 Row % = 2.2899 Col % = 2.3030 Time: 2011-01-28 10:14:32.796000
R = 21765 wR = 21661 wC = 209 Row % = 0.4778 Col % = 0.4801 Time: 2011-01-28 10:15:16.330000
R = 27121 wR = 27006 wC = 231 Row % = 0.4240 Col % = 0.4259 Time: 2011-01-28 10:15:31.773000
R = 31636 wR = 31491 wC = 291 Row % = 0.4583 Col % = 0.4599 Time: 2011-01-28 10:15:46.351000
R = 56835 wR = 56680 wC = 311 Row % = 0.2727 Col % = 0.2736 Time: 2011-01-28 10:17:19.144000
R = 64083 wR = 63919 wC = 329 Row % = 0.2559 Col % = 0.2567 Time: 2011-01-28 10:17:48.27100
R = 97213 wR = 97035 wC = 357 Row % = 0.1831 Col % = 0.1836 Time: 2011-01-28 10:20:15.096000
R = 97234 wR = 97044 wC = 381 Row % = 0.1954 Col % = 0.1959 Time: 2011-01-28 10:20:15.341000

jbwraith
Posts: 13
Joined: Tue Dec 21, 2010 4:01 am UTC

Re: The hardest maze in the world

Postby jbwraith » Mon Feb 07, 2011 5:57 am UTC

This is gonna make all of you feel dumb. The maze opens at (0,14) and again at (14,0). Go out of the maze, and enter from the other side. Maze solved.

Note- I don't code or anything, so that wasn't as much help as just looking at the puzzle for a while.

Of course, I may be completely wrong.

Osha
Posts: 727
Joined: Wed Dec 03, 2008 3:24 am UTC
Location: Boise, Idaho, USA

Re: The hardest maze in the world

Postby Osha » Tue Feb 08, 2011 6:52 pm UTC

jbwraith wrote:This is gonna make all of you feel dumb. The maze opens at (0,14) and again at (14,0). Go out of the maze, and enter from the other side. Maze solved.

Note- I don't code or anything, so that wasn't as much help as just looking at the puzzle for a while.

Of course, I may be completely wrong.

This is a snippet of the upper left corner of the maze.

HonoreDB
Posts: 161
Joined: Tue Feb 06, 2007 4:32 pm UTC
Contact:

Re: The hardest maze in the world

Postby HonoreDB » Wed Feb 09, 2011 3:24 am UTC

That is really clever! It made me feel like creating a variant.

The Puppy Maze

If a puppy starts at 0,0 of the following maze, is it possible for it to travel arbitrarily far down?

Code: Select all

Object at (R,C):

   R even:
      C equals R:
         \
      C prime:
         blank
      C composite:
         =
   R odd:
      C odd:
         \
      C even:
         =


The maze starts like this:
puppy_maze_beginning.tiff


The puppy can't fit through the tiny gaps between pieces.

If you download the attached zip file, unzip it, and open PuppyMaze.html, you can traverse it and see the coordinates of each image in the title text. Feel free to modify the code to create your own puzzles.

Anyway, what open problem is this equivalent to?
Attachments
Puppy Maze.zip
(7.8 KiB) Downloaded 68 times

User avatar
phlip
Restorer of Worlds
Posts: 7573
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: The hardest maze in the world

Postby phlip » Wed Feb 09, 2011 3:37 am UTC

Spoiler:
Twin primes?

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]


HonoreDB
Posts: 161
Joined: Tue Feb 06, 2007 4:32 pm UTC
Contact:

Re: The hardest maze in the world

Postby HonoreDB » Wed Feb 09, 2011 7:32 pm UTC

One more. Couldn't help myself.

The Kitty Maze

Can the kitty escape out the bottom of the maze?

Code: Select all

Object at (R,C):
   If R=0:
      If C=0:
         \
      If C=1:
         Kitty!
      Else:
         Blank
   If R=1:
      If C is a perfect square:
         \
      Else:
         =
   If R=C+1:
      If C-1 is a perfect square:
         |
      Else:
         \|
   If R=2:
      |
   If R>C+1:
      Blank
   If (R-1) is a factor of C and C is not a perfect square:
      Blank
   Else:
      |


Start of the maze:
Kitty Maze Start.gif


Zipped web page for generating and exploring the maze:
Kitty Maze.zip
(16.47 KiB) Downloaded 70 times


What open problem is this equivalent to?

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

Re: The hardest maze in the world

Postby mike-l » Wed Feb 09, 2011 9:06 pm UTC

It looks to me like there is a solution if
Spoiler:
There is no prime between [imath]n^2+1[/imath] and [imath](n+1)^2[/imath]. Which I didn't know was an open problem.
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

HonoreDB
Posts: 161
Joined: Tue Feb 06, 2007 4:32 pm UTC
Contact:

Re: The hardest maze in the world

Postby HonoreDB » Wed Feb 09, 2011 9:12 pm UTC

That's correct.
Spoiler:
It's called Legendre's conjecture.


Edit: Your solution is basically right, but just to be clear,
Spoiler:
That's an inclusive between--if n^2 + 1 is prime, then it's not a solution. You can see that in the gap between 2^2 and 3^2: even if 7 weren't prime, the primeness of 5 still makes it impossible to escape. Not that "if 7 weren't prime" is a well-formed counterfactual, but you know what I mean. Your solution looks like a slightly stronger version of the conjecture.

Calumnia
Posts: 13
Joined: Fri Jun 04, 2010 9:23 pm UTC

Re: The hardest maze in the world

Postby Calumnia » Mon Feb 21, 2011 10:55 am UTC

Glad you enjoyed it! I had been trying to think of how to design the Ultimate Maze™: a maze whose solution (if any) is isomorphic to a Gödel sentence, encoding a proof that the maze has no solution. But I had trouble figuring out how to even get started designing such a maze. Maybe you have some ideas of how it could be done?

I have to admit I'm having trouble wrapping my head around the idea of this maze -- what would it even mean to say that the maze has a solution, or doesn't?

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: The hardest maze in the world

Postby quintopia » Mon Feb 28, 2011 10:36 am UTC

The First Incompleteness Theorem says that a sufficiently powerful formal system contains a statement that is true, but for which no proof exists within that system. You are asking for a maze whose solution would correspond to a proof of a Gödel's sentence in a particular system. But, we know from said theorem that such a proof does not exist. Thus we would be able to say of your maze both "This maze has no solution." and "The statement whose proof would correspond to a solution to this maze is true."

That said, defining this maze would be hard to do explicitly, in the sort of terms the descriptions of mazes above use, and be extraordinarily complex, and yet somehow less interesting since we already know it would have no solution.

HonoreDB
Posts: 161
Joined: Tue Feb 06, 2007 4:32 pm UTC
Contact:

Re: The hardest maze in the world

Postby HonoreDB » Mon Feb 28, 2011 5:31 pm UTC

It would have a solution iff the formal system involved is inconsistent.

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3069
Joined: Sat May 09, 2009 11:55 pm UTC

Re: The hardest maze in the world

Postby Qaanol » Mon Feb 28, 2011 6:21 pm UTC

HonoreDB wrote:It would have a solution iff the formal system involved is inconsistent.

I presume you want to use ZF(C)?
wee free kings

User avatar
WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: The hardest maze in the world

Postby WarDaft » Mon Feb 28, 2011 7:22 pm UTC

Well, if we're going to go down that rabbit hole, how about a maze with a critical point whose position and existence depends on a Turing Machine which solves the halting problem.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: The hardest maze in the world

Postby Yakk » Mon Feb 28, 2011 7:28 pm UTC

Really, at this point, what I want is a maze that gives more false hope.

The "exit next to where you start" seems reasonable, and a maze that grows right-and-down.

This generates a left and a top "half" of the maze, where the left half is the part that can be clearly found from the entrance, and the right can be clearly found from the exit.

There is also a "middle" part, which cannot be clearly reached from either.

The barrier between these parts should not be macroscopically obvious. In order to figure out if a part can be reached within a size N x N sub-maze, we want to force the solver to actually check. Parts of the middle that seem divorced from the left or right should be retroactively part of it as N grows and "back routes" open up. The middle itself shouldn't be obviously split into different parts -- the size of "cut off" middle portions should either grow extremely fast, or should be completely eliminated.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 6 guests