DEEPAK.SURTI
  • Home
  • Blog
  • Mobile Apps
  • Open Source
  • Cool 3D Demos
  • About

Word Rectangle (ITA Archived Puzzle, Archived)

9/28/2011

0 Comments

 
Picture
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


0 Comments

Your comment will be posted after it is approved.


Leave a Reply.

    Picture

    Me

    I am a 3D graphics software engineer.

    profile for dmsurti at Stack Overflow, Q&A for professional and enthusiast programmers

    Archives

    December 2011
    November 2011
    October 2011
    September 2011
    August 2011
    July 2011
    June 2011
    May 2011
    April 2011
    August 2010
    January 2010
    December 2009
    September 2009
    August 2009

    Categories

    All
    Automator
    Books
    Code
    Continuations
    Css
    Drakma
    Education
    Express Card
    External Drive
    Html
    Ita
    Learning
    Life
    Lisp
    Mac
    Macros
    Mercurial
    Productivity
    Puzzle
    Reading
    Rss
    Simplicity
    Sudoku
    Work

    RSS Feed

    Picture
    me @ delicious
Powered by Create your own unique website with customizable templates.
  • Home
  • Blog
  • Mobile Apps
  • Open Source
  • Cool 3D Demos
  • About