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.
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:
Test your program using sudokus_finish.txt, which contains the solved versions of all of the same puzzles.
I. 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.
