Skip to main content

Implementing 8-puzzle search in java with full source code | download now

Image
By

The 8-puzzle problem

In this project you will implement a solution to the 8-puzzle by state-space search, using the search engine described in the lectures, and experiment with search strategies.

What you must do


Implementing 8-puzzle search

In the search2 folder in the Java download on the COM1005/2007 MOLE site is the code for the simple search engine and for Jugs problems. Note that you may have to recompile the code for your version of Java.

• Following the instructions in section 2.9 of the lecture notes, write classes to implement a state-space search for 8-puzzle problems.
• You should not need to change the code for the search engine except perhaps to control how much it prints as a search proceeds, and to stop the search after a given number of iterations (in an 8-puzzle the search tree can become large).
• Test your implementation with breadth-first searches for the following initial con- figurations and the same goal state as above:

Experimenting with Search Strategies


The search engine in the search4 folder implements the following search strategies:
• Breadth-first
• Depth-first
• Branch-and-Bound
• A*

In this case we won’t consider Depth-first and Branch-and-Bound is the same as Breadth- first because we have uniform costs. We’ll compare Breadth-first with 2 variants of A*.
• Adapt your 8-puzzle classes for search4. This means that your 8-puzzle state must now include a local cost g (always 1 for the 8-puzzle), and an estimated remaining cost estRemCost, which is used by A* and must be an underestimate of the true cost.
• Code two alternative methods in your 8-puzzle state class for computing estRemCost, assuming that the target pattern is always the same, as above.
o Hamming distance, which is the number of tiles out of place.
o Manhattan distance, which is the sum of the moves each tile needs to make before it is in its correct position.

The experiment is to compare the efficiency of breadth-first, A*(Hamming) and A* (Manhattan) over a number of puzzles. You are testing the hypothesis that A* is more efficient than breath-first, and the efficiency gain is greater the more difficult the problem and the closer the estimates are to the true cost. CAUTION: 8-puzzle search trees can be surprisingly large. You may have to wait a long time for a search to conclude.


Buy now

CONTACT DETAILS

For any other questions or other tasks please feel free to contact me
via email: mhassnainjamil@gmail.com
via WhatsApp: +92-324-7042178
via skype: hassnainjamil1
Labels:

Comments

Post a Comment

Popular posts from this blog

The Zoo Management System - entity relationship diagram & MS Access Database

By
Zoo Management System - Project Details: You are the employee of a big, worldwide working Zoo Management Company. Your company is responsible for the Zoo management. Your boss thinks it would be a great idea to store all data for each Zoo in a brand new self-developed ZOO Management System. Up to now, the ZOO management company has maps of each ZOO available. Your boss knows that you took a course in introduction on an ERP system, so he asks you if you could help designing such a system. Each ZOO must have the same organizational structure, which should look like this: Each Zoo has a Zoo-Address. Each Zoo has many visitors (Visitor Ticket Process (VTP). Many Zoo-Attractions belong to a Zoo. Module 1: Entity Relationship Diagram Design a ER (entity-relationship) diagram for your ZOO Management System. Use the information provided below with the entities and its attributes. Put the entities in the correct relationship to each other (organizational structure). Module 2: DB Implem...
1 comment
Read more

Human Physiology by Stuart Ira Fox [PDF] (12th edition) free download

By
21 comments
Read more

Sudoku Game Project in Java with full source code including GUI task

By
Introduction The purpose of the project is to try in practice the use of recursion and object-oriented program design. Please make sure to read this entire note before starting your work. Pay close attention to the sections on deadlines, deliverables, and exam rules. The problem Your task in this part of the project is to write a solver for Sudoku puzzles. Sudoku puzzles are a kind of crossword puzzles with numbers where the following two conditions have to be met: In each row or column, the nine numbers have to be from the set [1,2,3,4,5,6,7,8,9] and they must all be different.  For each of the nine non-overlapping 3x3 blocks, the nine numbers have to be from the set [1,2,3,4,5,6,7,8,9] and they ust all be different. The following two figures show a Sudoku puzzle and its solution. The input The input of your program, the Sudoku puzzles, is given in text files. More specifically, they are represented as nine lines of nine characters separated by spaces. The characters can be of two...
Post a Comment
Read more