Project 1 – Informed Search

General Instructions for all options 

  • Use Blackboard to submit your assignment.
  • Please submit a document PDF via BB that shows your algorithm choice with a brief explanation of your approach to solve the problem
  • Submit your code via Github only – do not email, zip, upload etc.
  • You can create your document in Word, Google Docs, Slide Deck, etc, but only submit the output PDF. 
  • You need to Submit AND demo your program during office hours to receive a grade and/or feedback.
  • You can use either Java or Python in your implementations. 
  • No homework is accepted after the deadline.
  • The numbers beside the options correspond to the last digit of your GWID, please ensure that you are attempting the correct option. 

Option 1: Maze (for GWIDs ending with 3,7,6) 

You are given a separate maze file in text format. In this maze, you can go up, down, left, or right. The maze is 81*81 binary matrix where each line in the file represents a row and its values are separated with a space. 1 indicates a block that you cannot pass. 0 indicates a clear space that you can pass from. 

You should implement a program using Informed Search that reads this maze and takes any two points (start and end indices) as inputs and tells whether there is a path in this maze between such points. Please note that index starts at 0 in the following points. For example, given the start point (1,1) and the end point (1, 8), your program outputs‘YES’ if there exists at least one path between those two points and ‘NO’ if no path exists. 

Apply your program in the following positions and submit your answers.

Start Point End Point
(1,34) (15,47)
(1,2) (3,39)
(0,0) (3,77)
(1,75) (8,79)
(1,75) (39,40)

Option 2: Water Pitcher (for GWIDs ending with 0,5,8,9) 

You are given a text file with 2 lines. First line has a variable number of integers, comma separated. Second line has an integer. There are no comments etc. in the file. (Don’t bother trying to handle negative numbers, fractional numbers, alphanumeric test cases etc. I trust you know how to do that, and this class is not focused on that.) 

Input File Structure: 

input.txt 
1,4,10,15,22 // Represents the capacities of the different water pitchers 
// You also have access to a virtual “infinite” capacity pitcher
181 // Represents the Target quantity  

Sample Files: 

>> cat input1.txt 
2,5,6,72
143

>> cat input2.txt
3,6
2

>> cat input3.txt
2
143

>> cat input4.txt
2,3,5,19,121,852
11443

Output: 

Output is a single number which represents the number of steps. 

To Do: 

  • Implement a program that reads this input file and calculates the shortest path (number of steps) from initial state (all pitchers are empty) to the final state (where the “infinite” capacity pitcher has the target quantity). 
  • Any kind of water movement (from any pitcher to any other pitcher) represents one step.
  • Implement an informed search (A*) for this problem. 
  • Write test cases (JUnit or equivalent) to ensure to make sure your program works. Unit test code is also included in the grading. 

Things to Consider:

  • In your write up you need to explain your lower bound. If you don’t have a lower bound, that means you don’t have A* algorithm. 
  • If there is NO path, then simply return -1. 

Option 3: N-Puzzle (for GWIDs ending with 1,2,4) 

Write a program that solves N-puzzle in n*n grid such that you rearrange the square blocks of the puzzle to be in order with the fewest possible moves. The puzzle includes 1 to N numbers with one blank space and you can move the squares horizontally and vertically into the blank space. 8-puzzle is a 3*3 grid labeled 1 though 8 and one blank square. 15-puzzle is a 4*4 grid labeled 1 through 15 and one blank square. Use A* search algorithm in your implementation. 

Constraints: 3 <= n <= 6 

Input Format: A file with n lines; each line has n numbers separated by tab. This initiates the puzzle configuration. 0 refers to the blank space. You have n-puzzle.txt as a sample file. Your code should work in any data size within the constraints. 

Note : Graphical User Interface is NEITHER REQUIRED, NOR RECOMMENDED.