program代做、代写Python程序语言

日期：2023-09-25 09:26

Figure.1 A simple example of 8 puzzle

Project Description

An 8 puzzle is a simple game consisting of a 3 x 3 grid (containing 9 squares). One of the squares is

empty. The remaining 8 squares in the grid have a movable tile that is annotated with a digit ranging

from 1-8 (hence, the name 8 puzzle). The objective in solving 8-puzzle is to keep moving the tiles around

into different positions one by one (so you move one tile at a time, and then you think about your next

move) until the numbers on the 3x3 satisfy a "goal test". In this project, we are going to experiment with

more than one kind of goal test.

Files to Submit: As part of the project submission, we expect you to submit a zip file which contains only

three files. You will need to create and submit 2 files for the assignment by yourselves (See Table 1 below

for file name and explanation). Make sure that you name these files exactly like this.

File Name Explanation

File-1: solution_q1.py Include all functions that could generate answers

for each sub-problem of Q1. Include solutions to

all the problems in a single Python file. Make sure

that your solution file could be directly run in the

terminal (through the command line “python

solution_q1.py”)

File-2: solution_q2.py Include all functions that could generate answers

for each sub-problem of Q2. Include solutions to

all the problems in a single Python file. Make sure

DS/CMPSC 442: Artificial Intelligence

Fall 2023

Project-1 Solve the game of 8-puzzle

!"#$% &$' ()+, -(%(. /01

In this project, every student is required to implement search algorithms learned during the class using

Python 3.9 (this is important, make sure that your code compiles with Python 3.9) to solve the 8-puzzle

problem under different scenarios. The detail of each question is mentioned below.

that your solution file could be directly run in the

terminal (through the command line “python

solution_q2.py”)

File-3: proj-1-submission.pdf Answer the rest of the questions in this project

Table 1. Submission files for project-1

In solution.py, you should have the ability to read from a file named “input.txt” (includes initial state of 8

puzzle) and print out the corresponding solutions in the terminal. In “input.txt” (make sure that you use

the same file name), you should have a single line that specifies the starting state of the 8-puzzle

problem. As an example, take the initial state in Figure.1 as an example, the input.txt file should contain

a single line that looks like this (The symbol ”_” represents the empty square):

7,2,4,5,_,6,8,3,1

As another example, if the initial state that you wanted to specify was the right-hand side state shown in

Figure 1, then input.txt should look like this.

_,1,2,3,4,5,6,7,8

NOTE: Make sure that there is no whitespace in your input.txt, so no space or tab characters in

between the numbers. Only use a single comma without any whitespaces to delimit the different

numbers in your file.

And the expected output inside the Terminal is (In the expected output window below, the phrase

“#answer generated by your function.” is a coding style comment. We don’t expect that to be part of the

output):

The solution of Q1.1 is:

#answer generated by your function.

The solution of Q1.2 is:

#answer generated by your function.

The solution of Q1.3 is:

#answer generated by your function.

……

…

…

Figure.2 The expected output in the terminal when running “python solution_q1.py”

Evaluation: Your code will be graded manually by TA for technical correctness. To foster the grading

process, they will directly check the output printed in the terminal after running the command “python

solution.py” with different testing version of “input.py” that the instructor has created. So make sure your

code can run in the terminal smoothly before making the submission.

Academic Dishonesty: We will be checking your code against other submissions in the class for logical

redundancy (using automated software). If you copy someone else’s code and submit it with minor

changes, we will know. These cheat detectors are quite hard to fool, so please don’t try. We trust you all

to submit your own work only; please don’t let us down. If you do, we will pursue the strongest

consequences available to us.

Now, let’s get down to the fun part and let’s code up some search algorithms ? ? ?

Question-1 Find the solution of 8-puzzle

For question 1, our goal test is the following: “all numbers should be arranged in

increasing order on the 3x3 grid and the empty cell should be on the top left corner”

(HINT: this is exactly the goal test that we have talked about in class, and this goal

state can also be seen on the right side of Figure 1 above)

Q1.1 The Coding Component

Q1.1.a

Implement a DFS that can work with an “input.txt” file that contains any possible starting state. Please

notice that the output of this implementation should be the actual path returned. Submit your code into

File-1(solution_q1.py).

Q1.1.b

Implement a BFS that can work with an “input.txt” file that contains any possible starting state. Please

notice that the output of this implementation should be the actual path returned. Submit your code into

File-1(solution_q1.py).

Q1.1.c

Implement a UCS that can work with an “input.txt” file that contains any possible starting state. Assume

that each tile movement requires paying a cost of 1 unit. Please notice that the output of this

implementation should be the actual path returned. Submit your code into File-1(solution_q1.py).

Q1.1.d

Implement A* search that can work with an “input.txt” file that contains any possible starting state. For

the choice of your heuristic function, use the Manhattan distance heuristic (this can be found in Slide 64

of the A* slide deck that was covered in class). Submit your code into File-1(solution_q1.py). Please notice

that the output of this implementation should be the actual path returned.

Q1.1.e

Implement A* search that can work with an “input.txt” file that contains any possible starting state. For

the choice of your heuristic function, use the Straight Line Distance heuristic which calculates the straight

line distance between the source tile and the destination tile, and adds this distance across each tile on

the 3x3 grid (we covered this heuristic in class). Submit your code into File-1(solution_q1.py). Please notice

that the output of this implementation should be the actual path returned.

Q1.2 The Writing Component

For all parts to this question, use the following starting state of the 8-puzzle search problem:

7,4,_,1,2,5,8,3,6

Q1.2.a

For your DFS implementation in Q1.1.a, run it with the start state given above, and tell us how many node

expansions of the search tree did DFS do to find the solution? Write down the answer to this question

into file-3 (proj-1-submission.pdf).

Q1.2.b

For your BFS implementation in Q1.1.b, run it with the start state given above, and tell us how many node

expansions of the search tree did BFS do to find the solution? Write down the answer to this question

into file-3 (proj-1-submission.pdf).

Q1.2.c

For your UCS implementation in Q1.1.c, run it with the start state given above, and tell us how many node

expansions of the search tree did UCS do to find the solution? Write down the answer to this question

into file-3 (proj-1-submission.pdf). Note: Assume that each tile movement requires paying a cost of 1

unit.

Q1.2.d

For your A* implementation in Q1.1.d, run it with the start state given above, and tell us how many node

expansions of the search tree did A* search do to find the solution? Write down the answer to this

question into file-3 (proj-1-submission.pdf).

Q1.2.e

For your A* implementation in Q1.1.e, run it with the start state given above, and tell us how many node

expansions of the search tree did A* search do to find the solution? Write down the answer to this

question into file-3 (proj-1-submission.pdf).

Questions-2 Find the solution of modified 8-puzzle

We now want to solve a different search problem. For question 2, our goal test is the

following: “the sum of numbers in the top row of the 8-puzzle should sum up to 11. If

that is true, we have reached a goal state”.

Q2.1 The Coding Component

Q2.1.a

Modify your DFS implementation to handle the new goal test. Submit your code into File2(solution_q2.py). Please notice that the output of this implementation should be the actual path returned.

Q2.1.b

Modify your BFS implementation to handle the new goal test. Submit your code into File2(solution_q2.py). Please notice that the output of this implementation should be the actual path returned.

Q2.1.c

Modify your UCS implementation to handle the new goal test. Assume that each tile movement requires

paying a cost of 1 unit. Submit your code into File-2(solution_q2.py). Please notice that the output of this

implementation should be the actual path returned.

Q2.1.d

Modify your A* implementation to handle the new goal test. For the choice of your heuristic function, use

the Manhattan distance heuristic (this can be found in Slide 64 of the A* slide deck that was covered in

class). Submit your code into File-2(solution_q2.py). Please notice that the output of this implementation

should be the actual path returned.

Q2.1.e

Modify your A* implementation to handle the new goal test. For the choice of your heuristic function, use

the Straight Line Distance heuristic which calculates the straight line distance between the source tile and

the destination tile, and adds this distance across each tile on the 3x3 grid (we covered this heuristic in

class). Submit your code into File-2(solution_q2.py). Please notice that the output of this implementation

should be the actual path returned.

Q2.2 The Writing Component

For all parts to this question, use the following starting state of the 8-puzzle search problem:

8,1,4,5,2,6,3,7,_

Q2.2.a

For your DFS implementation in Q2.1.a, run it with the start state given above, and tell us how many node

expansions of the search tree did DFS do to find the solution? Write down the answer to this question

into file-3 (proj-1-submission.pdf).

Q2.2.b

For your BFS implementation in Q2.1.b, run it with the start state given above, and tell us how many node

expansions of the search tree did BFS do to find the solution? Write down the answer to this question

into file-3 (proj-1-submission.pdf).

Q2.2.c

For your UCS implementation in Q2.1.c, run it with the start state given above, and tell us how many node

expansions of the search tree did UCS do to find the solution? Write down the answer to this question

into file-3 (proj-1-submission.pdf). Note: Assume that each tile movement requires paying a cost of 1

unit.

Q2.2.d

For your A* implementation in Q2.1.d, run it with the start state given above, and tell us how many node

expansions of the search tree did A* search do to find the solution? Write down the answer to this

question into file-3 (proj-1-submission.pdf).

Q2.2.e

For your A* implementation in Q2.1.e, run it with the start state given above, and tell us how many node

expansions of the search tree did A* search do to find the solution? Write down the answer to this

question into file-3 (proj-1-submission.pdf).

---------------------------------------END OF PROJECT----------------------------------