21
$\begingroup$

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.

enter image description here

Please, in your answer, clearly explain the path taken.

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

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

solution with 41 moves

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

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

enter image description here

(Apologies for my bad paint skills)

$\endgroup$
6
$\begingroup$

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

enter image description here

using a less obnoxious colour

![enter image description here

$\endgroup$
4
$\begingroup$

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]
                        newLocs.add(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
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.