Part 1: CSP: Word Sudoku
Created by Daniel Calzada based on dkmGames version of the game
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 9×9 grid with numbers 1-9 such that each row, column, and the nine 3×3 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 3×3 cell cannot contain duplicate letters. To familiarize yourself with this game, we recommend playing it for yourself athttp://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 (example). 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 (example).
Your task is to implement backtracking search (see lecture) 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 9×9 grid that satisfies all the constraints (example). 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.
Grid File | Word Bank
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.
Grid File (empty) | Word Bank
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.
Grid File | Word Bank