CS 163/164, Spring 2018

Programming Assignment - Honors Option

Sudoku Solver

Due Friday, May. 4th at 11:55pm

This is an Honors Assignment

To get honors option credit for this assignment, you would have already completed the paperwork. All other students are welcome to complete this assignment as optional and will be rewarded a cookie coupon!

Objectives of this Assignment

This assignment has the goal of teaching you how to:

How to write a reasonably complicated Java program,
that solves Sudoku puzzles in a graphical environment,
and makes you implement constraints in a binary format,
and shows the utility of a Java ArrayList based on an inner class.

Description

The purpose of the assignment is to implement an interface that has three methods relating to solving a Sudoku puzzle, and three getters that allow testing of your program. The interface is defined in GameInterface.java, which is part of the Java archive provided with this assignment, as shown below:

import java.util.ArrayList;

public interface GameInterface {

    // Load puzzle from file
    public void load(String filename);

    // Save puzzle to file
    public void save(String filename);

    // Return values
    public enum eStatus {
        eSuccess, // Made successful move
        eFailure, // Cannot solve puzzle!
        eSolved   // Solved entire puzzle
    }
    
    // Fill in one square, if possible
    public eStatus step();
    
    // Getter for puzzle data
    public int[][] getData();
    
    // Getter for puzzle constraints
    public int[][] getConstraints();
    
    // Inner class for puzzle move
    public class Move {
        int row;
        int column;
        int value;
    }

    // Getter for puzzle solution
    public ArrayList getSolution();
}

NOTE: This assignment is complex, make sure and read the instructions carefully!

Instructions

Create a project called Sudoku, and import the Java archive file named Sudoku.jar into the project. If imported correctly, you should see the following project hierarchy:

Sudoku/src/GameEngine.java: Starting point for the assignment.
Sudoku/src/GameInterface.java: Interface implemented by GameEngine.java.
Sudoku/src/UserInterface.java: Graphical user interface for the game.
Sudoku/images/0.png, 1.png, ..., 9.png: Image icons for user interface.
Sudoku/Normal.txt: Puzzle that is solvable using specified algorithm.
Sudoku/Hard.txt: Puzzle that is NOT solvable using specified algorithm.

NOTE: Do not change any of the files shown above except GameEngine.java.

Part One

Implement the load(), save(), and updateConstraints() methods in GameEngine.java, as follows:

The load() method allocates the 2-dimensional arrays for the puzzle and constraints, and an ArrayList of Move objects, and reads a puzzle file into the puzzle array. The method should also call updateConstraints().
The save() method writes the puzzle array to a puzzle file.

NOTE

The updateConstraints() method updates the constraints for each square that is not occupied in the puzzle.
Test the code above by running the UserInterface, which contains the main() method, and verify that you can produce the correct constraints.
No run configuration setup is required for the project, because the user interface launches a file browser to select files to read and write.

A short note on constraints. There is an integer constraint for each square that has not been filled in yet, meaning the value is still zero. Each constraint consists of the bottom 9 bits of the integer. Bit 0 corresponds to the value 1, Bit 1 corresponds to the value 2, and so on until Bit 8, which corresponds to the value 9. If the bit is 1, then the square cannot contain the corresponding value, otherwise it can. Thus if the bit value of a constraint is 0b110101111, then the value can only be 5 or 7. When the value has exactly one zero, you can fill in the square with the corresponding value. For example, if the constraint is 0b1111111101 then the corresponding square must have the value 2. The constraints are updated after loading the puzzle and after each step.

NOTE: You must implement the constraints exactly as described to pass testing!

Part Two

Implement the step() method to solve the puzzle one step at a time and return the correct status: eFailure for no move possible, eSuccess for a successful move that does not complete the puzzle, and eSolved for a successful move that also completes the puzzle.

The step method figures out the next move, as follows. Check the board row by row, from top to bottom, and within each row, from left to right. Update the first square that you find with a constraint with only one zero. Return eFailure if there are no squares with this status. Return eSuccess if you successfully update one square, but the puzzle is not completely solved. Return eSolved if you successfully update one square, and this also completes the puzzle. Update the constraints after each successful move. You should never update more than one square when the step method is called.

NOTE: In addition to updating one square, you must construct a Move object and add it to the history ArrayList defined in GameEngine.java.

Testing

The image below shows the correct constraints before any moves are made, which is all that is required for the initial submission.

Puzzle constraints before any moves

The output below shows the first 10 steps for the Normal.txt puzzle. The output is generated by the UserInterface based on the ArrayList of Move objects returned from the GameEngine.

Filled in 7 at row 0, column 2
Filled in 2 at row 0, column 3
Filled in 3 at row 0, column 5
Filled in 5 at row 0, column 0
Filled in 6 at row 0, column 1
Filled in 8 at row 0, column 7
Filled in 7 at row 1, column 4
Filled in 2 at row 1, column 7
Filled in 9 at row 2, column 5
Filled in 5 at row 2, column 6

The image below shows the correct constraints at the same point in the game, after 10 steps:

Puzzle constraints after 10 moves

Specifications

Work on your own, as always.
The submitted source code file must be named
```
 GameEngine.java 
```
Name the file exactly - upper and lower case matters!
Comments at the top as shown above.
Assignments should be implemented using Java, version 1.8.
Make sure your code runs on machines in the CSB 120 lab.
Read the syllabus for the late policy.
We will be checking programs for plagiarism, so please don't copy from anyone else.

Grading Criteria

50 points for Part One, 150 points for Part Two. Preliminary testing is identical to Part One, though testing section above shows an example of correct constraints and moves, and is a superior method of testing to automated grading for this assignment!

Final Testing (Part One)

test1: checks that the load() method can read Normal.txt from the file. (15 points)
test2: checks that the save() method can write Normal.txt to another file. (15 points)
test3: checks that getConstraints() is correct after 0 steps for Normal.txt. (10 points)
test4: checks that getSolution() is correct after solving Normal.txt. (10 points)

Final Testing (Part Two)

test5: checks that the load() method can read Another.txt from the file. (20 points)
test6: checks that the save() method can write Another.txt to another file. (20 points)
test7: checks that getConstraints() is correct after 0 steps for Another.txt. (20 points)
test8: checks that getConstraints() is correct after 10 steps for Another.txt. (20 points)
test9: checks that the return status from step() is correct for Another.txt. (20 points)
test10: checks that getSolution() is correct after solving Another.txt. (50 points)

The puzzle named Another.txt that we are using for final testing is available here.

Submit GameEngine.java to Checkin.