Results 1 to 4 of 4

Math Help - Puzzle Solving using Integer Programming

  1. #1
    Junior Member
    Joined
    Sep 2008
    From
    Boston, Massachusetts
    Posts
    41

    Puzzle Solving using Integer Programming

    Hello,
    A double word square is a square of letters where every row and column can be read as a word. A 3 * 3 word square would be:

    \begin{matrix} T&O&O\\ U&R&N \\ B&E&E \end{matrix}

    Given the following list of words, formulate an integer programming problem whose feasible solutions would be a 4*4 word square. Each word can only be used once.
    Word list:
    Area,Bake,Core,Cork,Icon,Iron,Knee,Lace,Lack,Lake, Limb,Lime,Lock,Make,Mere,More.

    These words are made up of four of the following letters:
    A,B,C,E,I,K,L,M,N,O,R
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,908
    Thanks
    766
    Hello, funnyinga!

    I found a solution using Common Sense . . .


    A double word square is a square of letters where every row and column is a word.

    A 3x3 word square would be: . \begin{matrix} T&O&O\\ U&R&N \\ B&E&E \end{matrix}

    Given the following list of words, find a 4x4 word square.
    Each word can only be used once.

    Word list: . \begin{array}{cccc}\text{AREA} & \text{BAKE} & \text{CORE} & \text{CORK} \\ \text{ICON} & \text{IRON} & \text{KNEE} & \text{LACE} \\ \text{LACK} & \text{LAKE} & \text{LIMB} & \text{LIME} \\ \text{LOCK} & \text{MAKE} & \text{MERE} & \text{MORE.} \end{array}
    Consider what word can be in the top row.


    Can AREA occupy the first row (or first column)?

    . . \begin{array}{|c|c|c|c|} \hline<br />
A & R & E & A \\ \hline<br />
* & * & * & * \\ \hline<br />
* & * & * & * \\ \hline<br />
* & * & * & *  \\ \hline\end{array}

    If AREA is in the first row, there must be: two more words starting with A,
    . . one word starting with R, one word starting with E.

    Since none of these is on the Word List, AREA is not the first word.

    In a similar fashion, we can eliminate all words except LACK and LIMB.


    So one solution would start like this:

    . . \begin{array}{|c|c|c|c|} \hline<br />
L & A & C & K \\  \hline I & * & * & * \\ \hline M & * & * & * \\ \hline B & * & * & * \\ \hline \end{array}


    The second column must be AREA.
    The fourth column must be KNEE.
    The fourth row must be BAKE.

    . . \begin{array}{|c|c|c|c|} \hline<br />
L & A & C & K \\  \hline I & R & * & N \\ \hline M & E & * & E \\ \hline B & A & * & E \\ \hline \end{array}


    Hence, the second row is IRON, the third row is MERE, the fourth row is BAKE.
    . . And the third column is CORK.



    Two solutions: . \begin{array}{|c|c|c|c|} \hline<br />
L & A & C & K \\  \hline I & R & O & N \\ \hline M & E & R & E \\ \hline B & A & K & E \\ \hline \end{array} . and . \begin{array}{|c|c|c|c|} \hline<br />
L & I & M & B \\  \hline A & R & E & A \\ \hline C & O & R & K \\ \hline K & N & E & E \\ \hline \end{array}

    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Sep 2008
    From
    Boston, Massachusetts
    Posts
    41
    Hi Soroban,
    Thanks, but I have been able to figure out a solution in the same manner. I am actually after a way to model this mathematically.
    Here is what I am working with:
    We require a compound variable that will be called "Placement". A "placement" represents adding a word to the 4*4 square in a certain way - using different grids of the square.
    The important information we need for each word placement is the word used, the grids covered, and the letters used by the word used.
    We start by numbering the grids from top left through to bottom right as grid 0 to grid 16, and number the words as:
    AREA - 0
    BAKE - 1
    CORE - 2
    CORK - 3
    ICON - 4
    IRON - 5
    KNEE - 6
    LACE - 7
    LACK - 8
    LAKE - 9
    LIMB - 10
    LIME - 11
    LOCK - 12
    MAKE - 13
    MERE - 14
    MORE - 15

    and the letters as
    A - 0
    B- 1
    C - 2
    E - 3
    I - 4
    K -5
    L - 6
    M - 7
    N - 8
    O - 9
    R - 10

    Then (using your example) we could use word 8 (LACK) to cover grids 0, 1, 2, & 3. In all each word has a possible 8 placements.
    Now
    Denote M as the set of placements.

    Let uw_m be the word used by placement m \in M.

    Let S_m be the set of grids covered by placement m, and we introduce variable x_m which are 1 if placement m is used, 0 otherwise.

    Then I'm trying to find a solution to the following constraints (that I'm not sure of):

    \sum_{m \in M , uw_m = w} x_m = 1 \ \forall \ w \in \{0,1,2,..., 15 \} (ensure that each word is used once)

    and

    \sum_{m \in M , s \ \in \ S_m} x_m = 1 \ \forall \ s \in \{0,1,2,..., 15 \}

    and x_m \ \in \ \{ 0 , 1 \} \ \forall \ m \ \in \ M.

    Im not sure of these constraints, and I don't yet have the constraint to ensure that the words van be read vertically as well as horizontally.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by funnyinga View Post
    Hi Soroban,
    Thanks, but I have been able to figure out a solution in the same manner. I am actually after a way to model this mathematically.

    ...
    I would think that once you have a candidate grid, checking that it meets the requirements is pretty easy; it's constructing the grid that requires more thought.

    But regarding verifying a candidate grid: you can have a function isGood() which returns true or false. A boolean array is fine for checking that no word is used more than once. After each word you check, look at the array for the appropriate index, and if it's true then you've already used the word, so return false. Else set that index to true. The problem statement doesn't say that every word has to be used once, just that no word is used more than once. Of course you can't use words not in the list. For list L = {Area, Bake, Core, Cork, Icon, Iron, Knee, Lace, Lack, Lake, Limb, Lime, Lock, Make, Mere, More}, check each of the 8 positions in turn, and if you see that the four-letter entry is not in your list, you return false. And of course you can check each letter separately and make sure there are no illegal letters. Another way to do this is simply to update your list at the beginning by removing any words that contain illegal letters. You can formalise everything with set notation, but if you have a working program then the code pretty much speaks for itself.

    As for constructing the grid, I would definitely program the logic in Soroban's post into the code, and then you can use backtracking for when there is more than one possible move. If you're not familiar with backtracking, it's basically using recursion to try all possible moves from a given state, and then whenever you come upon an impossible situation, use a return command to stop that path, and you will be left only with correct paths, if any exist.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Binary Integer Programming Problem
    Posted in the Advanced Applied Math Forum
    Replies: 0
    Last Post: August 14th 2011, 04:57 PM
  2. Integer Programming Problem
    Posted in the Advanced Applied Math Forum
    Replies: 0
    Last Post: April 26th 2010, 08:22 PM
  3. Integer Programming
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: March 10th 2010, 07:56 PM
  4. Integer puzzle
    Posted in the Math Challenge Problems Forum
    Replies: 2
    Last Post: November 14th 2009, 01:47 PM
  5. Integer programming
    Posted in the Business Math Forum
    Replies: 0
    Last Post: April 28th 2008, 07:18 PM

Search Tags


/mathhelpforum @mathhelpforum