Solving Sudoku with Backtracking.
Backtracking is a recursive search technique similar to depth first search. The primary difference between backtracking and depth first search is that DFS operates on a tree which exists in memory, while with backtracking there is no physical tree. The tree is inferred from the search pattern. In this assignment you are to use backtracking to solve Sudoku puzzles.
The Sudoku puzzle will be read in from a text file. You can create your own files by copying and pasting the following data into Notepad or some other text editor. The following is a valid puzzle:
0 0 3 0 2 0 6 0 0
9 0 0 3 0 5 0 0 1
0 0 1 8 0 6 4 0 0
0 0 8 1 0 2 9 0 0
7 0 0 0 0 0 0 0 8
0 0 6 7 0 8 2 0 0
0 0 2 6 0 9 5 0 0
8 0 0 2 0 3 0 0 9
0 0 5 0 1 0 3 0 0
The following is an invalid start board:
0 0 3 0 2 0 6 0 0
9 0 0 3 0 5 0 0 1
0 0 1 8 0 6 4 0 0
0 0 8 1 0 2 9 0 0
7 0 0 0 0 0 0 0 8
0 0 6 7 0 8 2 0 0
0 0 2 6 0 9 5 0 0
8 0 0 2 0 3 0 0 9
0 0 5 0 9 0 3 0 0
The following is a puzzle which has no solution:
5 0 3 0 2 0 6 0 0
9 0 0 3 0 5 0 0 1
0 0 1 8 0 6 4 0 0
0 0 8 1 0 2 9 0 0
7 0 0 0 0 0 0 0 8
0 0 6 7 0 8 2 0 0
0 0 2 6 0 9 5 0 0
8 0 0 2 0 3 0 0 9
0 0 5 0 1 0 3 0 0
The zeros represent open elements
This is the pseudo-code for the backtracking search of a Sudoku Puzzle:
boolean BackTrack (Board){
Find the first open element on the Board in row major order.
If there are no open elements return true (The puzzle is solved).
Calculate the candidates for this open element.
If there are no candidates return false. (We have reached a dead
end and need to backtrack)
For each candidate{
place candidate in the first open element on the Board
if (Backtrack(Board)) return true
remove the candidate that was placed before the recursive call
}
return false;
}
No GUI is required for this assignment. All operations will be done in the terminal window.
The program should first prompt for the file path to the puzzle file. This file is then read into memory. A validity test is performed on the data to ensure we are not starting from an invalid board. The validity test should check to see if there are any values greater than 9 or any multiple occurrences of values in the same row, column or square. If the file has invalid data, the program should print a message stating this, then prompt for the file path again. If the data is valid, the search will run. If the search is successful the completed puzzle will be printed to the terminal window. If the search finds that the puzzle had no solution it should print a message stating this. The program then asks if the user wants to continue, and repeats this process if the answer is "Y".
The purpose of this assignment is to give students practice with writing a program which uses multiple classes. You should remember our discussion in class about the single responsibility theorem and separation of concerns. Each class should be responsible for one thing. I am not going to tell you how many classes I think you should be using. It is up to you to look at the problem and decide how it should best be represented. You must submit a program with a reasonable number of classes. If you submit a program with all of your code in one class you will fail even if the search works.
Additionally, you should not use any of the Java Library container classes. If you think you need a linked list to store the candidates, then implement your own linked list. If you think a set would be a better choice, make your own set class. In order to get full marks you need to do three things:
1. Implement a working backtrack search as specified in Program Operation.
2. Use a reasonable number of classes where the workload is reasonably evenly distributed between classes. Note that it is possible to use too many classes, although too few is a much more common problem.
3. Adequately comment your code.