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.
Every file compiles as soon as you download it. Each method you need to write is marked
TODO with its task number.
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:
- Choose a method and a small example: what will you create, and what will you call?
- Decide the expected answer before you run anything. Work it out on paper.
- Copy one of the provided
printlnlines and change it to call your example. - 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].
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
LinkedListand 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
Iterablecontract.
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:
push(T item)adds the item to the top of the stack.pop()removes and returns the top item. If the stack is empty, returnnull.peek()returns the top item without removing it. If the stack is empty, returnnull.
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 itsnextset tonull, and how do you find that Node? - Now suppose your list also had a
tailfield 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:
- Declare four private fields: the row index, the column index, the value, and whether the Cell is locked.
Cell(int row, int col, int value)sets the row, column, and value, and makes the Cell unlocked.Cell(int row, int col, int value, boolean locked)sets all four fields.getRow(),getCol(),getValue(), andisLocked()return the fields.setValue(int newValue)andsetLocked(boolean lock)change them.toString()returns the value as a String, for example"5".
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.
- Declare a private field that is a 2D array of Cells.
-
Board()creates the array and fills every location with a new, unlocked Cell with value 0. Give each Cell its own row and column. Board(String filename)builds a board from a file (see below).get(int row, int col)returns the Cell at that location.set(int row, int col, int value)sets the value of the Cell at that location.set(int row, int col, int value, boolean locked)sets both its value and its locked status.
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.”
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:
-
See what
readgives you. Uncomment the two print statements inread. Inmain(), remove the//in front oftestTask4();, then runjava Board. Your constructor from Task 3 callsread, so the prints appear. Line up each printed line with the statement that produced it. -
Complete the two
TODOs inread.- 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 columnc. A non-zero value is one of the puzzle's starting numbers, so that Cell is locked. A 0 stays unlocked.
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:
- Values in a row are separated by one space.
- Between blocks, a row has
" | ": a space, a bar, and a space. - After the third and sixth rows, add the line
------+-------+------(6 dashes, a plus, 7 dashes, a plus, 6 dashes). - There is no space at the end of a line.
- Every line ends with
"\n", including the last one.
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.
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.