A sudoku grid consists of 9 lines and 9 columns, making up 81 cells, that are grouped in nine 3×3 boxes. In a
sudoku puzzle, some but not all of the cells already contain digits between 1 and 9. Here is an example of a
Solving a sudoku puzzle means completing the grid so that each digit from 1 to 9 occurs once and only once in
every row, once and only one in every column, and once and only once in every box. For instance, the previous
puzzle has the following solution.
Solving a sudoku puzzle is a very common assignment; it is not difficult and moderately interesting as a
“solution” (the completed grid) tells nothing about how the solution was reached. More interesting solvers are
logical in the sense that they (possibly partially only) solve the puzzle in steps and at every step, explain how
they made some progress; they do so by using some of the well known techniques that most people who solve
sudoku puzzles apply. Two remarks are in order.
Methods that only discover digits in empty cells are fairly limited; most methods need to keep track of
the list of possible digits that can go into a given cell, and making progress might mean reducing that
list. To apply techniques of the second kind, it is necessary to first mark the grid.
Often, it is not possible to completely solve a puzzle using exclusively the chosen methods; at some
point no progress can be made and then a random guess has to be made to either put a digit into a
given empty cell, or to remove a digit from the list of possible digits that can go into a given cell. It
might subsequently be necessary to backtrack and make alternative guesses if the earlier guesses turn
out to be inconsistent with a solution.
For this assignment, you will have to implement two such techniques, based on the notions of forced digits
and preemptive sets described in the paper A Pencil-and-Paper Algorithm for Solving Sudoku Puzzles by J. F.
Crook, Notices of the AMS, 56(4), pp. 460–468. Before anything else, you should study this paper. The forced
digits technique is applied first, followed by the preemptive set technique. When no progress can be made, the
forced digits techniques could be applied again, but that might not yield anything; an alternative would be to
try and fill some empty cell with one of the possible digits for that cell and apply the preemptive set technique
applied again, knowing that that guess might prove wrong and that other possible digits might have to be used
instead. In this assignment, we will stop at the point where the preemptive set technique can no longer be
applied; hence we can expect that our implementation will only partially solve most puzzles. But the technique
is very powerful and as explained in the article, subsumes many of the well known techniques.
本网站支持 Alipay WeChatPay PayPal等支付方式
E-mail: email@example.com 微信号:vipnxx