Overview · Why a Stack? · Files and Setup · Tasks · Exploration · Testing · Report Format · Checklist
In Project 4 you will write a program that solves Sudoku puzzles. Your solver works the way a careful person does: it fills in one empty square at a time with a number that fits, and when it reaches a square where nothing fits, it goes back and changes its most recent choice. Once your solver works, you will improve how it chooses which square to fill next and run experiments on randomly generated puzzles.
LinkedList a Stack, and you built a
Cell and a Board that can read and print a puzzle. In this project you
teach the Board the rules of Sudoku, and you write a Sudoku class that uses
your stack to search for a solution.
Cell, Board (yours, from Lab 4) ↓ Board: numLocked, validValue, validSolution, random boards (Tasks 1–3) ↓ Sudoku: findNextValue, findNextCell (Tasks 4–5) ↓ solve(): move forward, then back up with your Stack (Task 6) ↓ LandscapeDisplay: watch the solver work (Task 7) ↓ Exploration: a smarter solver, and experiments on random boards
The solver keeps a stack of the Cells it has filled in, in the order it filled them. The Cell on top of the stack is always its most recent choice. On every step the solver tries to fill in one more empty Cell:
Every Cell on the stack holds a value that fits, so the stack's size tells you how many of the puzzle's empty Cells are filled in so far. Suppose the puzzle started with 50 empty Cells. When the stack holds 50 Cells, every one of them has a value that fits, and the puzzle is solved.
If the solver backs up all the way, so that the stack is empty and the first Cell it filled has no values left to try, then every possibility has been tried, and the puzzle has no solution.
Here is a tiny example with three empty Cells, A, B, and C:
step what happens stack (top on the right) 1 A gets 1 [A] 2 B gets 3 [A, B] 3 C: nothing fits. Pop B, give B its next value 5 [A, B] 4 C gets 2 [A, B, C] all three filled: solved
A queue removes the oldest item first. If the solver used a queue, then when it got stuck it would undo its first choice, A, while keeping B and C. But B and C were chosen to fit around A. Once A changes, those later choices may no longer fit, and the solver has no record of why they were made.
Each choice depends on the choices made before it. So the only choice that is safe to change is the most recent one: nothing has been built on top of it yet. Undoing the last thing first is exactly what a stack does.
Work in the same Project4 folder you used for Lab 4. It should already contain your
LinkedList.java, Stack.java, Cell.java,
Board.java, board1.txt, and solved.txt. Download these files
into the same folder:
Board.java and Cell.java are your files from Lab 4, so the new methods
are not in them yet. Copy these stubs into them now. Afterward, every file compiles, and each
method you need to write is marked TODO with its task number.
At the top of Board.java, next to the other imports, add:
import java.util.Random; import java.awt.Color; import java.awt.Graphics;
Then, inside the Board class, just above the testing methods at the bottom, add:
// ===================== Project 4 =====================
private boolean finished; // true once the solver has finished (Task 7)
/**
* Creates a board with numFixed randomly placed, locked, valid values.
*/
public Board(int numFixed) {
this(); // start from an empty board (DRY again!)
// TODO (Task 3)
}
/** Returns the number of locked Cells on the board. */
public int numLocked() {
// TODO (Task 1)
return 0;
}
/**
* Returns true if value could go in the Cell at (row, col) without repeating
* a value in the same row, column, or 3x3 block. The Cell at (row, col)
* itself does not count.
*/
public boolean validValue(int row, int col, int value) {
// TODO (Task 1)
return false;
}
/** Returns true if every Cell holds a value from 1 to 9 that is valid where it is. */
public boolean validSolution() {
// TODO (Task 2)
return false;
}
/** Records whether the solver has finished. */
public void setFinished(boolean finished) {
this.finished = finished;
}
/** Draws the board. LandscapeDisplay calls this method. */
public void draw(Graphics g, int scale) {
// TODO (Task 7)
}
At the top of Cell.java, add:
import java.awt.Color; import java.awt.Graphics;
And inside the Cell class, just above main(), add:
/** Draws this Cell's value at (x, y). Empty Cells draw nothing. */
public void draw(Graphics g, int x, int y, int scale) {
// TODO (Task 7)
}
Compile everything to make sure the stubs went in correctly:
javac *.java
main() first.
As in Lab 4, Sudoku.java has a main() with a few tests for each task
and a TODO asking you to write tests of your own. All of your Project 4 tests go there.
For each task: write the method, run java Sudoku, write your own test, and only then
run Project4Tester.
numLocked() and validValue()numLocked() returns how many Cells on the board are locked.
validValue(int row, int col, int value) answers the central question of Sudoku:
could this value go in this Cell? It returns true only if:
value is between 1 and 9, andvalue, andvalue, andvalue.
Notice the word other: the Cell at (row, col) itself does not
count. Later, the solver asks whether a Cell's own value is valid where it is, and a Cell should
not conflict with itself.
(row / 3) * 3 gives the first row of
row's block. For example, row 4: 4 / 3 is 1, and 1 * 3
is 3. Rows 3, 4, and 5 are in the block that starts at row 3.
Test it. Run java Sudoku. testTask1() checks
board1.txt. In the TODO, write a test where the only conflict is in the
same 3×3 block, not the same row or column.
validSolution()
validSolution() returns true if the board is solved: every Cell holds a
value from 1 to 9, and every value is valid where it is. You have already written the method that
does most of the work. How can validValue answer both questions at once? (What does it
return for a Cell that holds 0?)
Test it. In main(), remove the // in front of
testTask2();. It checks solved.txt (solved) and
board1.txt (not solved). In the TODO, change one value in a solved board
and test it again.
Board(int numFixed)
For your experiments you will need puzzles with any number of starting values. This constructor
builds an empty board (its first line, this();, is already there) and then locks
numFixed random Cells. Repeat until numFixed Cells have been locked:
Use a Random object: rand.nextInt(9) returns a number from 0 to 8. Which
of your three random numbers needs adjusting, and how?
Test it. Uncomment testTask3();. It prints a random board with 20 starting
values. In the TODO, check that every locked Cell holds a valid value.
Sudoku constructors and findNextValue()
Open Sudoku.java. The fields, getBoard(), getSteps(),
and a helper method pause() are already written. First complete the two constructors.
For now, each one only needs to create the board and store delay:
Sudoku(String filename, int delay) reads the board from the file.Sudoku(int numLocked, int delay) creates a random board with numLocked starting values.
You will come back to the constructors in Task 7 to add the display. With delay set
to 0, there is no display.
Next, write findNextValue(Cell cell). It returns the next valid value for the Cell
that the Cell has not tried yet, or 0 if there is none. It only returns the value; it does
not change the Cell.
Test it. Uncomment testTask4();. In the TODO, test a Cell that
already holds 9.
findNextCell()
findNextCell() chooses the next Cell to fill. Go row by row, and within each row
column by column, to the first Cell whose value is 0. Then:
findNextValue finds a valid value for it, set the Cell to that value and return the Cell.null. That tells the solver it is stuck.
Only look at the first empty Cell. If it has no valid value, return null right
away; do not move on to a different Cell. Locked Cells never hold 0, so you do not need to check
whether a Cell is locked.
Test it. Uncomment testTask5();. In the TODO, call
findNextCell a second time and predict which Cell and value it returns.
solve()
You will write solve() in two stages. In Stage A the solver only moves
forward: it fills in one Cell after another and gives up the first time it gets stuck. In
Stage B you add backtracking. Getting Stage A working first means that when you write the
hardest part, you already know the rest of your solver works.
Write solve() following this algorithm:
create an empty stack of Cells: Stack<Cell> stack = new LinkedList<Cell>();
numEmpty = the number of Cells on the board minus the number of locked Cells
steps = 0
while the stack holds fewer than numEmpty Cells:
add 1 to steps
if steps is more than MAX_STEPS:
mark the board finished and return false (give up)
call pause()
next = findNextCell()
if next is null:
mark the board finished and return false (stuck)
push next onto the stack
mark the board finished and return true (solved)
“Mark the board finished” means board.setFinished(true); the display
uses it in Task 7.
MAX_STEPS? Some boards take millions of steps before the solver can tell
whether they have a solution. MAX_STEPS (100,000) lets the solver give up instead.
After solve() returns false, you can tell the two cases apart:
if getSteps() is more than MAX_STEPS, the solver gave up; otherwise the
board has no solution.
Test Stage A. Download easy.txt if you have not already. It is a puzzle
the solver can finish without ever getting stuck. Uncomment testTask6A(); in
main(). It solves easy.txt, which has 63 empty Cells, and then tries
board1.txt.
easy.txt should be solved in exactly 63 steps, one for each empty Cell, and
validSolution() should be true. board1.txt should
not be solved yet: your solver gets stuck after 15 steps, because it cannot back up.
If you see both of these, your findNextValue, findNextCell, and the
forward part of solve() are working. In the tester, the check named
Stage A should pass; most of the others need Stage B. Now you are ready for Stage B.
In Stage A, when findNextCell returns null, the solver gives up. Now,
instead, it should back up: pop its most recent choice and try that Cell's next value. Add the
backtrack loop between finding next and checking whether it is
null:
next = findNextCell()
while next is null and the stack is not empty: (backtrack: this loop is new)
pop a Cell off the stack
value = findNextValue(that Cell)
if value is 0:
set the Cell's value to 0 (no values left: clear it!)
else:
set the Cell's value to value
set next to this Cell
if next is still null:
mark the board finished and return false (no solution)
push next onto the stack
Compare this with the example at the top of the page. Now, when the solver
reaches if next is still null, it has backed up through every choice on the stack
and run out of options, so the puzzle has no solution.
When you pop a Cell and it has no values left to try, you must set its value back to 0 before you pop the next Cell. Forgetting this step is the most common mistake in this project. If the Cell keeps its old value, three things go wrong:
validValue sees that value in the Cell's
row, column, and block and rejects it everywhere else, even though nothing chose it anymore.
findNextCell skips it. findNextCell only looks for Cells
holding 0. When the solver moves forward again, it will not come back to this Cell, and it will
not try its values starting from 1.
The rule: a Cell that is not on the stack and is not locked must hold 0. Pushing a Cell gives it a value; when you back up past a Cell for good, clear it.
Test Stage B. Uncomment testTask6B();. It prints board1.txt,
solves it, prints the result, and checks it with validSolution(). Check by eye that
the starting values have not moved. Run testTask6A() again too: easy.txt
should still take 63 steps, and board1.txt should now be solved. In the
TODO, solve board2.txt the same way.
LandscapeDisplay opens a window and calls your Board's draw method to
show the board. Add these three pieces:
In Cell.java, complete draw. Locked values are blue and the solver's values are red:
public void draw(Graphics g, int x, int y, int scale) {
if (value == 0) return; // empty Cells draw nothing
char toDraw = (char) ('0' + value);
g.setColor(isLocked() ? Color.BLUE : Color.RED);
g.drawChars(new char[] {toDraw}, 0, 1, x, y);
}
Use the name of your own value field if it is not value.
In Board.java, complete draw. It draws every Cell, lines between the blocks, and a message when the solver finishes:
public void draw(Graphics g, int scale) {
for (int r = 0; r < SIZE; r++) {
for (int c = 0; c < SIZE; c++) {
get(r, c).draw(g, c * scale + 5, r * scale + 20, scale);
}
}
g.setColor(Color.BLACK);
for (int i = 0; i <= SIZE; i += 3) {
g.drawLine(i * scale, 0, i * scale, SIZE * scale);
g.drawLine(0, i * scale, SIZE * scale, i * scale);
}
if (finished) {
if (validSolution()) {
g.setColor(new Color(0, 127, 0));
g.drawString("Hurray!", scale * 3 + 5, scale * 10 + 10);
} else {
g.setColor(new Color(127, 0, 0));
g.drawString("No solution!", scale * 3 + 5, scale * 10 + 10);
}
}
}
Sudoku constructors, after creating the board: if delay is
greater than 0, assign ld a new LandscapeDisplay(board).
Your solve() already calls pause() on every step, which waits
delay milliseconds and redraws the window. Try it in main():
Sudoku game = new Sudoku("board1.txt", 10);
game.solve();
Watch the red values fill in, back up, and fill in again. That is your stack at work. Take a screenshot of a solved board for your report.
The exploration has two required elements. Element 1 makes your solver smarter. Element 2 uses both versions of your solver to study random boards. Both go in the Results section of your report.
findNextCell fills the board in order, row by row. A person solving a Sudoku does not
work that way. They look for a square where only one or two numbers fit, and they fill that in
first. Choosing well means fewer wrong guesses, and fewer wrong guesses means less backtracking.
Build it. Write findBestCell() in Sudoku.java:
null. Otherwise set it to its first valid value (use findNextValue) and return it.
Let solve() use either method. To compare the two methods, you need both of them,
so do not change findNextCell. Instead, Sudoku.java already has a
boolean field, useBestCell. It is false unless you call
setUseBestCell(true). In solve(), replace the line
next = findNextCell(); with:
Cell next;
if (useBestCell) {
next = findBestCell();
} else {
next = findNextCell();
}
Now every solver uses findNextCell, unless you call setUseBestCell(true)
first. To compare the methods, solve the same board twice:
Sudoku rowByRow = new Sudoku("board2.txt", 0);
rowByRow.solve();
System.out.println("findNextCell steps: " + rowByRow.getSteps());
Sudoku best = new Sudoku("board2.txt", 0);
best.setUseBestCell(true);
best.solve();
System.out.println("findBestCell steps: " + best.getSteps());
Run it. Solve board1.txt and board2.txt with each method and record getSteps() each time.
Report it. In your report, include:
Your random boards place valid starting values, but some of them still cannot be solved. In this experiment you measure how the number of starting values affects whether a random board can be solved, and how long the solver takes.
Run it. For each number of starting values 0, 5, 10, 15, 20, 25, 30, 35, and 40:
new Sudoku(numLocked, 0).MAX_STEPS steps).Do this twice: once with findNextCell and once with findBestCell.
A loop like this one, in main() or in a new class, runs the experiment for one method:
for each numLocked in 0, 5, 10, ..., 40:
solved = 0, noSolution = 0, gaveUp = 0, totalSteps = 0
repeat 10 times:
Sudoku game = new Sudoku(numLocked, 0);
game.setUseBestCell(...); // false or true
if game.solve() returns true:
solved++, totalSteps += game.getSteps()
else if game.getSteps() > Sudoku.MAX_STEPS:
gaveUp++
else:
noSolution++
print numLocked, solved, noSolution, gaveUp, and the average steps of the solved boards
Report it. Present your results as a table like this one, one for each method:
| Starting values | Solved | No solution | Gave up | Average steps (solved boards) |
|---|---|---|---|---|
| 0 | ||||
| 5 | ||||
| … | ||||
| 40 |
Then answer these questions in your Results section:
The provided tester is designed to help you make incremental progress. Before using it, test each
method yourself with the tests in Sudoku.java and tests you write.
javac *.java java Project4Tester // runs Task 1, 2, 3, ... and stops at the first task that needs work java Project4Tester 6 // runs only Task 6 java Project4Tester 8 // checks findBestCell (Exploration, Element 1)
As in Lab 4, the tester prints [PASS] or [FAIL] with expected and actual
values and a hint, and reports [CRASH] or [TIMEOUT] instead of crashing
itself. It does not check the display (Task 7); watch it instead.
Your intended audience is your peers who are not in this class but who have taken a computer science course. Your reader should be able to understand what you built, the important computer science ideas behind it, what experiments you performed, and what your results mean without having completed this assignment themselves.
Projects/
└── Project4/
├── Project4 Report (Google Doc)
├── LinkedList.java
├── Stack.java
├── Cell.java
├── Board.java
├── Sudoku.java
├── LandscapeDisplay.java
├── Lab4Tester.java
├── Project4Tester.java
├── board1.txt
├── board2.txt
├── easy.txt
├── solved.txt
└── Extension1/ (only if you did an extension)
Your project report should contain the following sections. Please include a header for each section.
Briefly summarize the project in your own words. Identify both the core computer science ideas and the application: a stack built from your linked list through an interface, and a search that uses the stack to back up and try again, applied to solving Sudoku puzzles. Briefly identify the experiments you performed. Detailed results belong in the Results section.
Include your screenshot of a solved board. Then present both Required Elements of the Exploration: the step table and explanation for Element 1, and the outcome tables and answers for Element 2.
Answer the following questions, using big-O notation where appropriate.
solve(), what does the stack hold? In terms of the puzzle, what does pushing
a Cell mean, and what does popping a Cell mean?
push and pop in your LinkedList.
Why does it matter for a solver that can take up to 100,000 steps?
findBestCell does much more work on each step than findNextCell, because
it checks every empty Cell. Use your step counts to explain why it can still be much faster overall.
Describe any work you completed beyond the required project. Focus on the design and behavior of the extension: what capability you added, what classes or methods changed, how the new logic works, and how you determined that it worked. If you did not complete an extension, simply state that no extension was completed. Some possibilities:
boolean setting with one that can name each method, such as an int or a String.You will find many Sudoku solvers on the web. If you use one as a reference, cite it. You will get far more credit for an algorithm of your own design that you analyze than for code copied from elsewhere.
List the people and outside resources that contributed to your work. Include people you worked with or received help from, including TAs and instructors, and acknowledge outside references that helped you understand an algorithm, library, or programming technique.
.java files compile together.Project4Tester and fixed every [FAIL], including Task 8 (findBestCell).Extension1, Extension2, and so on. Each extension folder must contain ALL files necessary to compile and run that extension; do not rely on files located elsewhere in your Project4 folder.