(python 3)Consider a puzzle that consists of a n n grid where each field contains a value Xij ? N. Our player starts in the top left corner of the grid. Our goal is to reach the bottom right corner. RULES OF THE GAME: On each turn, you may move your player up, down, left or right. The distance by which the player moves in a chosen direction is given by the number of its current cell. You must stay within the board (you cannot go off the edge of the board). EXAMPLE: If your player is on a square with value 3, then you may move either three steps up, down, left or right (as long as you dont leave the board).

(a) Represent the problem as a graph problem. Formalize it by determining what is represented as the nodes and as the edges.

(b) Implement the class PuzzleBoard, as shown below. (Note: the following template is C++, you should adapt it to Python)

(c) Implement an algorithm that returns the minimum number of moves required to solve this problem. If there is no solution, your algorithm should say so.

class PuzzleBoard {

private: // up to you.

public:

// Problem b) PuzzleBoard(int boardSize, int[][] fields = null); // constructor should create the graph (as you defined it in 1a) with the values from fields. If fields is null, then initialize the fields of the board with random values between 1 and boardSize-1.

Bool makeMove(int direction); // makes the move (if valid), direction is 0 for up, 1 for right, 2 for down, 3 for right. Returns true if the move was valid, false otherwise.

Bool getResult(); // Returns false if game is not over yet, true if puzzle was solved std::ostream &operator<<(std::ostream &os, PuzzleBoard const &m); // in python, this is the __str__ method.

// Problem c) int solve(); // returns the minimum number of moves needed to solve the puzzle, and -1 if its not solvable.