A sudoku grid consists of 9 lines and 9 columns, making up 81 cells, that are grouped in nine 3x3 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.

You will design and implement a program that will read a sudoku grid whose representation is stored in a file filename .txt and create a Sudoku object, with a number of methods:

. a method preassess() that prints out to standard output whether the representation is correct and has no digit that occurs twice on the same row, on the same column or in the same box;

. a method bare_tex_output() that outputs some Latex code to a file, filename_bare.tex, that can be compiled by pdflatex to produce a pictorial representation of the grid;

. a method forced_tex_output() that outputs some Latex code to a file, filename_forced.tex, that can be compiled by pdflatex to produce a pictorial representation of the grid to which the forced digits

technique has been applied;

. a method marked_tex_output() that outputs some Latex code to a file, filename_marked.tex, that can be compiled by pdflatex to produce a pictorial representation of the grid to which the forced digits

technique has been applied and that has been marked;

. a method worked_tex_output() that outputs some Latex code to a file, filename_worked.tex, that can be compiled by pdflatex to produce a pictorial representation of the grid to which the forced digits technique has been applied, that has been marked, and to which the preemptive set technique has been applied.

The input is expected to consist of 9 lines of digits, with possibly lines consisting of spaces only that will be ignored and with possibly spaces anywhere on the lines with digits. If the input is incorrect, that is, does not satisfy the conditions just spelled out, then the program should generate a SudokuError with Incorrect  input as message.

Here is a possible interaction:

$  python3

...

>>>  from  sudoku  import  *

>>>  Sudoku('sudoku_wrong_1.txt')

...

sudoku.SudokuError:  Incorrect  input

>>>  Sudoku('sudoku_wrong_2.txt')

...

sudoku.SudokuError:  Incorrect  input

>>>  Sudoku('sudoku_wrong_3.txt')

...

sudoku.SudokuError:  Incorrect  input

3.  Examples

3.1. First example. The file sudoku_1.txt has the following contents.

Here is a possible interaction:

$  python3

...

>>>  from  sudoku  import  *

>>>  sudoku  =  Sudoku('sudoku_1.txt')

>>>  sudoku.preassess()

There  is  clearly  no  solution .

3.2. Second example. The file sudoku_2.txt has the following contents.

Here is a possible interaction:

$  python3

...

>>>  from  sudoku  import  *

>>>  sudoku  =  Sudoku('sudoku_2.txt')

>>>  sudoku.preassess()

There  is  clearly  no  solution .

3.3. Third example. The file sudoku_3.txt has the following contents.

Here is a possible interaction:

$  python3

...

>>>  from  sudoku  import  *

>>>  sudoku  =  Sudoku('sudoku_3.txt')

>>>  sudoku.preassess()

There might  be  a  solution .

>>>  sudoku.bare_tex_output()

>>>  sudoku.forced_tex_output()

>>>  sudoku.marked_tex_output()

>>>  sudoku.worked_tex_output()

The effect of executing sudoku.bare_tex_output() is to produce a file named sudoku 3 bare.tex that can be given as argument to pdflatex to produce a file named sudoku 3 bare.pdf that views as the grid on page 2.

The effect of executing sudoku.worked_tex_output() is to produce a file named sudoku 3 worked.tex that can be given as argument to pdflatex to produce a file named sudoku 3 worked.pdf that views identically to sudoku_3_marked.pdf.

3.4. Fourth example. The file sudoku_4.txt has the following contents.

Here is a possible interaction:

$  python3

...

>>>  from  sudoku  import  *

>>>  sudoku  =  Sudoku('sudoku_4.txt')

>>>  sudoku.preassess()

There might  be  a  solution .

>>>  sudoku.bare_tex_output()

>>>  sudoku.forced_tex_output()

>>>  sudoku.marked_tex_output()

>>>  sudoku.worked_tex_output()

The effect of executing sudoku.bare_tex_output() is to produce a file named sudoku 4 bare.tex that can be given as argument to pdflatex to produce a file named sudoku 4 bare.pdf that views as follows.

The effect of executing sudoku.forced_tex_output() is to produce a file named sudoku 4 forced.tex that can be given as argument to pdflatex to produce a file named sudoku 4 forced.pdf that views as follows.

The effect of executing sudoku.marked_tex_output() is to produce a file named sudoku 4 marked.tex that can be given as argument to pdflatex to produce a file named sudoku 4 marked.pdf that views as follows.

The effect of executing sudoku.worked_tex_output() is to produce a file named sudoku 4 worked.tex that can be given as argument to pdflatex to produce a file named sudoku 4 worked.pdf that views as follows.

3.5. Fifth example. The file sudoku_5.txt has the following contents.

Here is a possible interaction:

$  python3

...

>>>  from  sudoku  import  *

>>>  sudoku  =  Sudoku('sudoku_5.txt')

>>>  sudoku.preassess()

There might  be  a  solution .

>>>  sudoku.bare_tex_output()

>>>  sudoku.forced_tex_output()

>>>  sudoku.marked_tex_output()

>>>  sudoku.worked_tex_output()

The effect of executing sudoku.bare_tex_output() is to produce a file named sudoku 5 bare.tex that can be given as argument to pdflatex to produce a file named sudoku 5 bare.pdf that views as follows.

The effect of executing sudoku.forced_tex_output() is to produce a file named sudoku 5 forced.tex that can be given as argument to pdflatex to produce a file named sudoku 5 forced.pdf that views as follows.

The effect of executing sudoku.marked_tex_output() is to produce a file named sudoku 5 marked.tex that can be given as argument to pdflatex to produce a file named sudoku 5 marked.pdf that views as follows.

The effect of executing sudoku.worked_tex_output() is to produce a file named sudoku 5 worked.tex that can be given as argument to pdflatex to produce a file named sudoku 5 worked.pdf that views as follows.

4.  Precisions