Word Rectangle (ITA Archived Puzzle, Archived)

Please refer to the word rectangle problem on this page

Analysis

This is similar to a board game like Queens and Kinghts or Sudoku. Let us then define the rules of the board game called ’word rectangle’. They can be stated as:

• Each row of the board should form a valid word.
• Each column of the board should form a valid word.

As is typical with board games, we can first build a search tree and walk through this tree. As soon as we find the above rules or constraints violated, we can backtrack while discarding the rest of the search tree. This is a problem of constraint propogation and search with backtracking.

The better way to think of this problem is that while typically board games give you the size of the board, here we are supposed to find the size of the board. As such our search tree should contain the following:

• The words and their prefixes. The prefix is a constraint propogation heuristic to check if the constraints are violated, while filling the board. Obviously this turns out to be a suffix tree!
• The words sorted by length from maximum to minimum. Then we can do binary search to determine the words beginning with a given letter and of length l in this sorted list. In fact if you do an inorder traversal of the suffix tree, you will end up with the sorted words!

Thus our search tree is made up of a suffix tree and sorted list.

Algorithm

• Build the search tree as described in the previous section.
• Pick a word ’w’ of largest length from the search tree.
• Find out the largest possible length for each distinct letter of the ’w’.
• Pick the smallest length ’l’ from the lengths determined in previous step. THis is because, we will have words of the smallest length available for all letters of word ’w’.
• Now for each letter of the word ’w’, pick a word of length ’l’ beginning with that letter. Now check if the rules of the board are satisifed. The rules will be assumed to be satisfied if the word length is 1. A word length of 1 implies the row or column is yet to be filled. If the rules are violated, discared the chosen word and pick another word of length ’l’ for the letter in consideration. Repeat the process till the board is filled.
• That board’s row and column lengths are the maximum possible lengths.

---

word-rectangle-ita.pdf
File Size:	169 kb
File Type:	pdf

Download File

---

---