关于后端:CSC3100-重要提示

CSC3100 Assignment 3
Important Notes:

1. The assignment is an individual project, to be finished on one’s own effort.
2. Submissions before the deadline 6pm Dec. 6, 2021 are treated as normal submissions.
   Submissions within one week after the deadline are treated as late submissions.
3. Plagiarism is strictly forbidden, regardless of the role in the process. Notably, ten consecutive
   lines of identical codes are treated as plagiarism.
   Marking Criterion:
4. The full score of the assignment is 100 marks.
5. Normal submission: 100 marks are given if a submission passes the test.
6. Resubmission: For normal submissions that fail the test, a resubmission is allowed within one
   week after the marking. 75 marks are given if the resubmission passes the test.
7. Late submission: 75 marks are given if it passes the test. No resubmission is allowed.
8. Zero mark is given if: there is no (normal or late) submission; both normal and late submissions
   fail the test; a normal submission fails the test and there is no resubmission; a late submission
   fails the test.
9. In case of identical copies, both submissions will be marked as zero. Similar rules apply to other
   cases of plagiarism found.
   Running Environment:
10. The submissions will be evaluated in Java environment under Linux platform.
11. The submission is acceptable if it runsin any of recent versions of Java SDK environment. These
    versions include from Java SE 8 to the most recent Java SE 17.
12. The submission is only allowed to import three packages of (java.lang.; java.util.; java.io.*)
    included in Java SDK. No other packages are allowed.
13. In the test, each program is required to finish within 5 seconds of time, with no more than
    128MB memory.
14. Each student is free to test his/her program in the evaluation platform before the submission.
    Submission Guidelines:
15. Detailed submission guideline will be given in a separate manual around Nov. 29.
16. Inconsistency with or violation from the guideline leads to marks deduction.
    Problem Description:
    Write a program to solve the 8-puzzle problem (and its natural generalizations) using the A* search
    algorithm. The 8-puzzle problem is a puzzle invented in the 1870s. It is played on a 3-by-3 grid with
17. square blocks labeled 1 through 8 and a blank square. Your goal is to rearrange the blocks so that
    they are in order. You are permitted to slide blocks horizontally or vertically into the blank square.
    The following shows a sequence of legal moves from an initial board position to the goal position.
    An algorithmic solution to the problem is based on the classical A* search algorithm
    (https://en.wikipedia.org/wiki/A*_search_algorithm). We define a state of the game to be the
    board position, the number of moves made to reach the board position, and the previous state.
    First, insert the initial state (the initial board, 0 moves, and a null previous state) into a priority
    queue. Then, delete from the priority queue the state with the minimum priority, and insert onto
    the priority queue all neighboring states (those that can be reached in one move). Repeat this
    procedure until the state dequeued is the goal state. The success of this approach hinges on the
    choice of priority function for a state. We consider the following priority function:
    • Manhattan priority function. The sum of the distances (sum of the vertical and horizontal
    distance) from the blocks to their goal positions, plus the number of moves made so far to get
    to the state.
    There is a key observation here: to solve the puzzle from a given state on the priority queue, the
    total number of moves we need to make (including those already made) is at least its priority, using
    the Manhattan priority function. (This is true because each block must move its Manhattan
    distance from its goal position. Note that we do not count the blank tile when computing the
    Manhattan priorities.)
    Consequently, as soon as we dequeue a state, we have not only discovered a sequence of moves
    from the initial board to the board associated with the state, but one that makes the fewest
    number of moves.
    Functional Requirement
    Write a program called Puzzle8.java that reads the initial board from an input file (file name
    specified by the user) and outputs a file (file name specified by the user) with a sequence of board
    positions that solves the puzzle in the fewest number of moves.
    java Puzzle8 initial.txt moves.txt
    The input file will consist of the 3-by-3 initial board position. The input format uses“0”to represent
    the blank square. As an example,
    initial.txt
18. 1 3
19. 2 5
20. 8 6
    After running the program, the output file will be:
    moves.txt
21. 1 3
22. 2 5
23. 8 6
24. 0 3
25. 2 5
26. 8 6
27. 2 3
28. 0 5
29. 8 6
30. 2 3
31. 5 0
32. 8 6
33. 2 3
34. 5 6
35. 8 0
    Program Template:
    There is no program template for this assignment.
    Appendix
36. initial.txt
37. moves.txt
38. astar_algorithm.pdf