Revisions History:
- Created Jan. 3rd 2007

SUDOKU is the latest puzzle craze. You can find Sudoku puzzles in both the Globe and Mail and the National Post newspapers. You start with a 9 * 9 grid in which some cells are filled with numbers in the range 1-9.

To solve a SUDOKU puzzle, complete the grid such that every number from 1 to 9 appears in:

• Each of the nine vertical columns
• Each of the nine horizontal rows
• Each of the nine 3 x 3 boxes

a) Write a Java program that uses recursion to solve SUDOKU puzzles. Your program should read the original grid from a text file using a method like readFile/1.

final int gridSideLength = 9;
final int gridSize = gridSideLength * gridSideLength;

public private static void readFile(String fileName) {
   try {
      Scanner scanner = new Scanner(new File(fileName));

      s = new int [gridSideLength] [gridSideLength];

      for (int row = 0;row <gridSideLength;row++)
         for (int col = 0; col < gridSideLength; col++) 
            s[row][col] = scanner.nextInt(); 

      scanner.close();
   } catch (FileNotFoundException e) {
        e.printStackTrace();}
}

To solve the puzzle use a brute force recursive method that tries all possibilities. The key recursive routine might look something like this:

     solve(int location)
       If location == gridSize // puzzle has been solved
          display_solution;
          return true;
       else
          Check each integer v between 1 and 9
              if v is OK in location //meaning that row, col and square conditions are met
                 set location to v
                 return solve(nextEmptyLocation(l))
              else return false

If you are unsure of how to go about designing a recursive solution you might want to look over the Maze_Search program.

b) Augment your program so that it reports timing statistics. If we call a Trial testing a single integer at a single location, how many trials per second does you code make. Show the output of your timing results in your testing.

c) Will your code always find a solution? Argue why or why not.

d) Using big-oh notation describe the complexity of your method.

Implement a class called Customer that represents a passenger on the airline DalhousieAir. Each Customer instance should keep track of its name, its address, its membership number in DalhousieAir's frequent flyer club, and the number of points accumulated in that club. Thus a Customer object has four  fields or instance variable:

name of type String
address of type String
membershipNumber of type int
membershipPoints of type int

Implement a class called Flight that represents a flight on DalhousieAir. Each Flight instance should keep track of its flight number, its origin, its destination, and its departure date and time. Thus a Flight instance has four fields (instance variables):

flight number of type int
origin of type String
destination of type String
departure of type String

Implement a class called AirlineTicket that represents a ticket for a flight on DalhousieAir. Each AirlineTicket instance should keep track of its passenger, its flight, and its price. Thus an AirlineTicket instance has three fields (instance variables):

passenger of type Customer
flight of type Flight
price of type double

For the Customer class, implement the following instance methods:

• public get (accessing) methods and protected set (modifying) methods for the fields (instance variables)
• a zero-argument constructor (i.e., one that takes no parameters)
• a constructor that accepts a name, address, and membership number, and sets the initial value of the membership points to zero
• a toString method that returns a String representing the Customer objectís name, address, membership number, and membership points.
• e.g., "Ming Chiang, 147 Hobson Road, Ottawa, #123456, 1500 points"
• an applyPoints method that takes an AirlineTicket as a parameter, calculates the points value of the ticket, and adds that value to the Customer objectís membership points. The applyPoints method should return the new value of the membership points. The points for a given AirlineTicket object are to be calculated by dividing the price of the AirlineTicket object by 100 and rounding to the nearest integer.

For the AirlineTicket class, implement the following instance methods:

• public get (accessing) methods and protected set (modifying) methods for the fields (instance variables)
• a zero-argument constructor (i.e., one that takes no parameters)
• a constructor that accepts a passenger, a flight, and a price
• a toString method that returns a String representing the AirlineTicket object. The String should include the passengerís name, the flight number, the origin, the destination, the departure, and the price. e.g., "Ming Chiang, Flight 1030, Ottawa to Calgary, 03/02/99 7:50 pm, $600.00"

For the Flight class, implement the following instance methods:

• public get (accessing) methods and protected set (modifying) methods for the fields (instance variables)
• a zero-argument constructor (i.e., one that takes no parameters)
• a constructor that accepts flight number, origin, destination, and a departure
• a toString method that returns a String representing the Flight object. The String should include the flight number, the origin, the destination, and the departure. e.g., "Flight 1030, Ottawa to Calgary, 03/02/99 7:50 pm"

Testing:

Be sure to test your code thoroughly. Create a class called TestTicket with several static test methods for testing your Customer, AirlineTicket, and Flight objects.

Choose meaningful test cases. You are responsible for developing a convincing test plan, i.e., for convincing the TAs that your methods work properly. Here is an example of a test method:

public static void test1() {

       Customer anisa;
       AirlineTicket ticketAnisa;
       Flight flightCalgary;
       anisa = new Customer();
       anisa.setName("Anisa Shane");
       anisa.setAddress("101 Shangrala Street, Calgary");
       anisa.setMembershipNumber(123456);
       anisa.setMembershipPoints(0);
       flightCalgary = new Flight(101, "Ottawa", "Calgary", "03/02/99 7:50 pm");
       ticketAnisa = new AirlineTicket(anisa, flightCalgary, 600.00);
       System.out.println(anisa);
       System.out.println(flightCalgary);
       System.out.println(ticketAnisa);
       System.out.println(anisa.applyPoints(ticketAnisa));
       System.out.println(anisa);
}

Note: Submit a printout of your Customer, AirlineTicket, and Flight classes and their methods along with a copy of the output generated by the testing. Include comments in your code and ensure that all of the output is clearly explained. Be sure to focus on encapsulation. Make everything private that it is reasonable to do so. Testing will be marked!