$29
Take Home Exam 3 Solution
PROBLEM
In THE-3, your task is to nd the placement of a subset-set W of N-letter words in a corpus C, on a grid of size N N such that the vertical readings (from top to bottom) and horizontal readings (from left to right) of letters are also words in C. For example, assume that C consists of the following seven words:
ALI, SIN, ASI, LIR, IRI, INI, KAR,
and the grid is 3 3 (note that each row and each column can hold only one word). One possible placement of these words on a grid of 3 3 is as follows:
column-1
column-2
column-3
row-1
A
L
I
row-2
S
I
N
row-3
I
R
I
In this placement, all the words that can be constructed from consecutive letters in a row and in a column are valid (they do not have to be meaningful) words in C. In other words, we made use of the words ALI (row-1), SIN (row-2), IRI (row-3), ASI (column-1), LIR (column-2), INI (column-3) which are members of the set C. Note that this placement did not make use of all the words in C; namely, KAR is not a part of the solution.
SPECIFICATIONS
You should write a function place_words(Corpus) which takes the corpus as a list of strings.
You can assume that all words in the corpus have the same size, and that this size is equal to N, the size of the grid (N can be di erent from 3). Moreover, there are no duplicate words in the corpus.
If there is a solution, your function should return it as a list of words such that the ith word in this list is the ith row in the grid.
If there is no solution, your program should just return False.
Words can only consist of letters from the English alphabet, and your solution should be case-insensitive; i.e., the two words CAN and Can should be treated as the same words.
Your solutions should be in uppercase no matter in which case the words in the corpus are.
We will not test your solution with erroneous input. However, we will test your program with words which may not have a valid placement on a grid!
Example Run
• Solution = place_words(["ALI", "SIN", "ASI", "LIR", "IRI", "INI", "KAR"])
• print Solution
["ALI", "SIN", "IRI"]
Notes
You cannot use any other method than backtracking (see Appendix for a quick intro). You are not allowed to import any function or module.
You may use recursion or iteration.
A word may appear only once in the grid (horizontally or vertically). Your function will be tested with multiple data.
Any program that performs below 30% of the total grade will enter a glass-box test (eye inspection by the grader TA). The TA will judge an overall grade in the range of [0,30].
The glass-box test grade is not open to negotiation, discussion or explanation.
Your function will be tested with Python interpreter (v2.7) that is installed on inek machines running Linux.
You are encouraged to share input-outputs on the news group of the course.
APPENDIX: INTRODUCTION TO BACKTRACKING
Backtracking is a widely-used method in Computer Science for nding a solution to a problem incrementally. The current (partial) solution is usually kept as an ordered set V = v1; ::; vN and at each step, a new partial-solution-element vi is added to V in such a way that the addition of vi to V takes us one step closer to the complete solution and that vi is not in con ict with V as far as the problem is concerned.
If V + vi is invalid, another element, if there is any, is placed in the position of vi. If no v can be found that would make V + v valid, the algorithm backtracks; in other words, it goes back to the previous step and tries another element v; in our scenario, this would mean removing vLAST and placing some other v in vLAST ’s place that would not invalidate V .
The process of (i) adding a valid new partial solution, and (ii) backtracking to nd a valid new partial solution is repeated until a solution is found or all the possible options are exhausted, which means that no valid solution exists for the problem.
A good example of backtracking is the n-queens problem; i.e., the placement of n queens on a n n-chessboard. We will illustrate backtracking on the 4-queens problem (Figure 1).
a b c d
1
2
3
4
Figure 1: 4-queens problem.
The backtracking-solution to the 4-queens problem is described in Algorithm 1. Note that the solu-tion in Algorithm 1 presents just the backbone of the solution, and the functions get_next_empty_row(), get_next_queen(), backtrack() and is_valid() need to be lled in. Another important point is that you
Algorithm 1 Pseudo code for the solution to 4-queens problem.
Set V to fg
while True do
q = get_next_queen()
if q is INVALID then
/* WE FINISHED ALL QUEENS => SOLUTION FOUND */ Return V as solution and exit
end if
(row, column) = get_next_empty_row()
/* ‘‘Empty row’’ means no queen is at (row, X) nor at (Y, column) for any X,Y nor in a diagonal with another queen */
if row == INVALID or column == INVALID then /* No valid & empty (row, column) */
backtrack() /* If there is no option to backtrack to, return NO-SOLUTION */ else
Set V = V + fq at (row, column)g
end if
end while
need to keep a track of the solutions that have been tried for each row, and when you backtrack from a row, you need to erase the options that have been tried for that row.
The backtracking solution to the 4-queens problem is displayed step-by-step in Figure 2.
a b c d
a b c d
a b c d
a b c d
a b c d
1
1
1
1
1
2
2
2
2
Backtrack
2
3
3
3
3
3
4
4
4
4
4
V={}
V = {(q1 at a1)}
V = {(q1 at a1), (q2 at c2)}
V = {(q1 at a1), (q2 at c2)}
V = {(q1 at a1)}
a b c d
a b c d
a b c d
a b c d
a b c d
1
1
1
1
1
2
2
2
Backtrack
2
Backtrack
2
3
3
3
3
3
4
4
4
4
4
V = {(q1 at a1), (q2 at d2)}
V = {(q1 at a1), (q2 at d2)
V = {(q1 at a1), (q2 at d2)
V = {(q1 at a1), (q2 at d2)}
V = {(q1 at a1)}
(q3 at b3)}
(q3 at b3)}
a b c d
a b c d
a b c d
a b c d
a b c d
1
1
1
1
1
Backtrack
2
2
2
2
2
3
3
3
3
3
4
4
4
4
4
V={}
V = {(q1 at b1)}
V = {(q1 at b1), (q2 at d2)}
V = {(q1 at b1), (q2 at d2)
V = {(q1 at b1), (q2 at d2)
(q3 at a3)}
(q3 at a3), (q4 at c3)}
SOLUTION!
Figure 2: Step-by-step solution to the 4-queens problem.
