CS 7375 Spring 2023 Assignment 1 Guidelines 2/2/2023 Problem Submission Rules: 1) Detection of plagiarism will result in Failing grade. Students must do this assignment by themselves. 2) After completion, your work must be submitted to an assignment folder in D2L by a corresponding deadline. 3) Late assignments will be accepted up to 24 hours after the due date for 50% credit. Assignments submitted more than 24 hours late will not be accepted for credit. 4) It is much better to submit a partial/failed-attempt solution than none. Include the circumstances of the incompletion in your report. Question: 8 Puzzle Problem The 8 puzzle consists of eight numbered, movable tiles set in a 3x3 frame. One cell of the frame is always empty thus making it possible to move an adjacent numbered tile into the empty cell. Start with a random state (cannot be fixed). The goal state is listed below. 1 2 3 8 4 7 6 5 The program is to change the initial configuration into the goal configuration. A solution to the problem is an appropriate sequence of moves. Try to implement Breadth-First Search (BFS), Depth-First Search (DFS), and Uniform-Cost Search (UCS) to solve this problem. Requirements: 1. You can choose any language you would like to use only from the following: C/C++, C#, Java, Python (preferred). You need to show understanding of the algorithms. In other words, the code should be wellcommented (That will be related to your final score). 2. Submit a PDF file of a written report, clearly describe your design and your test cases (screen shots). Please include your codes as needed in the PDF file. Please do not take codes from the website if possible. Try to understand the algorithm and implement the algorithm by your own. 3. Upload your code to GitHub/Bitbucket/etc and include a link to the code in the PDF file. Alternatively, you can upload your code file (such as code.py) to D2L. 4. You can work on the assignment solely or with others (up to 3 people). Please list all your names + KSU IDs at the very beginning of the PDF file. 5. Due date: Sunday 2/19/2022 11:59pm. Hints: In this assignment, the blank space can be represented by the number 0. A convenient way to consider the steps to the solution is the apparent movement of the blank space as pieces are moved; this metaphor will be provided as one interpretation of the solution here. The solutions to the puzzles that are shown here were generated using a search algorithm. Sample Puzzle #1 Consider the following starting configuration of the 8-puzzle: . The solution to this puzzle takes six moves. First, the two is moved up, the six is moved left, the five is moved down, the four is moved down, the three is moved right, and the two is moved up. If you consider that the space is moving, its moves are: down, right, up, up, left, down. The intermediate states with the movement of the space look like this: Current board layout: ._______. | 1 3 4 | "FIRST, from here, move DOWN." | 8 0 5 | | 7 2 6 | --------- Current board layout: ._______. | 1 3 4 | "SECOND, from here, move RIGHT." | 8 2 5 | | 7 0 6 | --------- Current board layout: ._______. | 1 3 4 | "THIRD, from here, move UP." | 8 2 5 | | 7 6 0 | --------- Current board layout: ._______. | 1 3 4 | "NEXT, from here, move UP." | 8 2 0 | | 7 6 5 | --------- Current board layout: ._______. | 1 3 0 | "THEN, from here, move LEFT." | 8 2 4 | | 7 6 5 | --------- Current board layout: ._______. | 1 0 3 | "THEN, from here, move DOWN." | 8 2 4 | | 7 6 5 | --------- Current board layout: ._______. | 1 2 3 | "Done." | 8 0 4 | | 7 6 5 | --------- And thus we are finished, with path (D R U U L D). Sample Puzzle #2 Consider the following starting configuration of the 8-puzzle: . This puzzle also requires six moves to solve. These steps are to move the seven to the left, the six down, the two to the left, the four down, the three left, and the two up. The solution, in terms of the movement of the space, is thus right, up, right, up, left, down. The solution looks like this: Current board layout: ._______. | 1 3 4 | "FIRST, from here, move RIGHT." | 8 6 2 | | 0 7 5 | --------- Current board layout: ._______. | 1 3 4 | "SECOND, from here, move UP." | 8 6 2 | | 7 0 5 | --------- Current board layout: ._______. | 1 3 4 | "THIRD, from here, move RIGHT." | 8 0 2 | | 7 6 5 | --------- Current board layout: ._______. | 1 3 4 | "NEXT, from here, move UP." | 8 2 0 | | 7 6 5 | --------- Current board layout: ._______. | 1 3 0 | "THEN, from here, move LEFT." | 8 2 4 | | 7 6 5 | --------- Current board layout: ._______. | 1 0 3 | "THEN, from here, move DOWN." | 8 2 4 | | 7 6 5 | --------- Current board layout: ._______. | 1 2 3 | "Done." | 8 0 4 | | 7 6 5 | --------- And thus we are finished, with path (R U R U L D).