Overview · Why a Stack? · Files and Setup · Tasks · Exploration · Testing · Report Format · Checklist

Overview

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.

From Lab 4 to Project 4: In Lab 4 you made your 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

How the Solver Works: Why a Stack?

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

Why not a queue?

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.

Files and Setup

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:

Sudoku.java LandscapeDisplay.java Project4Tester.java board2.txt easy.txt

Add the Project 4 method stubs to your own files

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
Work in order, and test in 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.

Tasks

Task 1 — 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:

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.

Finding the block: The blocks start at rows 0, 3, and 6 and columns 0, 3, and 6. Integer division drops the remainder, so (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.

Task 2 — 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.

Task 3 — Random boards: 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:

  1. Choose a random row, a random column, and a random value from 1 to 9.
  2. If that Cell is not already locked and the value is valid there, set the Cell to the value and lock it.

Use a Random object: rand.nextInt(9) returns a number from 0 to 8. Which of your three random numbers needs adjusting, and how?

Every starting value is valid where it is placed, but that does not mean the puzzle can be solved. Two values that are each legal can still make some other Cell impossible to fill. How often that happens is the subject of your experiments.

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.

Task 4 — The 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:

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.

Think about it: The solver tries values for a Cell in order, 1, 2, 3, and so on. When it comes back to a Cell, the Cell's current value is the last one it tried, so that value and every value below it have already been tried. Where should your search start? And what does a Cell holding 0 tell you about what it has tried?

Test it. Uncomment testTask4();. In the TODO, test a Cell that already holds 9.

Task 5 — 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:

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.

Task 6 — 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.

Stage A: Move forward

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.

Why 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.

Stage A checkpoint

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.

Stage B: Back up when you are stuck

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.

The most common bug: forgetting to clear a Cell

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:

  • The Cell is no longer on the stack, but it still holds a value. The solver has forgotten it, so it never backs up through this Cell again.
  • Its old value blocks other Cells. 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.

Task 7 — Watch the Solver: the Display

LandscapeDisplay opens a window and calls your Board's draw method to show the board. Add these three pieces:

  1. 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.

  2. 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);
            }
        }
    }
  3. In both 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.

Exploration

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.

Required Element 1: A Smarter Choice of Cell

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:

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:

Required Element 2: How Many Starting Values Make a Solvable Puzzle?

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:

  1. Create and solve at least 10 random boards with new Sudoku(numLocked, 0).
  2. For each board, record which of the three outcomes happened: solved, no solution, or gave up (more than MAX_STEPS steps).
  3. For the boards that were solved, record the number of 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 valuesSolvedNo solutionGave upAverage steps (solved boards)
0
5
…
40

Then answer these questions in your Results section:

  1. How does the number of starting values affect the chance that a random board can be solved? Around how many starting values does the change happen?
  2. Which numbers of starting values produce the most “gave up” results? Why might boards in that range be the hardest for the solver?
  3. How do your two methods compare in solved boards, gave-up boards, and steps?
Think experimentally: Use a delay of 0 for experiments; the display makes every step wait. Because the boards are random, your numbers will vary from run to run. If two runs disagree, run more boards.

Testing

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.

Basic Tester Self Check: Passing the provided tester is an important milestone, but it performs only basic checks. Passing all tests does not guarantee that every possible case in the project is correct.

Report Format

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.

Report Format: Google Doc Write your report as a Google Doc named Project4 Report and keep it in your Projects/Project4 folder, next to your code. Create it there directly (New → Google Docs inside the folder) so that it is a Google Doc rather than an uploaded Word or PDF file.

Your Project 4 folder should look like this

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.

Abstract

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.

Results

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.

Evidence → Observation → Interpretation
  1. Evidence: Present the relevant image, table, or numerical result.
  2. Observation: Describe what the evidence actually shows.
  3. Interpretation: Explain what you think the result means and why it may have occurred.

Data Structure Analysis

Answer the following questions, using big-O notation where appropriate.

  1. During solve(), what does the stack hold? In terms of the puzzle, what does pushing a Cell mean, and what does popping a Cell mean?
  2. Explain in your own words why the solver needs a stack and not a queue. Use a small example of your own.
  3. Give the running time of push and pop in your LinkedList. Why does it matter for a solver that can take up to 100,000 steps?
  4. 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.

Extensions

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:

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.

References/Acknowledgements

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.

Before You Submit

Remember: The provided tester performs only basic checks. Passing all of its tests does not guarantee full credit on the project. Your implementation must satisfy the complete project specification.