ALGORITHM & COMPLEXITY

The 8-puzzle is a sliding puzzle made up of a frame of numbered square tiles arranged in a random order with one tile missing. The n-puzzle, is a famous problem that can be solved using Brute Force algorithms. Figure 1 show the 8-puzzle which have both start and goal states.

Based on the diagram in Figure 1 and moving rules in Figure 2, answer the following questions

1. By using Breadth First Search,

a. Produce the solution using State Space Tree.

b. Develop the code using matrix representation approach. You must find the solution from reliable and legit resources (websites, books, papers, journals, etc) and state minimum 5 of them.

c. Calculate the time complexity for 1(b).

2. By using Best First Search,

a. Produce the solution using State Space Tree

b. Develop the code using matrix representation approach. You must find the solution from reliable and legit resources (websites, books, papers, journals, etc) and state minimum 5 of them.

c. Calculate the time complexity for 2(b).

3. Do the complexity analysis by comparing the outcome of question 1(c) and 2(c).

Moving rules: Move empty space (blank) up, move blank to the right, move blank down and move blank to the left