Stacks

The goal of this lab period is to update our LinkedList class to implement a Stack interface and begin work on the project.

---

Tasks

Implementing a Stack

1. Setup

   Make a new folder for this week's project.

   Copy over your LinkedList and LinkedListTests files from the previous project and download this Stack interface.

2. Implement the Stack interface

   Edit the declaration of your LinkedList class to implement the Stack interface: public class LinkedList<T> implements Queue<T>, Stack<T>, Iterable<T>

   In order to do so, you'll have to make sure you have all the methods from the Stack, namely:

   • public int size(): returns the number of items in the stack
   • public T peek(): returns the item on the top of the stack
   • public T pop(): removes and returns the item on the top of the stack
   • public void push(T item): adds the given item to the top of the stack
   One thing to be a bit careful about is that your peek method is used in both the Queue and Stack interfaces, so you'll need to ensure that your methods work in both cases.

   You can use these supplied StackTests.java to test your stack implementation.

Cell Class

In order to begin playing Sudoku, we'll write a simple Cell class, similar to the Cell class from Project 2 (Conway's Game of Life). The Cell will represent one location in a Sudoku board. If you haven't played Sudoku before, consider taking a minute to check out Sudoku.com. Accordingly, instead of being a somewhat binary object (Cells in Project 2 were either alive or dead), a cell in Sudoku can take on the values 1 - 9. A locked cell's value will be read from an input file and an unlocked cell's value is to be determined by the Sudoku solver.

1. Setup

   Start a Java file called Cell.java and make a public class called Cell. The Cell class should have four fields to hold the row index, column index, value, and whether the value is locked.

2. Write your constructors

   Write two constructors for the Cell class.

   • public Cell(int row, int col, int value) - initialize the row, column, and value fields to the given parameter values. Set the locked field to false;
   • public Cell(int row, int col, int value, boolean locked) - initialize all of the Cell fields given the parameters.
3. Write the accessor and mutator functions

   The following accessor and mutator functions manage the position of a cell (row, col), its value (number), and whether it is a locked value.

   • public int getRow() - return the Cell's row index.
   • public int getCol() - return the Cell's column index.
   • public int getValue() - return the Cell's value.
   • public void setValue(int newval) - set the Cell's value.
   • public boolean isLocked() - return the value of the locked field.
   • public void setLocked(boolean lock) - set the Cell's locked field to the new value.
4. Write a toString function

   The toString function should generate and return a representating String. In this case, have it return a string with the Cell's numeric value.

5. Write a few tests for your Cell class to validate your code.

Reading Files

The final part of the lab is to start a Board.java class and create a constructor that reads in a partially pre-filled Sudoku board from a file.

1. Create a new file Board.java. In it, create a new class Board. This will keep track of the Sudoku board itself. In particular, we'll need to manage 2D Array of Cells (this should be a class field) Add the following two methods:
   • public Board(): This is a constructor that creates a 9x9 2D array of Cells, all of which are initialized to have value 0.
   • public Board(String filename): This is a constructor that first calls the default constructor above, then calls the read method described below with filename.
   • public Cell get(int row, int col): this returns the Cell at the given row and col
   • public void set(int row, int col, int value): this sets the Cell at the given row and col to the given value
   • public void set(int row, int col, boolean locked): this sets whether the Cell at the given row and col is locked
2. Your second constructor should call the read method outlined below with filename. For this method to work, you will need to import java.io.* (the star means import everything from java.io) at the top of your file. The file reading part of the read method is already filled in for you, but you need to convert the data read in from the file into values in your sudoku board. You should approach this by first Download board1.txt and board2.txt and reading them. The non-zero values should be read in as locked cells. The zero values should be unlocked (they will be filled by your sudoku solving algorithm). Then write a main function that creates a new Board by passing in "board1.txt" as the filename. Running this code will cause the read method to print output. I recommend lining up the output with the print statements that produced it. This will give you a starting place for thinking about extracting specific values for cells in your board. There is one line marked with a TODO where the majority of your code will go, however you will need to add some code outside of the while loop and your code will be more than 1 line.

     public boolean read(String filename) {
       try {
         // assign to a variable of type FileReader a new FileReader object, passing filename to the constructor
         FileReader fr = new FileReader(filename);
         // assign to a variable of type BufferedReader a new BufferedReader, passing the FileReader variable to the constructor
         BufferedReader br = new BufferedReader(fr);
         
         // assign to a variable of type String line the result of calling the readLine method of your BufferedReader object.
         String line = br.readLine();
         // start a while loop that loops while line isn't null
         while(line != null){
             // print line
   	  System.out.println( line );
             // assign to an array of Strings the result of splitting the line up by spaces (line.split("[ ]+"))
             String[] arr = line.split( "[ ]+" );
             // let's see what this array holds: 
             System.out.println("the first item in arr: " + arr[0] + ", the second item in arr: " + arr[1]);
             // print the size of the String array (you can use .length)
             System.out.println( arr.length );
             // use the line to set various Cells of this Board accordingly
   	  // TODO THIS IS WHERE MOST OF YOUR CODE GOES
             // assign to line the result of calling the readLine method of your BufferedReader object.
             line = br.readLine();
         }
         // call the close method of the BufferedReader
         br.close();
         return true;
       }
       catch(FileNotFoundException ex) {
         System.out.println("Board.read():: unable to open file " + filename );
       }
       catch(IOException ex) {
         System.out.println("Board.read():: error reading file " + filename);
       }
   
       return false;
     }

   Once you have your constructor working, you may want to get rid of the print statements.
3. Define a Board toString method

   Write a public String toString() method that generates a multi-line string representation of the board. To make it easy to examine the board, you may want to have spaces that separate the 9x9 board into 3x3 blocks. When you have written this function, write a main method you can run to test the constructor and the toString methods. The main method should create a new Board object and then print it.

Lab checkpoint: Show us your code can read in a board correctly (constructor a board from board1.txt, then call the board's toString method and make sure it matches the file you read in!).

When you are done with the lab, go ahead and get started on the current project.

---