用Backtracking算法来解Sudoku游戏，整个作业分为三种难度，解Sudoku时间需要在10秒内。
Background
Sudoku is a puzzle that has gained much popularity since its first release in
a US Newspaper in 2004. The object of the original Sudoku is to fill in a
partially-completed 9x9 grid with numbers 1-9 such that each row, column, and
the nine 3x3 sub-grids contain no duplicate numbers. In this assignment, you
will implement a variation on Sudoku where, instead of filling the grid with
numbers, you will fill the grid with words. You will be given a word bank, or
a list of words that must be used exactly once (unless otherwise specified),
and you must arrange them so that every cell in the grid contains a letter.
Note that words will take up multiple cells in the grid and can be oriented
either horizontally or vertically, and words are allowed to overlap. Following
the rules of Sudoku, each row, column, and 3x3 cell cannot contain duplicate
letters. To familiarize yourself with this game, we recommend playing it for
yourself at http://dkmgames.com/WordSudoku.htm
. The only difference between the online
game and the game in this assignment is that in the online version, you are
given the orientation of the words, but in this assignment, your code must be
able to determine this for itself.
Word Sudoku game
The word bank will contain one word per line. The grid files will contain nine
lines of nine characters each. If the character is an underscore “_”, assume
that the letter that goes in that cell is unknown. Otherwise, assume that the
character belongs in the corresponding grid cell.
Your task is to implement backtracking search to solove the puzzles below.
First, you need to determine your formulation of the CSP and include it in
your report. What are the variables, domains, and constraints in your
formulation? With these in mind, implement any ordering heuristics that make
sense for your formulation to make your search efficient. Briefly describe
your implementation.
For each of the inputs below, please include in your report:
Your solution, the filled 9x9 grid that satisfies all the constraints. Please
either include an image of the filled grid, or inline it in a monospace font
(Courier New, for instance).
In order, the sequence of assignments made, where each assignment contains the
word, the coordinate of the top/left letter, and the orientation. Please
follow the format in the example file, corresponding to the sample grid above.
The lines are formatted as O,R,C: WORD, where O is the orientation (either H
or V) and R and C are the row/column for the top-left coordinate of the first
letter in the word. If you did not place this word on your grid (see Part 3),
use (N/A) instead.
The number of nodes expanded in the search tree. A state (either a partial or
full set of assignments) is considered expanded when its children states, if
any, are computed. This definition is equivalent to the definition of
expanding a node in a search tree.
The execution time of your search algorithm, in seconds or milliseconds.
Input 1 (for everybody): Start Grid with Hints
In this input, some of the cells in the grid will already be filled in for
you.
Input 2 (for everybody): Empty Start Grid
Solve another puzzle this time, except that unlike last time, you will not be
given hints in the starting grid.
Input 3 (for four credits only): Decoy Words
In this puzzle, you will be given a word bank and a non-empty start grid. The
challenge here is that some of the words in the word bank (you don’t know
which ones) will not be used in the final solution. You will need to find
which words should be placed and which ones shouldn’t. Your solution should
place as few words as possible. This requires traversing the entire search
tree and generating all possible solutions, so think carefully about how you
want to implement this in order to achieve a solution in a decent amount of
time. In your report, briefly describe any modifications to your
implementation you needed to make, and as part of your solution, also include
in your sequence of assignments the words that were not placed, according to
the notation above.
