AI-Based Problem Solving - Back to the Lost Keys

(Page 9 of 9 )

To conclude this chapter on problem solving, it seems only fitting to provide a Java program that finds the lost car keys described in the first example. The accompanying code employs the same techniques used in the problem of finding a route between two cities, so the program is presented without further explanation.

// Find the lost keys!
import java.util.*;
import java.io.*;
// Room information.
class RoomInfo {
  String from;
  String to;
  boolean skip;
  RoomInfo(String f, String t) {
    from = f;
    to = t;
    skip = false;
  }
}
class Keys {
  final int MAX = 100;
  // This array holds the room information.
  RoomInfo room[] = new RoomInfo[MAX];
  int numRooms = 0; // number of rooms
  Stack btStack = new Stack(); // backtrack stack
  public static void main(String args[])
  {
    String to, from;
    Keys ob = new Keys();
    ob.setup();
    from = "front_door";
    to = "keys";
    ob.iskeys(from, to);
    if(ob.btStack.size() != 0)
      ob.route(to);
  }
  // Initialize the room database.
  void setup()
  {
    addRoom("front_door", "lr");
    addRoom("lr", "bath");
    addRoom("lr", "hall");
    addRoom("hall", "bd1");
    addRoom("hall", "bd2");
    addRoom("hall", "mb");
    addRoom("lr", "kitchen");
    addRoom("kitchen", "keys");
  }
  // Put rooms into the database.
  void addRoom(String from, String to)
  {
    if(numRooms < MAX) {
      room[numRooms] = new RoomInfo(from, to);
      numRooms++;
    }
    else System.out.println("Room database full.\n");
  }
  // Show the route.
  void route(String to)
  {
    Stack rev = new Stack();
    RoomInfo r;
    int num = btStack.size();
    // Reverse the stack to display path.
    for(int i=0; i < num; i++)
      rev.push(btStack.pop());
    for(int i=0; i < num; i++) {
      r = (RoomInfo) rev.pop();
      System.out.print(r.from + " to ");
    }
    System.out.println(to);
  }
  /* If there is a path between from and to,
     return true, otherwise return false. */
  boolean match(String from, String to)
  {
    for(int i=numRooms-1; i > -1; i--) {
      if(room[i].from.equals(from) &&
        room[i].to.equals(to) &&
        !room[i].skip)
      {
        room[i].skip = true; // prevent reuse
        return true;
      }
    }
    return false; // not found
  }
  // Given from, find any path.
  RoomInfo find(String from)
  {
    for(int i=0; i < numRooms; i++) {
      if(room[i].from.equals(from) &&
        !room[i].skip)
      {
        RoomInfo r = new RoomInfo(room[i].from,
                           room[i].to);
        room[i].skip = true; // prevent reuse
        return r;
      }
    }
    return null;
  }
  // Determine if there is a path between from and to.
  void iskeys(String from, String to)
  {
    int dist;
    RoomInfo r;
  // See if at destination.
  if(match(from, to)) {
    btStack.push(new RoomInfo(from, to));
    return;
  }
    // Try another connection.
    r = find(from);
    if(r != null) {
      btStack.push(new RoomInfo(from, to));
      iskeys(r.to, to);
    }
    else if(btStack.size() > 0) {
      // Backtrack and try another connection.
      r = (RoomInfo) btStack.pop();
      iskeys(r.from, r.to);
    }
  }
}

DISCLAIMER: The content provided in this article is not warranted or guaranteed by Developer Shed, Inc. The content provided is intended for entertainment and/or educational purposes in order to introduce to the reader key ideas, concepts, and/or product reviews. As such it is incumbent upon the reader to employ real-world tactics for security and implementation of best practices. We are not liable for any negative consequences that may result from implementing any information covered in our articles or tutorials. If this is a hardware review, it is not recommended to open and/or modify your hardware.

Comments On: AI-Based Problem Solving

>>> Be the FIRST to comment on this article!

Buy this book...

This article is excerpted from chapter 10 of The Art of Java, written by Herbert Schildt (McGraw-Hill/Osborne, 2004; ISBN: 0072229713). Check it out at your favorite bookstore. Buy this book now.