CSC 440 - Project 1
Solving Puzzles

Overview

Part 1 - Travelers on a Bridge

We will investigate a particular instance of this problem, where we have four travelers with travel times as noted below:

A -- 1 minute
B -- 2 minutes
C -- 5 minutes
D -- 10 minutes

Consider the search space for this problem.

1. What information must be kept at each search node?
2. What is the initial search node?
3. What is the goaltest function for this problem?
4. What operators should be used to generate the children of a node?
5. Draw the state space for this problem.

For each of the search strategies listed below

• how the contents of the OPEN and CLOSED lists for each iteration through the Pseudocode for Searching
• indicate which goal state is reached if any
• write down the solution path that reaches that goal.

1. breadth first search
2. depth first search
3. uniform cost search

General Pseudocode for Searching

Note: Things may need to be tailored a bit to each different search method being used.

  OPEN   = { startNode } // Nodes under consideration.
  CLOSED = { }           // Nodes we're done with.

  while OPEN is not empty
  { 
    remove an item from OPEN based on search strategy used
    - call it X

    if goalState?(X) return the solution found

    otherwise // Expand node X.
    {
        1) add X to CLOSED
        2) generate the immediate neighbors (ie, children of X)
        3) eliminate those children already in OPEN or CLOSED
        4) add REMAINING children to OPEN according to QUEUEING FUNCTION
    }
  }
  return FAILURE  // Failed if OPEN exhausted without a goal being found.

Part 2 - Programming Puzzles

First, you must have the user input the initial state for your puzzle. This can be done by devising an appropriate symbolic language to describe a state for your puzzle. Such a language should be similar in nature to the solution language described on the back of your puzzle cards.

You will need to implement the SearchNode interface with a class for your particular puzzle. This will need to have data members as we have described for a node in the search tree, such that it tracks the current state space, parent node, total path cost, depth, etc. It should be able to generate all successor states (children) based on the current state and applying all possible actions.

The SearchSolver class will be used by your main driver class, in which you will find implemented the pseudocode search algorithm from above for Breadth First Search. It will search through the nodes level by level and report the first goal node found. It will print out the solution path to the goal node in such a manner that it can be implemented by you on the physical puzzle and verified, along with the length of the solution path and the number of nodes expanded to reach that goal node. You must test your program on more than one of the puzzle cards to guarantee your program can find the appropriate solutions.

Part 3 - Altering the Search

• BFS: Breadth First Search (already programmed)
• DFS: Depth First Search
• GREEDY: Greedy Search

For GREEDY search, your program must implement a heuristic function. This heuristic function is designed by you, and should attempt to model your best guess as to the distance left to a goal node. The heuristic function at the goal nodes should be equal to 0.

Evaluation

1. Describe your heuristic function in easy-to-understand English.
2. What do you see as the weaknesses of your heuristic function?
3. Is your heuristic function admissible?
4. Which search technique do you believe worked the best on your puzzle and why?

Code

• Cup.java
• CupsNode.java
• SearchNode.java
• SearchSolver.java

What to Hand In