Study CommonsRead · reason · practise

Home / Reasoning / Shortest Path: Find the Fewest Moves on a Grid

Reasoning & Coding · Coding

Shortest Path: Find the Fewest Moves on a Grid

Count moves on a grid, work out why a wall forces a detour, compare routes and use a number wave to find the shortest path from S to G.

Grades 3–5 · 16 practice questions · Original material
Learning objectiveFind the fewest moves between two squares on a grid by counting across plus down, adjust for walls that force a detour, compare routes and check the answer with a numbered distance wave.

The idea

A delivery driver wants the quickest way across town, not just any way. Computer programs face the same question all the time: of all the routes that work, which one takes the fewest steps? The answer is called the shortest path.

On our grids, one move takes the robot to the square directly left, right, above or below. There are no diagonal moves and the robot cannot enter a dark wall square. S is the start and G is the goal. Count moves, not squares: the robot is already standing on S, so a row of 6 squares from S to G is 5 moves.

With no walls, there is a quick rule. Count how many rows apart S and G are and how many columns apart they are, then add. If G is 2 rows down and 4 columns across, the fewest moves is 2 + 4 = 6. Many different routes can tie for the shortest, because the same moves can be done in a different order.

Walls change things. When a wall blocks the direct way, the robot must go around it, and the rule becomes a lower limit, not the answer. Find the gap in the wall, add up the moves to it, through it and on to G, and compare any other ways around.

A number wave checks your work. Write 0 on S, 1 on every square one move from S, 2 on every square one move from those, and keep spreading outward, never through a wall. The number that lands on G is the fewest moves. To find a route, start at G and step to a neighbour with a number one smaller each time.

Worked examples

Example 1 · No walls: add across and down

What is the fewest number of moves from S to G, and is there only one shortest route?

A 3 by 5 grid with no walls. S is the top left square and G is the bottom right square.SG
A 3 by 5 grid with no walls. S is the top left square and G is the bottom right square.
  1. G is 2 rows down and 4 columns across from S.
  2. Add them: 2 + 4 = 6 moves.
  3. Any order of 2 Down moves and 4 Right moves works, for example Right 4, Down 2 or Down 2, Right 4. So there are many shortest routes, all with 6 moves.

6 moves. Many routes tie for the shortest.

Example 2 · A wall makes a detour

Route A goes through the nearer gap and Route B through the farther gap. Which is shorter, and by how much?

A 4 by 5 grid. S is the top left square and G is the top right square. A wall fills the third column in the top two rows. The bottom two rows are open.SG
A 4 by 5 grid. S is the top left square and G is the top right square. A wall fills the third column in the top two rows. The bottom two rows are open.
  1. Without the wall, G is only 4 moves away along the top row. The wall blocks that.
  2. Route A uses the gap in row 3: Down 2, Right 4, Up 2 is 2 + 4 + 2 = 8 moves.
  3. Route B uses the gap in row 4: Down 3, Right 4, Up 3 is 3 + 4 + 3 = 10 moves.
  4. The nearer gap saves 2 moves each way.

Route A is shorter, with 8 moves. Route B has 10 moves.

Example 3 · Check with a number wave

The numbers show the fewest moves from S to each square. What is the fewest number of moves to G, and what is one shortest route?

A 3 by 5 grid of distance numbers. The top row reads S, 1, 2, 3, 4. The middle row reads 1, wall, wall, 4, 5. The bottom row reads 2, 3, 4, 5, G.S12341452345G
A 3 by 5 grid of distance numbers. The top row reads S, 1, 2, 3, 4. The middle row reads 1, wall, wall, 4, 5. The bottom row reads 2, 3, 4, 5, G.
  1. Each square holds one more than the smallest neighbour that is closer to S, so the numbers grow by 1 as they spread around the wall.
  2. G sits beside a 5 (above it and to its left), so G is 5 + 1 = 6 moves from S.
  3. Trace back from G: 5, 4, 3, 2, 1, S. Going forward, that is Right 4, Down 2, which is 6 moves.

6 moves. One shortest route is Right 4, Down 2.

Common mistakes

Counting the starting square as a move.

Why this fails: The robot is already on S. A row of 6 squares from S to G needs 5 moves, not 6.

Cutting a diagonal.

Why this fails: A move goes to a touching square, so a diagonal shortcut is really two moves, one across and one down.

Using rows plus columns when a wall blocks the way.

Why this fails: Across plus down is the answer only on an open grid. With a wall it is just the lowest the answer could be, so trace the detour.

Choosing the first gap you see.

Why this fails: Compare every way around the wall. A gap that looks closer to S can still lead to a longer route overall.

Thinking only one route can be shortest.

Why this fails: The same moves in a different order often tie. Any route with the fewest moves counts as a shortest route.

Foundation

Foundation practice

Count moves, not squares. Add rows apart and columns apart.

Concept

1. In this lesson, what counts as one move?

  1. From a square to a square diagonally across the corner
  2. Any slide in a straight line until the robot reaches a wall
  3. From a square to the square right beside it, directly above it or directly below it
  4. From a square to a square two spaces away in one jump
Count the moves

2. There are no walls. What is the fewest number of moves from S to G?

  1. 8
  2. 9
  3. 5
  4. 10
A 4 by 6 grid with no walls. S is the top left square and G is the bottom right square.SG
A 4 by 6 grid with no walls. S is the top left square and G is the bottom right square.
Count the squares

3. A shortest route takes 6 moves. How many squares does the robot stand on, counting S and G?

  1. 6
  2. 7
  3. 5
  4. 8
Count the moves

4. There are no walls. How many moves does it take to get from S to G in this row?

A single row of eight squares with S on the left end and G on the right end.SG
A single row of eight squares with S on the left end and G on the right end.
Spot the longer route

5. There are no walls. Every route below reaches G. Which one is NOT a shortest route?

  1. Right 3, Down 2
  2. Down 2, Right 3
  3. Right 1, Down 2, Right 2
  4. Right 3, Down 3, Up 1
A 4 by 4 grid with no walls. S is the top left square. G is in the third row, in the last column.SG
A 4 by 4 grid with no walls. S is the top left square. G is in the third row, in the last column.

Practice

Practice practice

Go around walls, compare routes and read a number wave.

Detour

6. The wall blocks the direct way. What is the fewest number of moves from S to G?

  1. 6
  2. 8
  3. 9
  4. 7
A 4 by 5 grid. S is the top left square. A wall fills the third column in the top three rows. G is in the third row, last column. The bottom row is open.SG
A 4 by 5 grid. S is the top left square. A wall fills the third column in the top three rows. G is in the third row, last column. The bottom row is open.
Compare routes

7. Route A: Up 1, Right 4, Down 1. Route B: Down 3, Right 4, Up 3. Both reach G without touching a wall. Which statement is true?

  1. Route B is shorter, by 4 moves
  2. Route A is shorter, by 2 moves
  3. The routes are the same length
  4. Route A is shorter, by 4 moves
A 5 by 5 grid. S is in the second row, first column. G is in the second row, last column. A wall fills the middle column in rows 2 to 4. Rows 1 and 5 are open.SG
A 5 by 5 grid. S is in the second row, first column. G is in the second row, last column. A wall fills the middle column in rows 2 to 4. Rows 1 and 5 are open.
Number wave

8. Each number shows the fewest moves from S to that square. What number belongs in the ? square?

  1. 4
  2. 3
  3. 5
  4. 2
A 3 by 4 grid showing distance numbers. The top row reads S, 1, 2, 3. The middle row has a wall, 2, a wall, 4. The bottom row reads 4, 3, a question mark, G.S1232443?G
A 3 by 4 grid showing distance numbers. The top row reads S, 1, 2, 3. The middle row has a wall, 2, a wall, 4. The bottom row reads 4, 3, a question mark, G.
Write a route

9. Write one shortest route from S to G in words, such as "Right 2, Down 1". Then say how many moves it has.

A 3 by 4 grid. S is the top left square. A wall fills the third column in the top two rows. G is the bottom right square.SG
A 3 by 4 grid. S is the top left square. A wall fills the third column in the top two rows. G is the bottom right square.
Concept

10. Mia adds one extra wall to a grid. Which statement about the fewest moves from S to G must be true?

  1. It gets longer every time a wall is added
  2. It stays the same or gets shorter, because walls guide the robot
  3. It stays the same or gets longer; it can never get shorter
  4. It always changes by exactly 2 moves
Count the routes

11. There are no walls. How many different shortest routes (4 moves each) lead from S to G?

  1. 3
  2. 6
  3. 4
  4. 9
A 3 by 3 grid with no walls. S is the top left square and G is the bottom right square.SG
A 3 by 3 grid with no walls. S is the top left square and G is the bottom right square.

Challenge

Challenge practice

Detours, stops on the way and reasoning about routes.

Detour

12. The wall in the fourth column leaves a gap only in the bottom row. What is the fewest number of moves from S to G?

  1. 6
  2. 12
  3. 9
  4. 8
A 5 by 7 grid. S is the fourth row, first column. G is the fourth row, last column. A wall fills the fourth column in rows 1 to 4. The bottom row is open.SG
A 5 by 7 grid. S is the fourth row, first column. G is the fourth row, last column. A wall fills the fourth column in rows 1 to 4. The bottom row is open.
Stop on the way

13. The robot must pick up the star (*) on the way to G. What is the fewest number of moves for the whole trip?

  1. 8
  2. 4
  3. 10
  4. 6
A 3 by 5 grid. S is the top left square and G is the top right square. Walls sit in the second and fourth columns of the middle row. A star is in the bottom row, third column.SG*
A 3 by 5 grid. S is the top left square and G is the top right square. Walls sit in the second and fourth columns of the middle row. A star is in the bottom row, third column.
Reason

14. Could a shortest route ever step onto the same square twice?

  1. Yes, whenever a wall is in the way
  2. Yes, if two shortest routes cross each other
  3. No: cutting out the loop would make a shorter route
  4. Only if G is in a corner
Fix the thinking

15. Jin says the fewest moves from S to G is 3, because G is 3 columns to the right. Is Jin right? Explain and give the correct number.

A 2 by 4 grid. S is the top left square. A wall is directly to the right of S. G is the top right square. The bottom row is open.SG
A 2 by 4 grid. S is the top left square. A wall is directly to the right of S. G is the top right square. The bottom row is open.
Reason

16. The shortest route from S to G is 6 moves and there are no walls. The robot may step back and forth. Could it reach G in exactly 9 moves?

  1. Yes: add 3 extra moves at the end
  2. No: every route is 6 plus an even number of extra moves
  3. Yes, but only if there is a wall
  4. No, because 9 is bigger than the longest possible route
A 3 by 5 grid with no walls. S is the top left square and G is the bottom right square.SG
A 3 by 5 grid with no walls. S is the top left square and G is the bottom right square.

Answer key

  1. 1. From a square to the square right beside it, directly above it or directly below it
    A move goes to one of the four touching squares: left, right, up or down. A diagonal shortcut is not allowed, a long slide counts as several moves, and a jump of two spaces is two moves.
  2. 2. 8
    G is 3 rows down and 5 columns across from S, so the fewest moves are 3 + 5 = 8. Choosing 9 counts the starting square as a move. Choosing 5 treats a diagonal as one move, which is not allowed. Choosing 10 counts squares (4 + 6) instead of moves.
  3. 3. 7
    The robot stands on S before it moves and on a new square after each of the 6 moves, so it stands on 1 + 6 = 7 squares. Choosing 6 forgets S. Choosing 5 takes both ends away, and 8 adds a square that is not there.
  4. 4. 7 moves.
    S and G are the two ends of a row of 8 squares. The robot is already standing on S, so it only needs to move onto the other 7 squares. Answering 8 counts the starting square.
  5. 5. Right 3, Down 3, Up 1
    The shortest route has 3 + 2 = 5 moves. The first three routes each make exactly 5 moves in a different order, so they are all shortest. Right 3, Down 3, Up 1 goes one row too far down and has to step back up, which makes 7 moves.
  6. 6. 8
    The only gap is along the bottom row. The robot goes down 3, right 4 and up 1, which is 3 + 4 + 1 = 8 moves. Choosing 6 is the answer if the wall were not there (2 + 4). Choosing 9 counts the starting square, and 7 stops one move short of G.
  7. 7. Route A is shorter, by 4 moves
    Route A makes 1 + 4 + 1 = 6 moves and Route B makes 3 + 4 + 3 = 10 moves, so Route A is shorter by 4. Route B is not shorter just because it looks bigger on the page, and the difference is 4, not 2: Route B is 2 moves longer going down and 2 moves longer coming back up.
  8. 8. 4
    The square to the left of ? holds a 3, and ? is one move further from S, so it is 3 + 1 = 4. Copying the 3 forgets that each step outward adds one. The 5 belongs to G, not the square before it, and 2 is too small because the squares beside ? hold 3 and the wall.
  9. 9. Example: Down 2, Right 3 (5 moves).
    The wall fills the top two squares of the third column, so the robot must cross in the bottom row. Down 2 and Right 3 gives 2 + 3 = 5 moves, which equals the number of rows plus columns apart, so nothing shorter exists. Right 1, Down 2, Right 2 is also a correct answer.
  10. 10. It stays the same or gets longer; it can never get shorter
    A new wall only takes squares away, so every old route is either still open or now blocked. The shortest length cannot get smaller. It does not always get longer, because the wall may sit away from every shortest route, and it does not always change by 2.
  11. 11. 6
    Every shortest route uses 2 Right moves and 2 Down moves in some order. The orders are RRDD, RDRD, RDDR, DRRD, DRDR and DDRR, which is 6. Choosing 3 or 4 misses some orders, for example the routes that turn in the middle. Choosing 9 multiplies 3 by 3, but a route has exactly 2 Right and 2 Down moves.
  12. 12. 8
    The robot goes down 1, right 6 and up 1: 1 + 6 + 1 = 8 moves. Choosing 6 ignores the wall, since S and G are in the same row 6 columns apart. Choosing 12 goes over the top of the wall instead, which is far from the gap. Choosing 9 counts the starting square.
  13. 13. 8
    Count in two parts. S to the star is 4 moves and the star to G is 4 moves, so the trip is 4 + 4 = 8. Choosing 4 is the shortest route straight to G, which skips the star. Choosing 6 stops too soon, and 10 adds extra moves that no part of the trip needs.
  14. 14. No: cutting out the loop would make a shorter route
    If a route returns to a square it has already stood on, everything between the two visits was wasted. Remove that loop and the route is shorter, so the original was not a shortest route. A wall can force a detour but never a repeat, and crossing routes meet at a square without either route using it twice. The corner does not matter.
  15. 15. No. The wall is in the way, so the fewest moves is 5.
    Jin counted the columns and forgot the wall. The robot must go down 1, right 3 and up 1, which is 1 + 3 + 1 = 5 moves. Counting across plus down only works when a wall does not block the direct way.
  16. 16. No: every route is 6 plus an even number of extra moves
    Each move changes the row number or the column number by 1. Any wasted step is undone by a step back, so extra moves come in pairs. The possible lengths are 6, 8, 10, 12 and so on, and 9 is not among them. Three extra moves cannot work because extra moves come in pairs. A wall would only remove options, and routes can be as long as you like.

Related practice

Code a robot path: turns, loops and the bugCoordinate plane: ordered pairsReasoning hub