# The Knight and the Maze

Shown below is a grid of blue and yellow squares with a knight in the upper left hand corner and green square in the lower right hand corner.

Your task is to guide the knight from its starting position to the green square using regulation chess knight moves.

The knight may only visit yellow squares to reach its goal.

• hint to who are trying - start from green box it is easier. – Amruth A Jul 26 '16 at 10:31
• Are you sure you don't want to accept this answer (41 moves) compared to the one you have accepted (59 moves)? – EKons Jul 26 '16 at 14:03

If my Python programming is to be believed, the minimum number of moves required is 41:

• Care to share your program? – wKavey Jul 26 '16 at 16:56
• What is this, CodeGolf.se? ;) – Zibbobz Jul 26 '16 at 17:27
• @wKavey Here you go: pastebin.com/zeYGeQFY – squeamish ossifrage Jul 26 '16 at 18:36
• I can confirm - see my answer. – Jonathan Allan Jul 26 '16 at 23:42
• I want to upvote but the score is 41 like the answer so I can't – Fabich Jul 27 '16 at 12:28

It's relatively easy if you start at the exit and try to reach the starting point.

(Apologies for my bad paint skills)

I am 3 minutes late but I think I have a slightly different solution

using a less obnoxious colour

Very late to see this lovely puzzle, but I thought I'd post since

I can confirm that the $41$ move path posted by squeamish ossifrage is optimal.

My code outputs the same path (# may be visited . may not, numbers are the move numbers mod $10$ (to keep to one character, but still allowing easy-ish path following)

This path of 41 moves was found:

0#2#4#6#8#0.##.3....#....3.........9...1..
.............2.6.4.....2.........8...0...2
.1#3#5#7#9#1#....7...1...#4..#.7..#.#...#.
................5..........#.6.#........3.
.##.#.#.#..##...8..#0..#...5......#.#.4...
............#....#9..#.....#...##.........
###.##.###.##..........##..#.#..#..#...5#7
...............#........###..#..#..#...8..
###########.#.....#.##...........#...#.#6.
................#.#....#.........#...#..9.
##.##.#######...#.#..#...#.#.#............
#...........####...#.#...#.#.#.#.##..##0..
##.########.#..#...#...#......##...###.#.1

Python code:

MAZE_TEXT = '''
###########.##.#....#....#.........#...#..
.............#.#.#.....#.........#...#...#
.############....#...#...##..#.#..#.#...#.
................#..........#.#.#........#.
.##.#.#.#..##...#..##..#...#......#.#.#...
............#....##..#.....#...##.........
###.##.###.##..........##..#.#..#..#...###
...............#........###..#..#..#...#..
###########.#.....#.##...........#...#.##.
................#.#....#.........#...#..#.
##.##.#######...#.#..#...#.#.#............
#...........####...#.#...#.#.#.#.##..###..
##.########.#..#...#...#......##...###.#.#'''

def solveDefault():
maze = makeMaze(MAZE_TEXT)
startRow = 0
startCol = 0
endRow = len(maze) - 1
endCol = len(maze[endRow]) - 1
path = solve(maze, startRow, startCol, endRow, endCol)
if not path:
print("No path was found")
return
solvedText = ''
for mazeRow, mazeRowText in enumerate(MAZE_TEXT.strip('\n').split('\n')):
for mazeCol, mazeChar in enumerate(mazeRowText):
if (mazeRow, mazeCol) in path:
solvedText += str(int(path.index((mazeRow, mazeCol))) % 10)
else:
solvedText += mazeChar
solvedText += '\n'
print("This path of {0} moves was found:".format(len(path) - 1))
print()
print(solvedText)

def makeMaze(mazeText):
return [[c == '#' for c in row] for row in mazeText.strip('\n').split('\n')]

def solve(maze, startRow, startCol, endRow, endCol):
if startRow < 0 or startRow > len(maze) or startCol < 0 or startCol > len(maze[startRow]):
raise ValueError("Start location ({0}, {1}) does not exist in the maze provided".format(startRow, startCol))
if not maze[startRow][startCol]:
raise ValueError("Start location ({0}, {1}) is not visitable in the maze provided".format(startRow, startCol))
if endRow < 0 or endRow > len(maze) or endCol < 0 or endCol > len(maze[endRow]):
raise ValueError("End location ({0}, {1}) does not exist in the maze provided".format(endRow, endCol))
if not maze[endRow][endCol]:
raise ValueError("End location ({0}, {1}) is not visitable in the maze provided".format(endRow, endCol))
if startRow == endRow and startCol == endCol:
return [(startRow, startCol)]
reachedByMoves = [dict([(None, [(startRow, startCol)])])]
endLoc = (endRow, endCol)
solved = False
while 1:
newLocs = set()
nextReached = dict()
for prevRC, curRCs in reachedByMoves[-1].items():
for rc in curRCs:
for nextRC in nextLocations(maze, *rc):
if nextRC not in newLocs and not any(nextRC in reached for reached in reachedByMoves[:-1]):
if rc in nextReached:
nextReached[rc].append(nextRC)
else:
nextReached[rc] = [nextRC]
if nextRC == endLoc:
break
else:
continue
break
else:
continue
break
else:
if nextReached:
reachedByMoves.append(nextReached)
solved = True
else:
break
continue
reachedByMoves.append(nextReached)
break
if solved:
p = [endLoc]
for reached in reachedByMoves[:0:-1]:
for fromRC, toRCs in reached.items():
if p[-1] in toRCs:
p.append(fromRC)
break
else:
raise ImplementationError("Successful path found but not traceable?")
return p[::-1]

def nextLocations(maze, row, col):
for rowDelta, colDeltas in ((-2,(-1,1)),(-1,(-2,2)),(1,(-2,2)),(2,(-1,1))):
newRow = row + rowDelta
if newRow >= 0 and newRow < len(maze):
for colDelta in colDeltas:
newCol = col + colDelta
if newCol >= 0 and newCol < len(maze[newRow]) and maze[newRow][newCol]:
yield newRow, newCol