# Python代写 | COMP9021 Assignment 2

本次澳洲代写主要为python数独游戏的assignment

2. Background

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

sudoku puzzle.

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.