Assignment - Problem Search Algorithms | Java (Programming ...

INFO405 Artificial Intelligence Homework 1 Instructions for submitting programs The beginning of the program should contain comments with your name. You should: 1. All source code. 2. A readme file: explaining how to compile and run the program 3. Executables (for Java, the .class or .jar files) 4. Screen shots of the program execution 5. Answers to questions asked below. Problem: Solving the 15-puzzle with uninformed search algorithms (15 points) On page 66 of the AIMA text, the 15-puzzle is introduced as a search problem. Here you are asked to write programs to solve the following 15 puzzle: Initial state: (an easy case) 1

2

4

5

7

3

8

9

6

11

12

13 10 14 Goal state:

15

1

2

3

4

5

6

7

8

9

10

11

12

13 14 15 First, you should download the Java implementation of algorithms from Norvig and Russell's Artificial Intelligence - A Modern Approach from http://code.google.com/p/aima-java/downloads/list. If you don't have Eclipse, you should install it now. Then you can do "File-Import...-Import Existing projects into Workplace" and import the aima-java project. If the import process doesn't work, you will need to create a new project in the same folder and then you will see the classes in Eclipse. Make sure you can run the EightPuzzleDemo. Now you need to extend the 8-puzzle implementation to solve the above 15-puzzle problem. To solve a problem with Uninformed Search, you need to write three classes . 1. a class that represents the Problem state .This class is independent of the framework and does NOT need to subclass anything . Let us, for the rest of these instruction, assume you are going to solve the NQueens problem . So in this step you need to write something like aima.search.nqueens.NQueensBoard . 2. a subclass of aima.search.framework.GoalTest.This implements only a single function ---boolean isGoalState(Object state); The parameter state is an instance of the class you created in step 1-a above. For the NQueensProblem you would need to write something like aima.search.nqueens.NqueensBoardTest 3. a subclass of aima.search.framework.SuccessorFunction .This generates a stream of Successors where a Successor is an object that represents an (action,

resultantState) pair. In this release of the code the action is a String (something like "placeQueenAt4,4" and the resultant State is an instance of the class you create in step 1.a . An example is aima.search.nqueens.NQueensSuccessorFunction. You can look at the EightPuzzleDemo.java, EightPuzzleBoard.java, EightPuzzleGoalTest.java, EightPuzzleSuccessorFunction.java files to figure out how 8puzzle is solved. In your own FifteenPuzzleDemo.java file, try to solve the 15-puzzle with BreadthFirstSearch, DepthFirstSearch, and IterativeDeepeningSearch. Do all of these four uninformed search algorithms work in this case? If not, report which algorithms work and which not, and explain why some algorithms fail and why some algorithms work. Now try to solve the 15-puzzle with following initial states: Case 1: At least 59 steps needed. 11

5

15

2

13

7

12

14 9

6

1

3 10 4 8 Case 2: At least 38 steps needed. 13

5

8

3

7

1

9

4

14

10

6

15

2 12 11 Do the four uninformed search algorithms still work for the above two more difficult cases? Why? Extra Credit (5 points) Implement a GUI for the 15-puzzle that shows the moves visually.