Implement a Recursive Best-First Search (RBFS) to determine a solution for the 8-puzzle problem given an input initial state. The 8-puzzle should be a 3x3 puzzle similar to the 8-puzzle described in Chapter 3 of your textbook.

The initial state of your program should be input from a text file with numbers in rows separated by a character. Each row of the input file should be terminated by a newline character.

The Heuristic Function h(n) should be the sum of the Manhattan distance of all displaced tiles.

The empty square should be represented by the number 0

Each move should be represented by one of the actions: up, down, left, or right to indicate which direct the empty tile moves. The result of an action will switch locations of the 0 tile with the tile in the direction of the move (i.e. if the empty tile moves up, the tile in that location will move down to replace the old location of the 0 tile).

You may choose to implement your program in one of the following languages. If you would like to use another language, please gain prior approval from the TA and/or instructor. Proprietary/platform specific languages are not permitted, e.g. Objective-C, Swift (Apple) or C#, F#, Visual Prolog (Microsoft).

- Java

- Python

The Goal State should have the empty tile in the upper left corner of the puzzle, e.g.

0 1 2

3 4 5

6 7 8

When a solution is discovered, your program should display the sequence of board states state from the given initial state. For example:

3 1 2

4 7 5

6 0 8

-------------

3 1 2

4 0 5

6 7 8

-------------

3 1 2

0 4 5

6 7 8

-------------

0 1 2

3 4 5

6 7 8

You may use any code and/or algorithms from the textbook website resources http://aima.cs.berkeley.edu/code.html

Submit all code as a single archive file (i.e. zip, tar, etc.). All code for you program (including any 3rd party or textbook code) should be included in the archive file

**There is a working code online implemented in JAVA, you can use this as reference:

https://github.com/vivekvenkatesh/eight-puzzle-rbfs