4. You've recently cleaned out your attic and discovered a hidden gem, your favorite wooden maze game from childhood. Th

[answerhappygod]

4 You Ve Recently Cleaned Out Your Attic And Discovered A Hidden Gem Your Favorite Wooden Maze Game From Childhood Th 1 (124.29 KiB) Viewed 43 times

4. You've recently cleaned out your attic and discovered a hidden gem, your favorite wooden maze game from childhood. This game requires you to tilt the board to guide a steel ball through the maze from the top left corner to the bottom right corner. You could never Isolve this game when you were younger, but as a good algorithms student, you know you can solve nearly any game with backtracking. To impress your younger self, you won't stop at just beating the game. You need to figure out every possible way to win the game. The wooden maze is represented as an n x n grid and an array Blocked[1...n, 1...n] which specifies the maze's walls. In this version of the game, you can only move the ball to the right (→) or down (↓) from any cell and the maze's walls block certain moves. Blocked[i, j] is a set that contains which moves you cannot make from cell (i, j) due to the maze's walls. For example, if Blocked[i, j] = {→} then you could not move right from cell (i, j) into cell (i, j+1), but moving down to cell (i+1, j) is still an option. You keep choosing non-blocked moves until you either get stuck and lose, or make it to the bottom right corner (n, n) and win. Describe an analyze an algorithm to compute the number of solution paths from the start position (1, 1) to the goal position (n,n). Solution: Figure 1. Two solution paths in the wooden maze game.