[SOLVED] Constraint satisfaction problem

Contents

Part 1: Constraint satisfaction problem (Word Sudoku)

Part 1: Word Sudoku (for everybody)

Inspired by 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 game is to fill in a partially-completed 99 grid with numbers 1-9 such that each row, column, and the nine 33 sub-grids contain no duplicate numbers. Below, you can see a sample of an unsolved and solved sudoku puzzle. This can be thought of as a constraint-satisfaction problem.

Images from Wikipedia

In this assignment, we will implement a variation on Sudoku where, instead of filling the grid with numbers, we will fill the grid with words. You will be given a word bank, a list of words that must be used exactly once (unless otherwise specified), arranged 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 (see exmaple). Following the rules of Sudoku, each row, column, and 33 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 (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).

For each of the parts below, please include in your report:

Your solution, the filled 99 grid that satisfies all the constraints (example). Please either upload 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.

Part 1: Start Grid with Hints
In this part, some of the cells in the grid will already be filled in for you.
Grid File | Word Bank

Part 2: 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

Part 3: Decoy Words
In this puzzle, youl 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 know which ones) will not be used in the final solution. You will need to find which words should be placed and which ones shouldnt. Your solution should place as few words as possible. Think carefully about how you want to implement this in order to achieve a solution in a decent amount of time. In your report, make sure that you also include in your sequence of assignments the words that were not placed, according to the notation above.

(Note: A trivial solution would be to use brute-force, trying all possible subsets of the words in the word bank until you find a combination that completely fills the grid. However, as this is an assignment on CSPs, if you use brute force, you will not receive credit for this part.)
Grid File | Word Bank

Conceptual Questions
In addition to including the above in your report, answer these questions. For some, there is no correct answer. The questions are designed to help you think conceptually about what youve written:

What are the variables in this CSP, and what values can they be assigned? With these in mind, how did you compute the most constrained and most constraining variable and the least constraining value?
How did you change your variables, assignment values, and/or algorithm to account for the case in Part 3 where each word may or may not be needed in the final solution?
How would the variables, values, and even the word bank be different if you were solving original numeric Sudoku instead of Word Sudoku?
Could you solve this problem as a tree-structured CSP? If so, explain how. If not, explain why not.

Report Checklist

Part 1:

For everybody: Include your answers to the four bullet points above for each of the three word bank/grid combinations, along with the answers to the conceptual questions above.

WARNING: You will not get credit for any solutions that you have obtained, but not included in your report! For example, if your code prints out path cost and number of nodes expanded on each input, but you do not put down the actual numbers in your report, or if you include pictures/files of your output solutions in the zip file but not in your PDF. The only exception is animated paths (videos or animated gifs).