Lab 45
Lab 45
Lab 45
Introduction
In Constraint Satisfaction Problems (CSPs), the goal is to find a complete, consistent assignment
of values to a set of variables 𝑋 (taken from their domains 𝐷) satisfying a set of constraints 𝐶 that
limit the valid combinations of variable values. In this assignment, you will have an opportunity
to develop a program using CSP solution techniques to solve Sudoku puzzles.
Sudoku (Japanese meaning number place) puzzle is a 9x9 grid (81 variables) where each cell in
the grid can take on the integer values 1-9 (the domain of each variable). A solution to a Sudoku
puzzle is an assignment of values for each cell in the grid such that no two cells in the same row,
column, or 3x3 square have the same value.
For example, for an initial configuration of a Sudoku puzzle, you might be given:
003|020|600
900|305|001
001|806|400
-----------
008|102|900
700|000|008
006|708|200
-----------
002|609|500
800|203|009
005|010|300
which has the solution:
483|921|657
967|345|821
251|876|493
-----------
548|132|976
729|564|138
136|798|245
-----------
372|689|514
814|253|769
695|417|382
Getting Started
The code you will be using can be downloaded as a zip archive on Blackboard, namely Lab45-
Sudoku.
Assignment
Your assignment is to write a program in Python that can take a set of Sudoku puzzles as input
from a file, models each puzzle as a CSP, and outputs solutions to each puzzle.
Extract the files into a directory/folder on your computer which will contain several files of Sudoku
puzzles:
And other files that you can and cannot modify as below
sudoku.py The main file that runs to solve all Sudoku problems.
Exercise 1: Implement the constraint satisfaction problem in the initialize function in the csp.py.
How did you represent the Sudoku puzzle a CSP? What design options did you consider, and how
did you decide on this implementation?
Your program should be able to read in these puzzles, solve them, then output the solutions in the
same format (a string of 81 digits, followed by a newline character) in the same order they were
read in from file, so that it is called as follow:
What to submit
1. The solutions to all 145 puzzles in the same format as the input files (please put all of the
euler.txt solutions under a header called “Euler” and the magictour.txt solutions under a
header called “Magic Tour”)
2. A short paragraph describing your experience during the assignment (what did you enjoy,
what was difficult, etc.)
3. An estimation of how much time you spent on the assignment.
4. Source code + README (how to compile and run your code).
5. Please create a folder called "yourname_StudentID_Lab45" that includes all the required
files and generate a zip file called "yourname_StudentID_Lab45.zip".
6. Please submit your work (.zip) to Blackboard.