Starting from:
$30
Homework 4: CSPs
Artificial Intelligence
Homework 4: CSPs
SUBMISSION
You will submit one zip file, named hw4_myUNI.zip, which contains files:
- written.pdf,
- driver.py or driver_3.py [Both are included in the starter code. Update the one
you wish to use and delete the other before submitting]
- README.txt or .pdf
You can submit as many times as you like before the deadline. Only your most recent submission will be
graded. The written submission can be handwritten and scanned (PDF scanning mobile apps typically
work well), or typed, but it must be legible in order to receive credit.
WRITTEN
Consider the Sudoku puzzle below. Each variable is named by its row and its column
(see Programming “Introduction” for an example). Recall each variable 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.
1. List the names of the variables in the blue circle and their corresponding initial
value domains.
2. Reduce the domain for the four unassigned variables in question 1 by enforcing
arc constraints using the entire puzzle board. List the new domains.
3. Assume we have to choose one of the four unassigned variables in question 2 to
explore further. Using the minimum remaining value heuristic, which variable or
variables should we explore next?
4. Assume we choose A4 to explore next and assume that A6, B5, C5 are the last
three remaining variables waiting to be assigned. Using least constraining value
rule, which value of A4 should be tried first?
PROGRAMMING
I. Introduction
II. What To Submit
III. Backtracking Algorithm
IV. Important Information
V. Before You Submit
I. Introduction
The objective of Sudoku is to ll a 9x9 grid with the numbers 1-9 so that each column, row, and 3x3
sub-grid (or box) contains one of each digit. You may try out the game here: sudoku.com. Sudoku has
81 variables, i.e. 81 tiles. The variables are named by row and column, and are valued from 1 to 9
subject to the constraints that no two cells in the same row, column, or box may be the same.
Frame your problem in terms of variables, domains, and constraints. We suggest representing a
Sudoku board with a Python dictionary, where each key is a variable name based on location, and value
of the tile placed there. Using variable names Al… A9… I1… I9, the board above has:
- sudoku_dict["B1"] = 9, and
- sudoku_dict["E9"] = 8.
We give value zero to a tile that has not yet been filled.
II. What To Submit
Your program will be executed as follows:
$ python driver.py <input_string
In the starter zip, sudokus_start.txt, contains hundreds of sample unsolved Sudoku boards, and
sudokus_finish.txt the corresponding solutions. Each board is represented as a single line of text, starting
from the top-left corner of the board, and listed left-to-right, top-to-bottom.
The first board in sudokus_start.txt is represented as the string:
003020600900305001001806400008102900700000008006708200002609500800203009005010300
Which is equivalent to:
0 0 3 0 2 0 6 0 0
9 0 0 3 0 5 0 0 1
0 0 1 8 0 6 4 0 0
0 0 8 1 0 2 9 0 0
7 0 0 0 0 0 0 0 8
0 0 6 7 0 8 2 0 0
0 0 2 6 0 9 5 0 0
8 0 0 2 0 3 0 0 9
0 0 5 0 1 0 3 0 0
Your program will generate output.txt, containing a single line of text representing the finished Sudoku
board. E.g.:
483921657967345821251876493548132976729564138136798245372689514814253769695417382
Test your program using sudokus_finish.txt, which contains the solved versions of all of the same
puzzles.
Besides your driver (and any other python code dependency), submit a README.txt with your
results and observations, including the:
- number AND line numbers of boards you could solve from sudokus_start.txt,
- running time, and
- any other relevant information.
III. Backtracking Algorithm
Implement backtracking search using the minimum remaining value heuristic. Pick your own order of
values to try for each variable, and apply forward checking to reduce variables domains.
- Test your program on sudokus_start.txt.
- Report the puzzles you can solve now, running time, observations.
IV. Important Information
1. Test-Run Your Code
Test, test, test. Make sure you produce an output file with the exact format of the example given.
2. Grading Submissions
We test your final program on 20 boards. Each board is worth 5 points if solved, and zero otherwise.
These boards are similar to those in your starter zip, so if you solve all those, you’ll get full credit.
3. Time Limit
No brute-force! Your program should solve puzzles in well under a minute per board. Programs with
much longer running times will be killed.
4. Just for fun
Try your code on the world’s hardest Sudokus! There’s nothing to submit here, just for fun. For example:
Sudoku:
800000000003600000070090200050007000000045700000100030001000068008500010090000400
Solution:
812753649943682175675491283154237896369845721287169534521974368438526917796318452
Homework 4: CSPs
SUBMISSION
You will submit one zip file, named hw4_myUNI.zip, which contains files:
- written.pdf,
- driver.py or driver_3.py [Both are included in the starter code. Update the one
you wish to use and delete the other before submitting]
- README.txt or .pdf
You can submit as many times as you like before the deadline. Only your most recent submission will be
graded. The written submission can be handwritten and scanned (PDF scanning mobile apps typically
work well), or typed, but it must be legible in order to receive credit.
WRITTEN
Consider the Sudoku puzzle below. Each variable is named by its row and its column
(see Programming “Introduction” for an example). Recall each variable 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.
1. List the names of the variables in the blue circle and their corresponding initial
value domains.
2. Reduce the domain for the four unassigned variables in question 1 by enforcing
arc constraints using the entire puzzle board. List the new domains.
3. Assume we have to choose one of the four unassigned variables in question 2 to
explore further. Using the minimum remaining value heuristic, which variable or
variables should we explore next?
4. Assume we choose A4 to explore next and assume that A6, B5, C5 are the last
three remaining variables waiting to be assigned. Using least constraining value
rule, which value of A4 should be tried first?
PROGRAMMING
I. Introduction
II. What To Submit
III. Backtracking Algorithm
IV. Important Information
V. Before You Submit
I. Introduction
The objective of Sudoku is to ll a 9x9 grid with the numbers 1-9 so that each column, row, and 3x3
sub-grid (or box) contains one of each digit. You may try out the game here: sudoku.com. Sudoku has
81 variables, i.e. 81 tiles. The variables are named by row and column, and are valued from 1 to 9
subject to the constraints that no two cells in the same row, column, or box may be the same.
Frame your problem in terms of variables, domains, and constraints. We suggest representing a
Sudoku board with a Python dictionary, where each key is a variable name based on location, and value
of the tile placed there. Using variable names Al… A9… I1… I9, the board above has:
- sudoku_dict["B1"] = 9, and
- sudoku_dict["E9"] = 8.
We give value zero to a tile that has not yet been filled.
II. What To Submit
Your program will be executed as follows:
$ python driver.py <input_string
In the starter zip, sudokus_start.txt, contains hundreds of sample unsolved Sudoku boards, and
sudokus_finish.txt the corresponding solutions. Each board is represented as a single line of text, starting
from the top-left corner of the board, and listed left-to-right, top-to-bottom.
The first board in sudokus_start.txt is represented as the string:
003020600900305001001806400008102900700000008006708200002609500800203009005010300
Which is equivalent to:
0 0 3 0 2 0 6 0 0
9 0 0 3 0 5 0 0 1
0 0 1 8 0 6 4 0 0
0 0 8 1 0 2 9 0 0
7 0 0 0 0 0 0 0 8
0 0 6 7 0 8 2 0 0
0 0 2 6 0 9 5 0 0
8 0 0 2 0 3 0 0 9
0 0 5 0 1 0 3 0 0
Your program will generate output.txt, containing a single line of text representing the finished Sudoku
board. E.g.:
483921657967345821251876493548132976729564138136798245372689514814253769695417382
Test your program using sudokus_finish.txt, which contains the solved versions of all of the same
puzzles.
Besides your driver (and any other python code dependency), submit a README.txt with your
results and observations, including the:
- number AND line numbers of boards you could solve from sudokus_start.txt,
- running time, and
- any other relevant information.
III. Backtracking Algorithm
Implement backtracking search using the minimum remaining value heuristic. Pick your own order of
values to try for each variable, and apply forward checking to reduce variables domains.
- Test your program on sudokus_start.txt.
- Report the puzzles you can solve now, running time, observations.
IV. Important Information
1. Test-Run Your Code
Test, test, test. Make sure you produce an output file with the exact format of the example given.
2. Grading Submissions
We test your final program on 20 boards. Each board is worth 5 points if solved, and zero otherwise.
These boards are similar to those in your starter zip, so if you solve all those, you’ll get full credit.
3. Time Limit
No brute-force! Your program should solve puzzles in well under a minute per board. Programs with
much longer running times will be killed.
4. Just for fun
Try your code on the world’s hardest Sudokus! There’s nothing to submit here, just for fun. For example:
Sudoku:
800000000003600000070090200050007000000045700000100030001000068008500010090000400
Solution:
812753649943682175675491283154237896369845721287169534521974368438526917796318452
1 file (230.9KB)
