Algorithms and Data Structures

Part 3:

Assignment 2 Part 3

Write a class called SudokuToSatReducer. This is where the bulk of the work is done.

An instance of this class receives the input file (not just a file name) as a parameter containing a Sudoku board, and outputs the equivalent boolean expression to a file in the DIMACS format, the format in which the SAT solver expects its input. This is accomplished by the following methods.

write a method to

Create a file for output.

Call createBoard( ) to create a Sudoku board, from the input file which is provided as a parameter.

Call reduceBoard() to reduce the board to a SAT input file.

Calculate and output the time taken for step c.

You can use the Timer class from your Assignment 1.

You may have to write the following methods. Each of these methods write a clause of numbers to the output file. So, remember to put a 0 at the end of each clause to be consistent with the DIMACS style input file format that your SAT solver expects. Also, you need to output the number of variables and the number of clauses to the output file. These methods translate the constraints on the Sudoku board puzzle. For explanations on the constraints see the assignment specification.

Write atleastOneInRow () to translate the constraint 1.1.A.

Write atmostOneInRow () to translate the constraint 1.1.B.

Write atleastOneInCol () to translate the constraint 2.1.A.

Write atmostOneInCol () to translate the constraint 2.1.B.

Write atleastOneInBox () to translate the constraint 3.1.A.

Write atmostOneInBox () to translate the constraint 3.1.B.

Similarly, two more methods for constraint 4.

Note that each of the above methods will be called several times (how many times and who calls?). furthermore, since the variables in a clause must be integers, each of the above functions must use an encoding scheme to convert the boolean variables to a single number. This encoding scheme should be written as a separate method.

If you need, you may have to write additional helper methods to complete the class.

Reducing Sudoku to SAT The constraints of a Sudoku puzzle can be modeled using a boolean formula in conjumctive normal form (cn). There are several ways to translate or encode a Sudoku problem into an equivalent SAT problem. The remaining of this section presents one of these encodings. The typical Sudoku puzzle that one finds in newspapers or pastime books consists ofa square grid of size 9, containing preset values in some of its 81 cells. The grid is subdivided into 9 3x3 boxes. The objective of the puzzle is to fill each blank cell so that each column, each row, and each box contains all the digits from 1 to 9 Create 729 (9x9x9) different bgoleanvariables where j j and k take on values from 1 to 9. Intuitively, the boolean variable uk is set to true if and only if the cell at row j and column j takes the value k. Recall the constraints on a Sudoku puzzle solution: 1. Each row must have all the digits 1 through 9 2. Each column must have all the digits 1 through 9, 3. Each 3x3 box must have all the digits 1 through 9, 4. Each cell must have exactly one value in the range 1 through !9 Constraints 1, 2, and 3 are similar except that each refers to a different subset of cells. We now present a SAT encoding for Constraint 1. Constraint, when applied to a rowi can be viewed as a conjunct (and) of the following nine constraints: 1.1. The number 1 is the value of exactly one cell in rowi 1.2The number 2 is the value of exactly one cell in row t For this project you will develop a SudokuToSAT reducer that receives an input puzzle and writes out a SAT instance in thecof format. Your reducer will: 1.9. The number 9 is the value of exactly one cell in row i 1. read an input Sudoku instance from a file, We will only address Constraint 1.1 since the other eight constraints can be translated in analogous manner. Constraint 1.1, in tun, can be broken down as a conjunct of two 2. translate the input Sudoku instance into an equivalent SAT instance Here are the details. 1.1.A At least one cell of row has the value 1 1.1.B. At most one cell of rowhas the value 1 Step 1 Your program will read from the command line the name of a file, and then read from this file the input Sudoku puzzle (instance). An input file for a Sudoku instance contains: Constraint 1.1A, for row i, yields the propositional clause: Zero or more comment lines at the beginning of the file, each starting with the character 'c', followed by Constraint 1.1 B. for row yields a subomula comprising 36 clauses of the form * a line with "3 3" that indicates the dimensions ofeach box in the puzzle, followed b a sequence of 31 integers in the range from 0 to 9. These integers are the values in Sudoku grid in row-major order, with a 0 indicating a cell that does not have a preset value. ((notuui) or (not vi^i) combined together with the and operator, for all distinet combinations of j and k, j and k in the range 1 through 9. Can you think of a mathematical formula to find the number of such distinct combinations? Step 2 Your program will then translate the input Sudoku instance into an equivalent SAT instance. A total of 37 (ie. 1 +36 clauses from the translation of Constraint 1.1 for row ivalue1 A total of 37 * %333 clauses from Constraint l for rowi A total of333 9-2997 clauses from Constraint Translating a Sudoku instance into an equivalent SAT instance Reducing Sudoku to SAT The constraints of a Sudoku puzzle can be modeled using a boolean formula in conjumctive normal form (cn). There are several ways to translate or encode a Sudoku problem into an equivalent SAT problem. The remaining of this section presents one of these encodings. The typical Sudoku puzzle that one finds in newspapers or pastime books consists ofa square grid of size 9, containing preset values in some of its 81 cells. The grid is subdivided into 9 3x3 boxes. The objective of the puzzle is to fill each blank cell so that each column, each row, and each box contains all the digits from 1 to 9 Create 729 (9x9x9) different bgoleanvariables where j j and k take on values from 1 to 9. Intuitively, the boolean variable uk is set to true if and only if the cell at row j and column j takes the value k. Recall the constraints on a Sudoku puzzle solution: 1. Each row must have all the digits 1 through 9 2. Each column must have all the digits 1 through 9, 3. Each 3x3 box must have all the digits 1 through 9, 4. Each cell must have exactly one value in the range 1 through !9 Constraints 1, 2, and 3 are similar except that each refers to a different subset of cells. We now present a SAT encoding for Constraint 1. Constraint, when applied to a rowi can be viewed as a conjunct (and) of the following nine constraints: 1.1. The number 1 is the value of exactly one cell in rowi 1.2The number 2 is the value of exactly one cell in row t For this project you will develop a SudokuToSAT reducer that receives an input puzzle and writes out a SAT instance in thecof format. Your reducer will: 1.9. The number 9 is the value of exactly one cell in row i 1. read an input Sudoku instance from a file, We will only address Constraint 1.1 since the other eight constraints can be translated in analogous manner. Constraint 1.1, in tun, can be broken down as a conjunct of two 2. translate the input Sudoku instance into an equivalent SAT instance Here are the details. 1.1.A At least one cell of row has the value 1 1.1.B. At most one cell of rowhas the value 1 Step 1 Your program will read from the command line the name of a file, and then read from this file the input Sudoku puzzle (instance). An input file for a Sudoku instance contains: Constraint 1.1A, for row i, yields the propositional clause: Zero or more comment lines at the beginning of the file, each starting with the character 'c', followed by Constraint 1.1 B. for row yields a subomula comprising 36 clauses of the form * a line with "3 3" that indicates the dimensions ofeach box in the puzzle, followed b a sequence of 31 integers in the range from 0 to 9. These integers are the values in Sudoku grid in row-major order, with a 0 indicating a cell that does not have a preset value. ((notuui) or (not vi^i) combined together with the and operator, for all distinet combinations of j and k, j and k in the range 1 through 9. Can you think of a mathematical formula to find the number of such distinct combinations? Step 2 Your program will then translate the input Sudoku instance into an equivalent SAT instance. A total of 37 (ie. 1 +36 clauses from the translation of Constraint 1.1 for row ivalue1 A total of 37 * %333 clauses from Constraint l for rowi A total of333 9-2997 clauses from Constraint Translating a Sudoku instance into an equivalent SAT instance