Childrens' puzzle books often contain Word Search puzzles like the one shown at the right. These problems are fun enough to solve, but how are they created?
For the next several assignments, you will be writing a Python program
to create such a puzzle, using various search strategies. For extra credit, you may additionally write a LISP
program to solve it. For either language, you should use a functional programming
approach and representation as described below (e.g., we will use Python list representations
which closely match their LISP counterparts). For this assignment, you do not have to implement a solution strategy, other than the "flail wildly" search strategy, which is used to demonstrate that your routines work.
To write a program to solve this problem,
we will need to have
- a way to represent the problem, and
- functions to carry out various aspects of the problem, using this representation.
The purpose of this exercise is to develop some of the functions necessary
to create such a puzzle. Future exercises will build on this foundation, until
eventually the problem is solved.
The knowledge base for this problem consists of a m×n grid and a list of k words to be placed in the grid. The state s=(grid,words) will be a partially filled-in grid and a list of words that still need to be added to the grid.
A rule r can be characterized by the five attributes (i, row, col, dh, dv), and is defined by the following action and preconditions:
- Action: Insert word[i] in grid, starting at position [row,col] and continuing in direction [dh,dv], where -1<= dh,dv <= 1 and |dh|+|dv| >0
- Precondition: word does not extend beyond edge of grid
- Precondition: word does not conflict with existing words in grid
For instance, word[7]="heuristic" was placed in the top left corner of the grid, proceeding in the horizontal direction, by applying rule (7,0,0,1,0) and word[0]="admissible" was placed in the grid by applying rule (0,9,10,-1,-1).
|
Each of the words at the bottom appears once in the grid, either horizontally, vertically or diagonally, forward or backward.
Find each word and circle it.
| H |
E |
U |
R |
I |
S |
T |
I |
C |
S |
A |
L |
| A |
C |
L |
A |
B |
I |
N |
N |
A |
C |
E |
P |
| I |
K |
R |
B |
Y |
R |
T |
E |
M |
M |
Y |
S |
| A |
P |
C |
A |
I |
N |
E |
E |
A |
R |
I |
I |
| H |
C |
R |
A |
E |
S |
H |
P |
A |
R |
G |
L |
| U |
O |
E |
G |
R |
S |
S |
N |
M |
L |
D |
L |
| A |
P |
A |
R |
A |
T |
O |
I |
O |
Y |
N |
I |
| R |
T |
T |
H |
I |
I |
K |
B |
M |
U |
E |
H |
| T |
I |
A |
O |
S |
G |
A |
C |
D |
D |
D |
G |
| A |
M |
M |
S |
P |
L |
O |
C |
A |
L |
A |
I |
| S |
U |
I |
I |
L |
D |
I |
A |
A |
B |
E |
E |
| K |
M |
A |
I |
H |
A |
I |
T |
L |
R |
D |
G |
|
| Admissible |
Agent |
Backtrack |
| Cannibal |
Deadend |
Global |
| Graphsearch |
Heuristic |
Hill |
| LISP |
Local |
Missionary |
| Optimum |
Search |
Symmetry |
|
Puzzle produced by Armored Penguin
|
|
Using this representation, write the following statements and functions,
and test them using Python, showing your output.
- Assign an empty m×n grid and the full list of words {word[0],…, word[k-1]}
to initialState.
- Write a function goal(state) which returns true if state.words equals the empty list.
- Write
a function applyRule(rule,state) which returns the value of applying a rule to a given state. This does not change the value of state.
- Write
a function precondition(rule,state) which returns True if the given rule may be applied to state, that is, the preconditions are satisfied. For instance, given the value of initialState, the precondition for rule (7,0,0,1,0) is satisfied (and True is returned) because the word fits in the grid and there are no other words in the grid that conflict with it. Note, however that False is returned for the rule (7,0,8,1,0), because the word does not fit in the grid when starting at position [0,8] and filling forward in the positive direction. Likewise, suppose "heuristic" has been placed successfully with the first rule and the new state is state2. Then if rule2 is (0,9,10,-1,-1) , precondition(rule2,state2) returns True because the final letter 'e' overlaps with the letter 'e' in position [0,1]. However, the rule (0,9,11,-1,-1) would not satisfy the preconditions for this state because it does not overlap properly with existing words in the grid.
- Write a function generateRules(state) which calls precondition and returns a list of all possible rules that may be applied to the current state, where rules have the form described above. This should be a list of all possible words, starting positions and directions which satisfy the preconditions for the given state.
- Write a function describeState(state), which shows the partially filled in grid and lists words still remaining to be placed in the grid.
- Write a function describeRule(rule), which explains the meaning of the given rule, e.g.,
Place the word "admissible" in the grid starting at position (9,10) and proceeding in the direction [-1,-1].
- Test these primitives by writing a routine flailWildly(state), which repeatedly tests goal(state) and if a goal has not been reached, determines all applicable rules for the current state, chooses one randomly and applies it. At each step, describe the current state, describe each applicable rule, and describe which rule has been chosen.
|
|