Instruction: For this assignment, you need to implement two different search algorithms to solve a puzzle...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
Instruction: For this assignment, you need to implement two different search algorithms to solve a puzzle problem. For this puzzle game, the GUI (graphical user interface) framework is provided that is developed by Python and pygame library. Below is a highlight of the provided framework. Two folders are given: 1. game folder - This folder deals with all the graphical or visual stuff, including pattern generation from an image, user mouse/keyboard interface, ext (You do not need to modify any files in this class). 2. sol folder - This folder has the file that provides a solution for a given puzzle. Three functions you can find from this file "bfs()", "dfs()" and "astar()". (For this project, you are required to implement the first two functions). These three functions are triggered by the three buttons in the GUI accordingly. What you need to do is to create Python project (suggested using the Interpreters 3.0 or higher) and copy these two folders directly to the created project. Then you need to install the pygame library, e.g. pip tools. Open the "puzzle.py" file in the game folder and run the code from there. Requirements: You need to implement the two functions in the "solution.py" file in the "sol" folder: 1. bfs (puzzle) (50%) 2. dfs(puzzle) (50%). The input argument "puzzle" is just a list of 9 numbers, e.g. [4, 3, 5, 2, 0, 1, 8, 6, 7], where the number "8" represents the empty space. You can use a print() function to see this input data. Both functions expect you to return a list of a path for the number "8" to move to make the sequence into a sequential order. Each element of the path represents a new position of the number "8" to move. The details are explaned in the section below. What should be submitted: Explanation of the returned "path" list: The path stores the moving steps of the empty space "8" to move though when you play the game you move the tiles rather than the empty space. Below shows an example of the moving path of "8" For example: Input: data = {0, 4, 1, 3, 8, 2, 6, 7, 5 }; Goal: make it into the correct order {0, 1, 2, 3, 4, 5, 6, 7, 8) You need to make the following changes on the number 8, since the number 8 represents the empty space, moving 8 to its neighboring numbers equals to moving the corresponding number to the empty space. Below it shows a demo of the steps: 041 swap with 4 081 swap with 1 018 swap with 2 012 swap with 5 012 382 342 >342 348 -> 345-... 675 675 675 675 678 So from this example, the right path should be {1, 2, 5, 8). WHY? You may thought it was {4, 1, 2, 5), since the number 8 has swapped with them in this order. That is true. However, we do not care which number it swapped with, but which position the number 8 has gone through. As the numbers can be in any positions during different time, which give no hint about where the number 8 is. In contrast, the positions are fixed. So we assume the positions are in the same order as an increasing sequence: [0] [1] [2] Fixed Position = [3] [4] [5] [6] [7] [8] Here, I use "[]" to distinguish the positions from the numbers. So now you can see, the number 8 starts from position [4], then swapped with number 4, which goes to the position [1]; then swapped with number 1, which goes to the position [2]; then swapped with number 2, which goes to the position [5]; finally, swapped with number 5, which goes to the position [8]. So the path you should assign to the parameter "&solution" with the path sequence {1, 2, 5, 8). solution.py puzzle.py highlight_digit.py GeneratePuzzle.py digit_sqr.py button.py X Node.py X 2 #This is the only file you need to work on. You do NOT need to modify other files 4 # Below are the functions you need to implement. For the first project, you only need to finish implementing bfs() and difs () 5 6 7 #here you need to implement the Breadth First Search Method def bfs (puzzle): 8 9 list = [] 10 A return list 11 12 #here you need to implement the Depth First Search Method def dfs (puzzle): 13 14 list = [] 15 0 return list 16 17 18 #This will be for next project 19 def astar (puzzle): list = [] 20 21 A return list 22 23 3 Instruction: For this assignment, you need to implement two different search algorithms to solve a puzzle problem. For this puzzle game, the GUI (graphical user interface) framework is provided that is developed by Python and pygame library. Below is a highlight of the provided framework. Two folders are given: 1. game folder - This folder deals with all the graphical or visual stuff, including pattern generation from an image, user mouse/keyboard interface, ext (You do not need to modify any files in this class). 2. sol folder - This folder has the file that provides a solution for a given puzzle. Three functions you can find from this file "bfs()", "dfs()" and "astar()". (For this project, you are required to implement the first two functions). These three functions are triggered by the three buttons in the GUI accordingly. What you need to do is to create Python project (suggested using the Interpreters 3.0 or higher) and copy these two folders directly to the created project. Then you need to install the pygame library, e.g. pip tools. Open the "puzzle.py" file in the game folder and run the code from there. Requirements: You need to implement the two functions in the "solution.py" file in the "sol" folder: 1. bfs (puzzle) (50%) 2. dfs(puzzle) (50%). The input argument "puzzle" is just a list of 9 numbers, e.g. [4, 3, 5, 2, 0, 1, 8, 6, 7], where the number "8" represents the empty space. You can use a print() function to see this input data. Both functions expect you to return a list of a path for the number "8" to move to make the sequence into a sequential order. Each element of the path represents a new position of the number "8" to move. The details are explaned in the section below. What should be submitted: Explanation of the returned "path" list: The path stores the moving steps of the empty space "8" to move though when you play the game you move the tiles rather than the empty space. Below shows an example of the moving path of "8" For example: Input: data = {0, 4, 1, 3, 8, 2, 6, 7, 5 }; Goal: make it into the correct order {0, 1, 2, 3, 4, 5, 6, 7, 8) You need to make the following changes on the number 8, since the number 8 represents the empty space, moving 8 to its neighboring numbers equals to moving the corresponding number to the empty space. Below it shows a demo of the steps: 041 swap with 4 081 swap with 1 018 swap with 2 012 swap with 5 012 382 342 >342 348 -> 345-... 675 675 675 675 678 So from this example, the right path should be {1, 2, 5, 8). WHY? You may thought it was {4, 1, 2, 5), since the number 8 has swapped with them in this order. That is true. However, we do not care which number it swapped with, but which position the number 8 has gone through. As the numbers can be in any positions during different time, which give no hint about where the number 8 is. In contrast, the positions are fixed. So we assume the positions are in the same order as an increasing sequence: [0] [1] [2] Fixed Position = [3] [4] [5] [6] [7] [8] Here, I use "[]" to distinguish the positions from the numbers. So now you can see, the number 8 starts from position [4], then swapped with number 4, which goes to the position [1]; then swapped with number 1, which goes to the position [2]; then swapped with number 2, which goes to the position [5]; finally, swapped with number 5, which goes to the position [8]. So the path you should assign to the parameter "&solution" with the path sequence {1, 2, 5, 8). solution.py puzzle.py highlight_digit.py GeneratePuzzle.py digit_sqr.py button.py X Node.py X 2 #This is the only file you need to work on. You do NOT need to modify other files 4 # Below are the functions you need to implement. For the first project, you only need to finish implementing bfs() and difs () 5 6 7 #here you need to implement the Breadth First Search Method def bfs (puzzle): 8 9 list = [] 10 A return list 11 12 #here you need to implement the Depth First Search Method def dfs (puzzle): 13 14 list = [] 15 0 return list 16 17 18 #This will be for next project 19 def astar (puzzle): list = [] 20 21 A return list 22 23 3
Expert Answer:
Answer rating: 100% (QA)
class State def initself state parent move depth cost key selfstate state selfparen... View the full answer
Related Book For
Corporate Finance
ISBN: 978-0077861759
10th edition
Authors: Stephen Ross, Randolph Westerfield, Jeffrey Jaffe
Posted Date:
Students also viewed these accounting questions
-
For this assignment you will prepare a list for the broad topic: Health. All you need to do is jot down your ideas that come to mind when you think of the word: Health. You don't have to write full...
-
For this assignment you will be required view the following two videos on YouTube. www.youtube.com/watch?v=bKJPxCPB-RE www.youtube.com/watch?v=rUns1Jbve0w 1) After watching the video please indicate...
-
For this assignment you will be creating a basic Hotel Reservation System. The program must meet the following guidelines: User can reserve up to 3 rooms at a time Your program will need to loop...
-
On January 1, 2010, Phelps Company purchased an 85% interest in Sloane Company for $955,000 when the retained earnings of Sloane Company were $150,000. The difference between implied and book value...
-
The Justice Department has been asked to review a merger request for a market with the following four firms. Firm Assets A .......... $156 million B .......... 130 million C .......... 45 million D...
-
BF 3 reacts with CsF to form CsBF 4 while there is no reaction between BBr 3 and CsBr. Explain these observations.
-
What is the purpose of the IT strategic planning process?
-
Midori Company had ending inventory at end-of-year prices of $100,000 at December 31, 2009; $119,900 at December 31, 2010; and $134,560 at December 31, 2011. The year-end price indexes were 100 at...
-
Your team have just been assigned to a major project in its capital budgeting division. This assignment requires your team to determine the net cash flows and Net Present Value (NPV), Internal Rate...
-
Planning is one of the most important management functions in any business. A front office managers first step in planning should involve determine the departments goals. Planning also includes...
-
Evening Story Corporation has sales of $4,507,670; income tax of $572,797; selling, general, and administrative expenses of $265,282; depreciation of $332,732; cost of goods sold of $2,586,830; and...
-
Miller Company's contribution format income statement for the most recent month is shown below: Sales (28,800 units) Variable expenses Total $ 172,800 103,680 Contribution margin 69,120 Fixed...
-
How can globalization and increased competition lead firms to sever ties with longtime suppliers?
-
1. When we set up business, we decided to operate as a sole proprietorship (with one as the owner and other as an employee). Why was this a sensible decision for you? Your answer should reference at...
-
Imagine that you are a consultant for an investment fund which sold a client a call option on a stack. Explain to yen]: management {who are smart but not mathematically trained} what risk is present...
-
1. Who's Liable When a Recalled Product Causes an Injury? and why 2. what would happen if the product was never recalled and the person gets hurt?
-
Question 3. Capital management The table below is based on the annual financial statements of four major banks in Australia, ANZ Bank (ANZ), Commonwealth Bank of Australia (CBA), National Australia...
-
Write a paper by answer the following question: Should Recycling Be Mandatory?
-
Do you agree or disagree with the following statement: In an efficient market, callable and noncallable bonds will be priced in such a way that there will be no advantage or disadvantage to the call...
-
What is the present value of an annuity of $ 6,500 per year, with the first cash flow received three years from today and the last one received 25 years from today? Use a discount rate of 7 percent.
-
Bell Tolls, Inc., has an average collection period of 36 days. Its average daily investment in receivables is $58,300. What are annual credit sales? What is the receivables turnover?
-
The nozzle of a mixing vibrator is tested for its number of vibrations. The vibration frequency, for each nozzle sample, can be modeled by a normal distribution with mean 128 and standard deviation...
-
If a random variable has the standard normal distribution, find the probability that it will take on a value (a) between 0 and 2.3 ; (b) between 1.22 and 2.43 ; (c) between -1.45 and -0.45 ; (d)...
-
Verify that (a) \(z_{0.005}=2.575\); (b) \(z_{0.025}=1.96\).
Study smarter with the SolutionInn App