UG PROGRAMMING ASSIGNMENT Sliding Puzzle Group Project Report due: September 30, Friday, 2016 (4-5 page, hard copy) Use nxn board for varying n. Thus, input size is n^2 Implement the following three srtategies: blind breadth-first search (BFS), blind depth-first search (DFS), and heuristic guided A* search. Additional algorithms are welcome, specially local searches that needs less memory. For A* search use the sum of textbook's 2 heuristic functions h1 and h2. h1 = number of number-pieces in wrong positions h2 = Manhattan distance of digits from their correct position. Measure the number of steps (single tile moves) to arrive at the correct board position as the complexity, from a randomly generated starting board.The complexity measure of a search algorithm should be the average of at least 100 experiments for each n, i.e., randomly generated starting boards. Plot this complexity for each search algorithm against n, on the same plot if possible, in order to compare the algorithms' growths with respect to n. Note unsolvabilty of some input: https://en.wikipedia.org/wiki/15_puzzle You may add a check for that if you can, and exclude such input instances from your experiments. Discuss your result. Appendix: codes (commented please). Hard copy: include snap shot of the date of printout, turn in the next clas or in office (push under my door) on Friday 1. Nate and Rafael 2. Gregory and Jennifer 3. Emily and Andre 4. Jonathan and Matthew 5. Shiru and (Brian) 6. Kevin and Will 7. (Nicholas and Louay) () are my additions