代写CSC3100编程、代写Java编程语言

日期：2021-12-15 10:25

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:

1. The full score of the assignment is 100 marks.

2. Normal submission: 100 marks are given if a submission passes the test.

3. 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.

4. Late submission: 75 marks are given if it passes the test. No resubmission is allowed.

5. 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.

6. In case of identical copies, both submissions will be marked as zero. Similar rules apply to other

cases of plagiarism found.

Running Environment:

1. The submissions will be evaluated in Java environment under Linux platform.

2. 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.

3. 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.

4. In the test, each program is required to finish within 5 seconds of time, with no more than

128MB memory.

5. Each student is free to test his/her program in the evaluation platform before the submission.

Submission Guidelines:

1. Detailed submission guideline will be given in a separate manual around Nov. 29.

2. 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

8 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

0 1 3

4 2 5

7 8 6

After running the program, the output file will be:

moves.txt

0 1 3

4 2 5

7 8 6

1 0 3

4 2 5

7 8 6

1 2 3

4 0 5

7 8 6

1 2 3

4 5 0

7 8 6

1 2 3

4 5 6

7 8 0

Program Template:

There is no program template for this assignment.

Appendix

1. initial.txt

2. moves.txt

3. astar_algorithm.pdf