Homework 4 Sudoku
Homework 4 reads sudoku puzzles, solves them, and displays of course.
As I say in my comments...
* author Ryan M Phillips
* Feb 8 2014
* CS2420-EAE
*
* Class defines a Sudoku puzzle
* It will read a sudoku puzzle file, the name of which is a parameter
* It holds the puzzle solution with puzzle[][]
* It keeps track of how many times the puzzle has to backtrack in order to solve
* Solves with brute force
My Main class determines what file to read, calls the solve and display functions.
Here is some copy of my console after solving a few different puzzles:
Sudoku Puzzle:
6 8 . . . . . 5 .
. . . . . 5 . . .
. . 3 8 . . 2 6 .
1 . 7 . 2 . . . .
. . 9 5 . 8 6 . .
. . . . 1 . 7 . 2
. 2 1 . . 9 4 . .
. . . 4 . . . . .
. 3 . . . . . 2 8
Solution in progress, please wait...
Solved
Number of Backtracking Instances: 14512
Sudoku Puzzle:
6 8 2 7 9 3 1 5 4
7 1 4 2 6 5 8 9 3
5 9 3 8 4 1 2 6 7
1 6 7 3 2 4 5 8 9
2 4 9 5 7 8 6 3 1
3 5 8 9 1 6 7 4 2
8 2 1 6 3 9 4 7 5
9 7 5 4 8 2 3 1 6
4 3 6 1 5 7 9 2 8
Sudoku Puzzle:
6 8 1 . . . . 5 .
. . . . . 5 . . .
. 5 3 8 . . 2 6 .
1 . 7 . 2 . . . .
. . 9 5 3 8 6 1 .
3 . . . 1 . 7 . 2
. 2 1 . . 9 4 . .
. . . 4 . . . . .
. 3 4 . . . . 2 8
Solution in progress, please wait...
Cannot Be Solved
Number of Backtracking Instances: 5581
Sudoku Puzzle:
6 8 1 . . . . 5 .
. . . . . 5 . . .
. 5 3 8 . . 2 6 .
1 . 7 . 2 . . . .
. . 9 5 3 8 6 1 .
3 . . . 1 . 7 . 2
. 2 1 . . 9 4 . .
. . . 4 . . . . .
. 3 4 . . . . 2 8
Sudoku Puzzle:
5 4 . 2 . 9 . . 1
. . . 5 . . . . 4
. . 7 . . . 9 . .
8 . . . 3 . . 6 7
. . . 6 . 5 . . .
9 3 . . 1 . . . 2
. . 1 . . . 6 . .
2 . . . . 6 . . .
3 . . 1 . 7 . 4 9
Solution in progress, please wait...
Solved
Number of Backtracking Instances: 2128
Sudoku Puzzle:
5 4 3 2 6 9 8 7 1
6 8 9 5 7 1 3 2 4
1 2 7 8 4 3 9 5 6
8 1 5 9 3 2 4 6 7
4 7 2 6 8 5 1 9 3
9 3 6 7 1 4 5 8 2
7 9 1 4 2 8 6 3 5
2 5 4 3 9 6 7 1 8
3 6 8 1 5 7 2 4 9
Sudoku Puzzle:
. . . . . . . . .
. . . . . 3 . 8 5
. . 1 . 2 . . . .
. . . 5 . 7 . . .
. . 4 . . . 1 . .
. 9 . . . . . . .
5 . . . . . . 7 3
. . 2 . 1 . . . .
. . . . 4 . . . 9
Solution in progress, please wait...
Solved
Number of Backtracking Instances: 69175252
Sudoku Puzzle:
9 8 7 6 5 4 3 2 1
2 4 6 1 7 3 9 8 5
3 5 1 9 2 8 7 4 6
1 2 8 5 3 7 6 9 4
6 3 4 8 9 2 1 5 7
7 9 5 4 6 1 8 3 2
5 1 9 2 8 6 4 7 3
4 7 2 3 1 9 5 6 8
8 6 3 7 4 5 2 1 9
A couple notes on this. I originally solved it not by backtracking to the method that called a failure state, but forward into another recursive call to the backtrack'ed position... which I learned is not plausible because it takes up way too much memory when there are a lot of backtracking and would run up against overflow errors on all large problems. I had to rethink my solution, which is why this one came a day late.