Starting from:
$30
Constraint Satisfaction Problems
Constraint Satisfaction Problems
INSTRUCTIONS
In this assignment you will focus on constraint satisfaction problems. You will be
implementing the AC-3 and backtracking algorithms to solve Sudoku puzzles. The
objective of the game is just to fill a 9 x 9 grid with numerical digits so that each column,
each row, and each of the nine 3 x 3 sub-grids (also called boxes) contains one of all of
the digits 1 through 9. If you have not played the game before, you may do so
at sudoku.com to get a sense of how the game works. Please read all sections
of the instructions carefully.
I. Introduction
II. What You Need To Submit
III. AC-3 Algorithm
IV. Backtracking Algorithm
V. Important Information
VI. Before You Submit
I. Introduction
Consider the Sudoku puzzle as pictured above. There are 81 variables in total, i.e. the
tiles to be filled with digits. Each variable is named by its row and its column, and must
be assigned a value from 1 to 9, subject to the constraint that no two cells in the same
row, column, or box may contain the same value.
In designing your classes, you may find it helpful to represent a Sudoku board with a
Python dictionary. The keys of the dictionary will be the variable names, each of which
corresponds directly to a location on the board. In other words, we use the variable
names Al through A9 for the top row (left to right), down to I1 through I9 for the
bottom row. For example, in the example board above, we would have sudoku["B1"] = 9,
and sudoku["E9"] = 8. This is the highly suggested representation, since it is easiest to
frame the problem in terms of variables, domains, and constraints if you start this
way. In this assignment, we will use the number zero to indicate tiles that have not yet
been filled.
II. What You Need To Submit
Your job in this assignment is to write driver.py, which intelligently solves Sudoku
puzzles. Your program will be executed as follows:
$ python driver.py <input_string
In the starter code folder, you will find the file sudokus_start.txt, containing hundreds
of sample Sudoku puzzles to be solved. Each Sudoku puzzle is represented as a single
line of text, which starts from the top-left corner of the board, and enumerates the digits
in each tile, row by row. For example, the first Sudoku board in sudokus_start.txt is
represented as the string:
003020600900305001001806400008102900700000008006708200002609500800203009005010
300
When executed as above, replacing "<input_string" with any valid string
representation of a Sudoku board (for instance, taking any Sudoku board
from sudokus_start.txt), your program will generate a file called output.txt, containing
a single line of text representing the finished Sudoku board. Since this board is solved,
the string representation will contain no zeros. Here is an example of an output:
483921657967345821251876493548132976729564138136798245372689514814253769695417
382
You may test your program extensively by using sudokus_finish.txt, which contains
the solved versions of all of the same puzzles.
Note on Python 3
As usual, if you choose to use Python 3, then name your program driver_3.py. In
that case, the grader will automatically run your program using the python3 binary
instead. Please only submit one version. If you submit both versions, the grader will
only grade one of them, which probably not what you would want. To test your
algorithm in Python 3, execute the game manager like so:
$ python3 driver_3.py <input_string
Besides your code (your driver and any other python code dependency), submit
a file hw_sudoku_UNI.txt with you results and observations (including the
number of sudoku you could solve and which one were solved), running time,
and all relevant information.
III. AC-3 Algorithm
First, implement the AC-3 algorithm. Test your code on the provided set of puzzles
in sudokus_start.txt. To make things easier, you can write a separate wrapper script
(bash, or python) to loop through all the puzzles to see if your program can solve them.
How many of the puzzles you can solve? Is this expected or unexpected? Report the
puzzles you can solve with AC-3 alone in hw_sudoku_UNI.txt. Reporting the index
of the puzzles you can solve with Sudoku is enough. Report also your observations,
running time, and any relevant information about your implementation.
IV. Backtracking Algorithm
Now, implement backtracking search using the minimum remaining value heuristic.
The order of values to be attempted for each variable is up to you. When a variable is
assigned, apply forward checking to reduce variables domains.
Test your code on the provided set of puzzles in sudokus_start.txt. Use your AC-3
implementation to reduce the domains of variable before you perform backtracking
search.
Can you solve all puzzles now? Report the puzzles you can solve now using AC-3
followed by backtracking search. Report your observations, running time, difference in
running time between backtracking alone and backtracking preceded with AC-3 and
any relevant information about your implementation (no specific format of the write-up
will be provided, use your best judgment).
V. Important Information
Please read the following information carefully. Before you post a clarifying question on
piazza, make sure that your question is not already answered in the following sections.
1. Test-Run Your Code
Please test your code and make sure it successfully produces an output file with the
correct format. Make sure the format is the same the example provided above.
2. Grading Submissions
We will test your final program on 20 test cases. Each input test case will be rated 5
points for a successfully solved board, and zero for any other resultant output. The test
cases are no different in nature than the hundreds of test cases already provided in your
starter code folder, for which the solutions are also available. If you can solve all of
those, your program will most likely get full credit. In addition, you will also get 10
extra points for a clear concise write-up. In sum, your submission will be assessed out
of a total of 110 points. The 10 extra points are bonus.
3. Time Limit
By now, we expect that you have a good sense of appropriate data structures and object
representations. Naive brute-force approaches to solving Sudoku puzzles may take
minutes, or even hours, to [possibly never] terminate. However, a correctly
implemented backtracking approach as specified above should take well under a
minute per puzzle. The grader will provide some breathing room, but programs with
much longer running times will be killed.
4. Just for fun
Try your code on the world’s hardest Sudoku and see if you can solve them! There is
nothing to submit here, just for fun. Here is an example:
Sudoku:
800000000003600000070090200050007000000045700000100030001000068008500010090000
400
Solution:
812753649943682175675491283154237896369845721287169534521974368438526917796318
452
INSTRUCTIONS
In this assignment you will focus on constraint satisfaction problems. You will be
implementing the AC-3 and backtracking algorithms to solve Sudoku puzzles. The
objective of the game is just to fill a 9 x 9 grid with numerical digits so that each column,
each row, and each of the nine 3 x 3 sub-grids (also called boxes) contains one of all of
the digits 1 through 9. If you have not played the game before, you may do so
at sudoku.com to get a sense of how the game works. Please read all sections
of the instructions carefully.
I. Introduction
II. What You Need To Submit
III. AC-3 Algorithm
IV. Backtracking Algorithm
V. Important Information
VI. Before You Submit
I. Introduction
Consider the Sudoku puzzle as pictured above. There are 81 variables in total, i.e. the
tiles to be filled with digits. Each variable is named by its row and its column, and must
be assigned a value from 1 to 9, subject to the constraint that no two cells in the same
row, column, or box may contain the same value.
In designing your classes, you may find it helpful to represent a Sudoku board with a
Python dictionary. The keys of the dictionary will be the variable names, each of which
corresponds directly to a location on the board. In other words, we use the variable
names Al through A9 for the top row (left to right), down to I1 through I9 for the
bottom row. For example, in the example board above, we would have sudoku["B1"] = 9,
and sudoku["E9"] = 8. This is the highly suggested representation, since it is easiest to
frame the problem in terms of variables, domains, and constraints if you start this
way. In this assignment, we will use the number zero to indicate tiles that have not yet
been filled.
II. What You Need To Submit
Your job in this assignment is to write driver.py, which intelligently solves Sudoku
puzzles. Your program will be executed as follows:
$ python driver.py <input_string
In the starter code folder, you will find the file sudokus_start.txt, containing hundreds
of sample Sudoku puzzles to be solved. Each Sudoku puzzle is represented as a single
line of text, which starts from the top-left corner of the board, and enumerates the digits
in each tile, row by row. For example, the first Sudoku board in sudokus_start.txt is
represented as the string:
003020600900305001001806400008102900700000008006708200002609500800203009005010
300
When executed as above, replacing "<input_string" with any valid string
representation of a Sudoku board (for instance, taking any Sudoku board
from sudokus_start.txt), your program will generate a file called output.txt, containing
a single line of text representing the finished Sudoku board. Since this board is solved,
the string representation will contain no zeros. Here is an example of an output:
483921657967345821251876493548132976729564138136798245372689514814253769695417
382
You may test your program extensively by using sudokus_finish.txt, which contains
the solved versions of all of the same puzzles.
Note on Python 3
As usual, if you choose to use Python 3, then name your program driver_3.py. In
that case, the grader will automatically run your program using the python3 binary
instead. Please only submit one version. If you submit both versions, the grader will
only grade one of them, which probably not what you would want. To test your
algorithm in Python 3, execute the game manager like so:
$ python3 driver_3.py <input_string
Besides your code (your driver and any other python code dependency), submit
a file hw_sudoku_UNI.txt with you results and observations (including the
number of sudoku you could solve and which one were solved), running time,
and all relevant information.
III. AC-3 Algorithm
First, implement the AC-3 algorithm. Test your code on the provided set of puzzles
in sudokus_start.txt. To make things easier, you can write a separate wrapper script
(bash, or python) to loop through all the puzzles to see if your program can solve them.
How many of the puzzles you can solve? Is this expected or unexpected? Report the
puzzles you can solve with AC-3 alone in hw_sudoku_UNI.txt. Reporting the index
of the puzzles you can solve with Sudoku is enough. Report also your observations,
running time, and any relevant information about your implementation.
IV. Backtracking Algorithm
Now, implement backtracking search using the minimum remaining value heuristic.
The order of values to be attempted for each variable is up to you. When a variable is
assigned, apply forward checking to reduce variables domains.
Test your code on the provided set of puzzles in sudokus_start.txt. Use your AC-3
implementation to reduce the domains of variable before you perform backtracking
search.
Can you solve all puzzles now? Report the puzzles you can solve now using AC-3
followed by backtracking search. Report your observations, running time, difference in
running time between backtracking alone and backtracking preceded with AC-3 and
any relevant information about your implementation (no specific format of the write-up
will be provided, use your best judgment).
V. Important Information
Please read the following information carefully. Before you post a clarifying question on
piazza, make sure that your question is not already answered in the following sections.
1. Test-Run Your Code
Please test your code and make sure it successfully produces an output file with the
correct format. Make sure the format is the same the example provided above.
2. Grading Submissions
We will test your final program on 20 test cases. Each input test case will be rated 5
points for a successfully solved board, and zero for any other resultant output. The test
cases are no different in nature than the hundreds of test cases already provided in your
starter code folder, for which the solutions are also available. If you can solve all of
those, your program will most likely get full credit. In addition, you will also get 10
extra points for a clear concise write-up. In sum, your submission will be assessed out
of a total of 110 points. The 10 extra points are bonus.
3. Time Limit
By now, we expect that you have a good sense of appropriate data structures and object
representations. Naive brute-force approaches to solving Sudoku puzzles may take
minutes, or even hours, to [possibly never] terminate. However, a correctly
implemented backtracking approach as specified above should take well under a
minute per puzzle. The grader will provide some breathing room, but programs with
much longer running times will be killed.
4. Just for fun
Try your code on the world’s hardest Sudoku and see if you can solve them! There is
nothing to submit here, just for fun. Here is an example:
Sudoku:
800000000003600000070090200050007000000045700000100030001000068008500010090000
400
Solution:
812753649943682175675491283154237896369845721287169534521974368438526917796318
452
1 file (425.4KB)
