Discuss Knight's Maze here

[MatthewV]

link to puzzle

(You can post a number of moves as a solution if you don't wish to spoil the route)

[Thok]

Too lazy to actually do this, but the following method is guaranteed to give you a correct answer.

Start at your original point. Label all squares that are a legal L move away from that square with a 1. Label all unlabelled squares that are a one legal L move away from a square labeled 1 with a 2. In general at step n, label all unlabelled squares that are a one legal L move away from a square labeled n-1 with an n. At some point you will label the exit with a number m, then you are m steps away. (You can reconstruct a path by backtracking from the final square, each step going to a square that is a legal L move away and has a label that is smaller than your current label).

Just to double-check, you can only move the knight along a L-shaped subdiagram of the white diagram, correct? In other words, you can't always move a piece over two and up one, even if the destination square is empty.

[MatthewV]

Just so there is no confusion here...


Red= illegal move
Green= legal move
X= knight

[Zotmeister]

So by "L-shape", you mean "two cells in an orthogonal direction and then one cell in a direction perpendicular to that direction, passing freely over pools but not through walls"? Anyone else think that's an oversimplification besides me? - ZM
_________________
Darkness lessons learned/Avenging golden tresses/Yellow flower blooms
- "(dedicated to Millia Rage)", original haiku

[Ctorj]

uhhm...which pyramid are you? The yellow one or the red one?
_________________
"Love is the absolute expression of the human perfection" -Me!

Created by MyFitnessPal.com

[Zotmeister]

[Hand-E-Food]

I think I've found the way. Using the simplified map with the top being North.

Go from the blue square (red pyramid) EEN NEE WSS WSS WWS SEE ESS EES ENN SWW ESS ESS WWS SWW WWN NNW NWW NNW WNN WWN NNE WNN NNE WNN EEN WSS WSS SEE NEE NEE NNE SWW SWW ESS SEE to arrive at the green square (yellow pyramid.)

[fadeblue]

That's too long, Hand-E-Food. I've definitely found an upper bound of 27 moves.

[Aalk4308]

Nice work Hand-E-Food. A slight improvement in the NW corner shaves off a few steps to get a 31 step solution as follows: EEN NEE WSS WSS WWS SEE ESS NNE WWS ESS SSE SEE WWS WWS WWN NNW NWW NNW WNN WWN NNE WNN NNE WNN EEN NEE EES SSW SWW ESS SEE. (I also changed how to get through the SE corner, but it didn't save any steps.) I don't see how to get to fadeblue's 27 steps though.

[Thok]

[fadeblue]

There are several paths of that length, but they can be divided into 2 categories (based on how they approach the SE corner).

[Thok]

Duh, you're right. I guess there are like 3 ways to go from the 15th square to the 20th square (starting from western of the two squares).

One solution is

WWS SSW WSS SEE SSE EES NNE SWW ENN SSE WWS ESS SEE NEE NEE WWN WNN NNW NEE WSS NNW WWN NEE NNW NEE NWW SSW

[Smitty]

A 21 move solution using the simpler, rotated image. A question remains though...

Start at blue square, EEN NEE WSS WSS WWS SEE ESS NNE WWS ESS SSE SSW SWW (NWW: questionable move here: it's a "knight" move, but "uses" a black square) ENN NWW WNN WWN NNE ENN NEE

[Tony Gardner]

I can't view the picture Matthew posted in post #3, but reading Zotmeister's interpretation of that picture, I don't think your path is allowed Smitty, for the reason you indicate yourself. I guess Thok's solution of 27 steps is the real deal.

[Holywhippet]

[MatthewV]

That wouldn't make a very interesting maze.

[fadeblue]

If we could jump over walls, then there'd be a 5-move solution.

[Zotmeister]

[fadeblue]

Doh! I'm blind...

[Holywhippet]

Well, the rules of the puzzle only say you can't land on the pools of mercury. Walls are never mentioned. Of course, if this is an underground labyrinth then jumping over them would be impossible.

[Lucky Wizard]

Yep, 27 moves is the least. There are eight solutions -- moves 1-4 and 10-15 and 21-23 are the same in each, but there are two different paths for moves 5-9, two for moves 16-20, and two for moves 24-27. (Here the moves are numbered with move 1 being the move starting at the green square and move 27 being the move ending at the blue square.)

Metapuzzle: This puzzle concerns two adjacent squares in this grid whose shortest connecting path is 27 moves. But this actually isn't the longest number of moves between adjacent squares in the grid. Can you find a pair of adjacent squares that requires 37 moves to move between?

[CB]

A minor correction: there are three different paths for moves 24-27. This raises the total number of solutions to 12.

Now for the metapuzzle: i could only find a pair of adjacent squares requiring 35 moves. I used Roy-Floyd, so i'm pretty sure that one that needs 37 doesn't exist!

And a metapuzzle of my own: Which pairs of points in this maze are furthest apart, and how many moves are required between them?

[ChienFou]

Knight's maze is fun. Way back in 1969 in the days when there were 6 computers in London, I worked for a computer bureau on a Control Data 6600. awesome machine 1MFlop in 1969! I worked in the traffic department, where we modelled traffic flow and one of our problems was computing shortest route between two points in a network.

in those days we'd set up 1000 zones and count the traffic out and traffic in. Then we'd build the shortest routes between each zone on the network of roads. Then we'd relax the trip end matrix(the counts) to get journeys. Then we'd load the network with the journeys using the shortest paths (we called them trees) and then we could see the amount of traffic on each road in the network. it's why the M4 goes North of Reading for example; my fault

Back to the maze. You can do the same thing here, just build the tree, using inhibitors to stop building branches whenever an illegal move is made. (We actually stored the trees as "backlinks" much as described above).

Eventually I used the same methods to solve the non-crossing Knight's Tour on a 7x7 (unique solution) and 8x8 (about 1 dozen solutions) chess board. The algorithm is rather nice in that each time you make a move, all the moves which cross it become illegal, so there are some lovely tables for removal and recovery of the matrix of legal moves.

Just for curiosity, has anyone seen the picture for the 7x7 - it's very pretty.

[CB]

7x7 non-crossing? I must be looking at a different set of rules... Non-crossing for me means that if a move of c3-d5 has been made, then all moves from c4 to d2, e3, and e5, from d4 to b3, b5, and c6, and b4 - d3 - c5 - e4 are forbidden. But in that case, a tour must contain each of the 4 corners, which means that a1 must be connected to both c2 and b3. This makes b1 and a2 unreachable, doesn't it?

[ChienFou]

Since I posted that I googled for "Non-crossing knight's Tours" and found a couple of interesting sites. The 6x6 solution is unique (17 moves), the 7x7's are very pretty, some are closed and symmetrical

[Lucky Wizard]

The pair I had thought to be 37 moves was on the right-hand side of the simplified map, 6 and 7 squares south of the top edge.

[CB]

One of the best paths between (5,13) and (6,13) is:
(start from the upper square!) SSW, SSW, EEN, WNN, ENN, NNW, WWN, ESS, NWW, WWS, WNN, NWW, WWS, SWW, ESS, WSS, SSE, WSS, SEE, SSE, ESS, EES, ESS, SEE, EEN, NEE, NNW, NNW, EEN, SSW, NWW, NNW, EEN, ENN, ENN.
There is at least another route, by using four different squares in the lower right corner zone, but at first glance i couldn't find others.

^{PS For the coordinates of the two endpoints i used C-style indexing. The upper left corner is at (0,0).}

[Lucky Wizard]

Okay, thanks.

[MatthewV]

If someone wants to make a similar maze that has only one possible shortest route and provides a decent challenge for those solving, I would be able to use it in a puzzle I am currently working on.