Use your SVN client to update your individual SVN repository. You should find a new folder, GoSudoku. Within the folder are four files: sudoku.go, sudoku_test.go, docs.html and Makefile.
These files follow the conventions described in How to Write Go Code. While those conventions are primarily about writing new Go packages, we’re using them for the basic unit testing facilities they provide.
The file sudoku.go contains a partial implementation for a Sudoku puzzle solver. Your job is to complete the solver.
Sudoku is a numeric puzzle game that originated in Japan. A Sudoku puzzle typically consists of an n×n matrix of n×n matrices. The solver’s task is to fill in each cell of the larger matrix with the numbers 1 through n2. This must be done so that each row, each column, and each smaller matrix contains every number (and hence, no duplicates).
The figure on the left below shows a starting configuration for a puzzle with n=3. The figure on the right shows the solved puzzle. Solutions are not necessarily unique, though in published puzzles the given configuration typically constrains the puzzle to a single solution.
Puzzle from Grand Master Su Doku Ultimate, by Wayne Gould, p. 11.
Humans typically solve Sudoku puzzles by analyzing constraints and identifying cells where only one number fits, or pairs of cells where only two numbers fit. For example, consider where we could put a 1 in the top-center small matrix of the puzzle above—the one with 2, 7, 6, and 9 filled in. The 1 can’t go in the first row, because of the 1 in the top-right matrix. The 1 can’t go in the third row, because of the 1 in the top-left matrix. Finally, the 1 can’t go in the fourth column, because of the 1 in the bottom-center matrix. Thus, the 1 in the top-center matrix must go to the right of the 6.
A computer program could use the same strategy, perhaps using dynamic programming. However, for small values of n, it is better to use a recursive search with backtracking.
sudoku_test.go provides a full suite of unit tests. Compile the program and run the tests by cding into the GoSudoku directory and running the command gotest. The tests are written in the order that I implemented my solution. You'll probably want to comment out later tests and just get one test case at a time to work.docs.html is the godoc-generated documentation of sudoku.go. Read over the file to get an idea of the provided datatypes, methods, and functions.
sudoku.go in your favorite text editor. Study the provided code. You will need to use the provided functions in your solution.
You should complete the TODO items in the provided code in the order given. That is, implement and test these methods in order:
func (b *Board) IsFull() (full bool, r, c int)func (b *Board) IsValid() boolfunc (b *Board) ValidGuesses(r, c int) BitSetfunc (b *Board) Solve() (result *Board, success bool)// Recursive, but not concurrentfunc (b *Board) ConcSolve() (result *Board, success bool)// Recursive and concurrent
The comments in the file and the unit tests provide the specifications for these methods.
If you are completely stuck on a problem, you may “purchase” a function from me for 2 points. To do that, commit your code demonstrating that you have solutions to the earlier methods and send me an email requesting the answer to the next method. I’ll email back the code. I’m relying on your honesty to not share answers with classmates. Don’t count on me being up all night on Wednesday to send answers. You’ll need to start early to solve this problem.