Homework 4: CSPs Solution

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_3.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.




 
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