使用 Backtracking
算法，解决 Sudoku 问题。
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
A1…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.
What To Submit
Your program will be executed as follows:
$ python driver_3.py
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:
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.:
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.
Important Information
- Test-Run Your Code
Test, test, test. Make sure you produce an output file with the exact format
of the example given. - 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. - 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. - Just for fun
Try your code on the world’s hardest Sudokus! There’s nothing to submit here,
just for fun.
For example:
Sudoku:
Solution:
