Many many thanks to Dr. Garrison for this project description and starting code. THANK YOU BASED BILLIAM

In this assignment, you will be implementing a backtracking algorithm to solve Sudoku puzzles. If you aren’t familiar (or even if you are and need a refresher), have a look at this site.


Starting point

Download and extract these materials. Contained are:

Sudoku.java contains the following:


Testing

We will be testing your code on the command line. You are welcome to use an IDE, but before submitting, please test that your Java files can be compiled and run on the command line without it.

We should be able to run your program like so:

java Sudoku -t

to run all the test methods, or:

java Sudoku 2-easy.su

to load and solve a Sudoku board file.

The main we gave you handles this command-line interface. But right now, nothing happens :)


Your task

This is a tough project. As such, 60% of the grade is for correctness, and 40% is for the thoroughness of your testing methods.

You will implement four methods to solve the problem: isFullSolution, reject, extend, and next.

To complement those four, there are four testing methods: testIsFullSolution, testReject, testExtend, and testNext. Each of these should make several tests of the corresponding solving methods.

The puzzle-solving algorithm

By implementing the four solving methods, you will be constructing a backtracking solver program. Important points:

The puzzle-solving methods

These methods make up the four parts of the backtracking template. These methods are not recursive! Only the solve method is, and we already wrote that for you ;)

Do not write all the methods at once. Start with isFullSolution and reject. Test them extensively with your testing methods (by running your program with java Sudoku -t).

The testing methods

Re-read starting at Chapter 2.16 to review the concepts behind writing test methods. Write your testing methods at the same time you write the solving methods. Have a look at this 8-Queens example to see some example testing methods.

For each of the testing methods, try to follow these guidelines:

You can make new board files following the guidelines below, and then use readBoard to load them for testing.

For example, if I were testing the reject method, I would give it…


Example boards

We’ve included 5 example boards (the .su files). If you open them in your text editor, you will see they look something like this:

3__79425_
2__56_197
79_82_4_3
_2__78_41
57_1_6_82
1483_2976
9_7_856_4
4526_7839
_164397_5

There are 9 rows, and each has 9 columns. Any non-number character is treated as an empty (unsolved) cell.

You can open one of the existing files and “File > Save As…” to make your own boards. Make a bunch! It’s fine!


Submission

You will submit a ZIP file named username_proj3.zip where username is your Pitt username.

Do not put a folder in the zip file, just the following file(s):

Do not submit any IDE project files.

Submit to the Box folder at this link. Drag your zip file into your browser to upload. If you can see your file, you uploaded it correctly!

You can also re-upload if you made a mistake and need to fix it.