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

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 (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-Tif C=0: Left-Tif C is even: Forward-slantif 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

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

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).

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

Re: The hardest maze in the world

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.

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

Re: The hardest maze in the world

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

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

Re: The hardest maze in the world

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

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

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

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

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:

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

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

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

Well, that was fast.

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

Re: The hardest maze in the world

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:

Zipped web page for generating and exploring the maze:
Kitty Maze.zip

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

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

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

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?

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

Re: The hardest maze in the world

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

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

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

Re: The hardest maze in the world

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

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

Re: The hardest maze in the world

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.

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

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.