Thread: 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:



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

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: .

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

Word list: .

Consider what word can be in the top row.


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

. .

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:

. .


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

. .


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



Two solutions: . . and .

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 as the set of placements.

Let be the word used by placement .

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

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

(ensure that each word is used once)

and



and .

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.

Originally Posted by funnyinga

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.