When I was young, I played an ancient Indian board game called Snakes and Ladders, a small example of which is shown to the right. The rules of the game follow. • You start at square 1. • On each turn, you roll a six-sided dice and move forward the number of squares indicated on the dice (1 to 6). 21 22 23 24 25 20 816 • If you land on the last square (in this case 25), the ends. game 199876 12345 • If you land beyond the last square, you remain on the original square. • If you land on a square at the foot of a ladder, you move up the ladder to the square at the top. • If you land on a square at the head of a snake, you slide down the snake to the square at the bottom. In this example, if you land on the ladder at square 2, you move up to square 14. If you land on the snake at square 18, you slide down to square 4. Problem Given an instance of the Snakes and Ladders, find the least number of dice rolls that takes you from the start to the end of the game. Requirements 1) Create an instance S of a Snakes and Ladders board. 2) Using a breadth-first search, find the least number of dice rolls from the start to final position in S. 3) Return the sequence itself. You may need to include additional information to reconstruct the sequence of dice rolls.

When I was young, I played an ancient Indian board game called Snakes and Ladders, a small example of which is shown to the right. The rules of the game follow. • You start at square 1. • On each turn, you roll a six-sided dice and move forward the number of squares indicated on the dice (1 to 6). 21 22 23 24 25 20 816 • If you land on the last square (in this case 25), the ends. game 199876 12345 • If you land beyond the last square, you remain on the original square. • If you land on a square at the foot of a ladder, you move up the ladder to the square at the top. • If you land on a square at the head of a snake, you slide down the snake to the square at the bottom. In this example, if you land on the ladder at square 2, you move up to square 14. If you land on the snake at square 18, you slide down to square 4. Problem Given an instance of the Snakes and Ladders, find the least number of dice rolls that takes you from the start to the end of the game. Requirements 1) Create an instance S of a Snakes and Ladders board. 2) Using a breadth-first search, find the least number of dice rolls from the start to final position in S. 3) Return the sequence itself. You may need to include additional information to reconstruct the sequence of dice rolls.