Lab 4: Stacks and the Sudoku Board

Watch someone solve a Sudoku and you will see a rhythm. They write a number in an empty square and check it: is that number already in the same row, column, or 3×3 block? If not, they move on to the next square. If every number they try conflicts, then an earlier choice was wrong. So they erase the number they wrote most recently and try a different one there. If nothing works there either, they erase the one before that. With luck, you could fill a whole puzzle without ever going back, but usually solving is a back-and-forth of choosing, checking, and undoing.

That back-and-forth needs a memory of your choices in order, so that you can always undo the last one first. On paper, the eraser and your own memory do this job. In a program, the data structure that remembers the last thing you did is called a stack, and Project 4, a Sudoku solver, is built on one.

This lab has two parts. First, using the software engineering idea of code reuse, you will build a stack from code you have already written in your LinkedList from Project 3, along with a new interface, Stack.java. Then you will build the two classes that represent a Sudoku puzzle: Cell, one square of the puzzle, and Board, the 9×9 grid that can read a puzzle from a file and print it.

For each task, you will first test your code yourself with small tests in main(), including tests you write on your own. Only when your own tests pass will you run Lab4Tester.java to check the cases you may have missed.

A stack: last in, first out

A stack is like a pile of plates. You can only add a plate to the top (push), look at the top plate (peek), or take the top plate off (pop). The plate you take off is always the one you put on most recently.

push(1)   push(2)   push(3)   pop() returns 3   pop() returns 2

                        [3]
              [2]       [2]          [2]
    [1]       [1]       [1]          [1]               [1]

A stack only ever touches one end. Think back to Lab 3: which end of your linked list can you add to and remove from without walking through the list?

Setup

In your personal Google Drive Projects folder, create a new folder named Project4. Copy your completed LinkedList.java from your Project3 folder into it. Then download these files into the same folder. Do not rename them.

Download Stack.java Download Cell.java Download Board.java Download Lab4Tester.java board1.txt solved.txt

Every file compiles as soon as you download it. Each method you need to write is marked TODO with its task number.

Use your own LinkedList. Do not download a new one or write a separate stack class. The point of Task 1 is that the list you already wrote can be a stack.

Testing Your Own Code with main()

Before you use the tester, you will test each method yourself. Testing means calling a method on a small example where you already know the right answer, and checking that your code gives that answer.

Cell.java and Board.java each have a main() method at the bottom with some tests already written for you. Each test prints the answer it should get (expected) and the answer your code produced (got):

getRow():   expected 2,     got 2
getValue(): expected 7,     got -1     <-- these do not match: look at getValue() or the constructor
isLocked(): expected false, got false
toString(): expected 7,     got 7

When every line matches, your code passes those tests. When a line does not match, the line tells you which method to look at.

Here is what one of those tests looks like in the code:

Cell a = new Cell(2, 5, 7);
System.out.println("getRow():   expected 2,     got " + a.getRow());

The first part, in quotes, is text you type yourself: the name of the method and the answer you expect. The last part, a.getRow(), actually calls your method, and its result is printed after got.

Your turn: write tests of your own

The provided tests do not check everything. After the provided tests in each task there is a TODO asking you to write one or more tests of your own, in the same style. To write a test:

  1. Choose a method and a small example: what will you create, and what will you call?
  2. Decide the expected answer before you run anything. Work it out on paper.
  3. Copy one of the provided println lines and change it to call your example.
  4. Run the file and compare expected with got.

Deciding the answer first is the important part. If you run the code first and then write down whatever it printed, the test cannot catch a mistake.

Test in main() first, then run the tester.

For each task: write the method, run your main() tests, fix anything that does not match, and write your own test. When every line matches, run the tester. The tester checks more cases, but your own tests are where you learn whether you understand what the method should do.

Run the Tester

javac *.java
java Lab4Tester          // runs Task 1, 2, 3, ... and stops at the first task that needs work
java Lab4Tester 4        // runs only Task 4

As in Lab 3, for every check the tester prints [PASS] or [FAIL]; a failure shows what was expected, what your code produced, and a hint. If your code throws an exception, you will see [CRASH]. If a check takes too long, you will see [TIMEOUT].

Lab workflow: Read the task → draw a picture → write the method → run the provided tests in main() → write your own test → run Lab4Tester.

Part 1: A Stack

Task 1 — Make LinkedList implement Stack

REUSE — sign a new contract with the code you already have.

Open Stack.java and read it. It is an interface: a list of method signatures with no bodies.

public interface Stack<T> {
    public int size();        // the number of items on the stack
    public T peek();          // the item on top, without removing it
    public T pop();           // removes and returns the item on top
    public void push(T item); // adds item to the top
}

Interfaces are contracts

An interface describes what a type can do without saying how. Stack says that anything called a stack can report its size and can push, pop, and peek. It says nothing about Nodes, arrays, or any other way of storing the items.

When a class says implements Stack<T>, it signs a contract: “I have every one of these methods, with exactly these signatures.” In Lab 3 we called implements Iterable<T> a promise, and that is a fine way to think about it. The difference is that Java enforces this promise. If a single method is missing or has the wrong signature, the class does not compile.

The contract benefits both sides:

  • The class that implements it is free to do the work however it likes. Your LinkedList and someone else's array-based stack can both be stacks.
  • The code that uses it can rely on those methods existing without knowing or caring which class is behind them. That is why a for-each loop works on your list: the loop only needs the Iterable contract.

A class can sign as many contracts as it likes, separated by commas. You cannot write new Stack<Integer>(), because an interface has no code to run; you create an object of a class that implements it.

Add Stack<T> to the contracts in your LinkedList class header:

public class LinkedList<T> implements Iterable<T>, Stack<T>

Now try to compile and read the error message. It names a method the contract requires that your class does not have yet. You already have size(). Write the other three:

Before writing anything, decide which end of the list is the top. Look at the methods you wrote in Lab 3. Two of them already do almost everything push and pop need. Each of your three methods should be short.

Think about it: which end is the top?

Suppose you made the end of the linked list the top of the stack. Draw a list of four Nodes and work through these questions:

  • To push, where does the new Node go? How many Nodes do you visit to get there?
  • To pop, which Node is removed? After removing it, which Node must have its next set to null, and how do you find that Node?
  • Now suppose your list also had a tail field pointing at the last Node. Which of your answers change, and which do not?

Then answer the same questions with the front of the list as the top. The tester pushes and pops a million items, so your choice matters.

Test it. LinkedList.java is your own file, so there are no tests in it yet. Copy these lines into the main() method of your LinkedList (you can replace or keep your Lab 3 tests), then run java LinkedList:

Stack<Integer> stack = new LinkedList<Integer>();
stack.push(1);
stack.push(2);
System.out.println("peek(): expected 2, got " + stack.peek());
System.out.println("pop():  expected 2, got " + stack.pop());
System.out.println("size(): expected 1, got " + stack.size());

// TODO (Task 1): Write at least two tests of your own. Ideas:
//   - What should pop() return when the stack is empty?
//   - Does peek() remove the item? Check size() after calling it.

In Project 4, the solver will declare its stack by the interface type:

Stack<Cell> stack = new LinkedList<Cell>();

The variable's type is the contract, Stack; the object is your LinkedList. Through this variable the solver can call only push, pop, peek, and size. It cannot reach into the middle of the list, so it is guaranteed to use the list as a stack and nothing else.

Part 2: The Sudoku Board

Sudoku in one paragraph

A Sudoku puzzle is a 9×9 grid divided into nine 3×3 blocks. Some squares start with a number; the rest are empty. The goal is to fill every empty square with a number from 1 to 9 so that each number appears exactly once in every row, every column, and every 3×3 block. If you have never played, try the free easy puzzle at New York Times Sudoku.

Each square is a Cell. A Cell with value 0 is empty. A Cell that holds one of the puzzle's starting numbers is locked: the solver must never change it.

Task 2 — The Cell class

BUILD — one square of the puzzle.

Cell is similar to the Cell class from Project 2, with two differences. It holds a number from 0 to 9 instead of alive or dead, and it stores its own row and column as fields.

Why store the row and column? In Project 2, only the grid knew where a Cell was. In Project 4, the solver will push Cells onto your stack. When it pops one off, it gets the Cell by itself, not its location in the array, but it still needs to know which row, column, and 3×3 block that Cell belongs to. So each Cell carries its location with it.

In Cell.java:

The first constructor does the same work as the second with locked set to false. Can you write it in one line by calling the other constructor with this(...)?

Test it. Run java Cell and check that every expected matches every got. Then complete the TODO at the end of main(): write at least two tests of your own, for example of setLocked.

Task 3 — The constructors, get(), and set()

BUILD — a 2D array of objects.

A Board holds a 9×9 array of Cells. Board.SIZE is already defined as 9; use it instead of typing 9.

Two steps, not one: new Cell[SIZE][SIZE] creates the grid of references, but every location starts as null. You still have to put a new Cell(...) in each location. If you see a NullPointerException, this is the first place to look.

The second constructor: Board(String filename)

Before a board can be filled from a file, it needs the same empty grid of Cells that Board() builds. You could copy the code from Board() into this constructor line for line, but that is a style programmers work hard to avoid. If the same code lives in two places, every fix has to be made twice, and sooner or later one copy gets forgotten. The rule has a name: DRY, for “Don't Repeat Yourself.”

Don't repeat yourself: call the first constructor with this(), then call read(filename) to fill in the board from the file. Java lets one constructor call another this way, as long as the call is the very first line.

Like Stack reusing your LinkedList, this is code reuse: write the code once, and use it everywhere it is needed. You will write read in Task 4. For now it does nothing, so Board("board1.txt") gives you an empty board, and that is exactly what it should do at this point.

Test it. The tests in Board.java are split into three methods, testTask3(), testTask4(), and testTask5(). For now, main() calls only testTask3(). Run java Board, check the results, and complete the TODO in testTask3() with a test of the 4-parameter set.

Task 4 — read(String filename)

READ A FILE — turn lines of text into Cells.

A board file has nine lines, one for each row. Each line holds nine numbers separated by spaces, and 0 means an empty Cell. Here is board1.txt:

0 0 0 3 0 1 0 0 0
0 0 0 0 0 0 0 0 0
9 0 0 0 0 0 0 0 0
0 0 0 0 0 0 9 0 0
0 0 6 0 0 0 0 0 7
2 0 0 0 0 0 0 0 0
0 0 0 0 5 0 0 0 0
0 0 0 0 7 0 8 0 0
0 0 0 0 0 0 0 0 0

The read method in Board.java already opens the file, reads it one line at a time, skips blank lines, and splits each line into an array of Strings called tokens. For the first line above:

line:   "0 0 0 3 0 1 0 0 0"
tokens: [0, 0, 0, 3, 0, 1, 0, 0, 0]  length = 9

Work in two steps:

  1. See what read gives you. Uncomment the two print statements in read. In main(), remove the // in front of testTask4();, then run java Board. Your constructor from Task 3 calls read, so the prints appear. Line up each printed line with the statement that produced it.
  2. Complete the two TODOs in read.
    • Before the loop, create a variable that keeps track of which row the current line belongs to.
    • Inside the loop, turn each token into an int with Integer.parseInt(tokens[c]) and set the Cell in the current row and column c. A non-zero value is one of the puzzle's starting numbers, so that Cell is locked. A 0 stays unlocked.
    Ask yourself: where does the row variable change, and how often? When your board looks right, comment the print statements out again.

Choose test data that makes mistakes visible

Suppose your read accidentally stops one line early, so the last row of the file is never read. The last row of board1.txt is all zeros, and an unread row is also all zeros, so your board would look perfect and you would never notice. Most of board1.txt is zeros, which hide mistakes like this one.

solved.txt is a completed puzzle: every row contains each number from 1 to 9. A missing row, a row that lands in the wrong place, or a number shifted one column over is easy to spot.

Each file is good for something different. Use solved.txt to check that every value lands in the right place. Use board1.txt to check locking: in a solved board every Cell is locked, so it cannot show you whether the zeros stay unlocked.

Test it. The provided tests check a locked number in board1.txt and a number in the last row of solved.txt. In the TODO, write a test for a number in the last column of solved.txt.

Task 5 — toString()

DISPLAY — print the board so you can check it.

Return a multi-line String that shows the board with lines between the 3×3 blocks. You will be reading a lot of boards in Project 4, so the layout is fixed. For solved.txt, toString() must return exactly this:

1 9 8 | 7 6 5 | 4 3 2
7 6 5 | 4 3 2 | 1 8 9
4 3 2 | 1 9 8 | 6 5 7
------+-------+------
9 8 1 | 5 4 6 | 2 7 3
2 7 6 | 9 1 3 | 8 4 5
5 4 3 | 8 2 7 | 9 1 6
------+-------+------
6 1 7 | 3 8 9 | 5 2 4
3 2 4 | 6 5 1 | 7 9 8
8 5 9 | 2 7 4 | 3 6 1

The tester compares your String with this one character by character, so follow these rules exactly:

Every line, the separator lines included, is 21 characters long, so the bars and plus signs line up. Ask yourself: for which column numbers do you add a bar, and for which row numbers a separator line? And: how do you avoid a space after the last value in a row?

If a check fails, the tester tells you the first line that does not match. A trailing space is invisible on the screen, so the tester shows each line in quotes.

Test it. In main(), remove the // in front of testTask5(); and run java Board. It prints solved.txt so you can compare it with the board above. In the TODO, print a Board made from board1.txt and compare it with the file.

Lab checkpoint

When the tester prints LAB CHECKPOINT REACHED!, call a TA or instructor over and show them the tester output and your printed solved.txt. Then start Project 4.

Lab 4 complete

You have a stack built on your own linked list, and a Board that can load and display any puzzle. In Project 4 you will teach the Board to check whether a number is allowed in a Cell, and then use your stack to search for a solution.

Submission

Before the end of the lab period, make sure your work is in your personal Google Drive folder Projects/Project4.

Your Project 4 folder should begin like this

Projects/
└── Project4/
    ├── LinkedList.java      (yours, now implementing Stack)
    ├── Stack.java
    ├── Cell.java
    ├── Board.java
    ├── Lab4Tester.java
    ├── board1.txt
    └── solved.txt

Project 4 builds on every one of these files. Add the Project 4 files to this same Project4 folder.

Remember: The provided tester performs basic checks of the required behavior. Passing its checks does not replace understanding your code or being able to explain why your stack operations take the same time no matter how many items are on the stack.

Ready for Project 4?

Return to the CS231 course page, navigate to the Projects page, and open Project 4: Solving Sudoku, or go directly to the project.