---
title: "States, moves, graphs and trees"
course: "AI101 · AI, explained"
unit: "Building with rules and search"
lesson: 16 of 36
source: https://open.maestrocollege.edu/ai-explained/states-moves-graphs-and-trees
publisher: Maestro College
---

# States, moves, graphs and trees

Lesson 16 of 36 in **AI, explained** (AI101), unit "Building with rules and search". An open lesson from Maestro College.

## What the learner will be able to do
- Represent a problem as states, moves, a start state and a goal state.
- Understand a graph as nodes connected by edges stored as an adjacency list, and recognize the search tree that a search unfolds from the start state.
- Create a function that returns the valid moves from a given state.

## Teaching notes
STARTING STATE: router.py, untouched from here to L10. IN THIS LESSON: recall the GPS route planner from the Unit 1 challenge (places as states, roads as moves) and present the repo maze as the same problem in miniature. The learner prints load_maze() and pastes it; base the representation on what it shows, with states as (row, col) tuples. They draw a three-by-three grid as a graph and an adjacency list by hand, then write neighbors(maze, state) in a new search.py, returning open neighbors in the order up, down, left, right. Illustrate a small maze beside its state graph and two levels of its search tree. END STATE: neighbors() output for the start, committed as 'Add maze states and moves'.

## Course teaching approach
- Start from a real-world problem, then introduce the concept as the solution.
- Keep it true beginner level, hands-on, a little gamified. The learner should feel they are winning.
- Balance explanation, demonstration and practice. No copy-paste exercises: give small story-based tasks.
- End with one fun closed question about the topic.

## How to use this document
You are acting as a tutor for a learner on Maestro Open. Teach from this document, one small step at a time. Ask the learner to try things, wait for their answer, then give feedback. Keep it beginner-friendly. If the lesson involves code or spreadsheets and you cannot run them, ask the learner to try it on their own computer and paste the result back. Do not award grades, credit or certificates.

## When the lesson is done
The lesson is complete only when the learner has shown they can do every outcome listed above. Check each one with a small task or question; if an answer is wrong, explain and let them try again before moving on.
When every outcome is covered:
1. Say clearly: "Lesson 16 complete: States, moves, graphs and trees."
2. Give a two-line recap of what they learned.
3. Name the next lesson, "Breadth-first search" (lesson 17 of 36), and give the learner its link: https://open.maestrocollege.edu/ai-explained/breadth-first-search.md. Tell them to paste that page into this chat, or fetch it yourself if you can open links, then start it the same way. Do not start teaching the next lesson's topic until the learner has it.

Previous lesson: Chaining rules into an expert system
Next lesson: Breadth-first search