Algorithm for crossword puzzle with given grid [closed]

Asked 21/12, 2011 at 4:29 Answered 21/12, 2011 at 21:26

Before I write something about the problem, I need to let you know:

This problem is my homework (I had about 1 week to return working program)
I was working on this problem for about a week, every day, trying to figure out my own solution
I'm not asking for complete program; I need a general idea about the algorithm

Problem:

Given: a wordlist and a "grid", for example:

grid (X means any letter):

X X 
XXXX
X X
XXXX

wordlist:

ccaa
baca
baaa
bbbb

You have to find example "solution" - is it possible to fit words from wordlist into a given grid? If there is at least one solution, print one (whichever correct). If no - print message, that there is no possible solution. For given example, there is a solution:

b c 
baca
b a 
baaa

It's hard for me to write everything that I've already tried (because English is not my native language and I also have a lot of papers with wrong ideas).

My naive algorithm works something like this:

First word needs just proper length, so find any (first?) word with proper length (I'm going to use given example grid and wordlist to demonstrate what I think):
```
c X 
cXXX
a X
aXXX
```
For first common letter (on the crossing of 2 words) find any (first) word, that fit the grid (so, have proper length and common letter on proper position). If there is no such words, go back to (1) and take another first word. In the orginal example there is no word which starts with "c", so we go back to (1) and select next words (this step repeats few times until we have "bbbb" for 1st word). Now we have:
```
b X 
bXXX
b X
bXXX
```
And we're looking for a word(s) which starts with "b", for example:
```
b X 
baca
b X
bXXX
```
General process: try to find pairs of words which fit to the given grid. If there is no such words, go back to previous step and use another combination - if there is no such - there is no solution.

Everything above is chaotic, I hope that you understand at least problem description. I wrote a draft of an algorithm, but I'm not sure if that works and how to properly code this (in my case: c++). Moreover, there are cases (even in example above) that we need to find a word that depends on 2 or more other words.

Maybe I just can't see something obvious, maybe I'm too stupid, maybe... Well, I really tried to solve this problem. I don't know English well enough to precisely describe what I think about this problem, so I can't put here all my notes (I tried to describe one idea and it was hard). Believe or not, I've spend many long hours trying to figure out solution and I have almost nothing...

If you can describe a solution, or give a hint how to solve this problem, I would really appreciate this.

Dorree answered 21/12, 2011 at 4:29 Comment(9)

Are the Xs in the grid the same characters? i.e. if X is 'a' then all X must be 'a'? – Strephon 21/12, 2011 at 4:44

No, 'X' means any letter, it's there to show how grid ("template") of a crossword looks. And these characters don't need to be the same. – Dorree 21/12, 2011 at 4:57

Can you add a case where there isn't solution? – Strephon 21/12, 2011 at 4:58

same grid, but instead "bbbb" there is "bbba". (edit: I won't be able to answer other questions for next ~7h) – Dorree 21/12, 2011 at 5:5

Ok, if I can figure out a solution I'll post it here! – Strephon 21/12, 2011 at 5:9

Think of words as arrays of characters. Once you have the correct length, you should be able to scan each array for matching characters at specific indexes (for example): pos 2 must equal 'b' and pos 4 must equal 'a'. – Merchant 21/12, 2011 at 5:21

@Steve Wellens: that was obvious for me, arrays are here a lot more useful than for example lists in this case. But still, I have no idea about the general algorithm. – Dorree 21/12, 2011 at 5:59

Why you say with "bbba" there is no solution? Is not possible to write the word from bottom to top? And from left to right? – Strephon 21/12, 2011 at 6:4

First create an array of chars with the matching pattern (example): 0-0-'b'-0-'a' Once you have this, iterate your subset of potential words. Check each word against the pattern. The internal loop will check each character, skipping the character when the pattern's character is 0. When the word matches, add it to a results list. – Merchant 21/12, 2011 at 14:27

The corssword problem is NP-Complete, so your best shot is brute force: just try all possibilities, and stop when a possibility is a valid. Return failure when you exhausted all possible solutions.

reduction that prove that this problem is NP-Complete can be found in this article section 3.3

Brute force solution using backtracking could be: [pseudo code]:

solve(words,grid):
   if words is empty:
       if grid.isValudSol():
          return grid
       else:
          return None
   for each word in words:
       possibleSol <- grid.fillFirst(word)
       ret <- solve(words\{word},possibleSol)
       if (ret != None):
          return ret
   return None

in here we assume fillFirst() is a function that fills the first space which was not already filled [first can actually be any consistent ordering of the empty spaces, but it should be consistent!] , and isValid() is returning a boolean indicating if the given grid is a valid solution.

Antiseptic answered 21/12, 2011 at 6:54 Comment(4)

What if function fillFirst won't find any possible solution? What will be the value of possibleSol? Can you give more specific example? I'm not sure if I understand your algorithm. – Dorree 21/12, 2011 at 13:46

if fillFirst() cannot do anything, it leaves the puzzle as is... The algorithm is quite simple: it just tries all possible solutions for the puzzle, and returns a valid solution if it encounters one. – Antiseptic 21/12, 2011 at 14:13

can you give example of fillFirst() in some language (c++, java)? I understand the concept of this function, but I don't know how to implement it. I represent grid as a 2D array with 1 (when there is a place for letter) and 0 (when it should be a empty space). How should I find out if I can fit a word into a given grid (which can be already partialy filled)? – Dorree 21/12, 2011 at 14:51

I've found my notes and at one point I had really similar idea, but just didn't add 2 lines. Anyway, I understand your solution, thank's for help. – Dorree 22/12, 2011 at 14:23

I wrote a progam this morning. Here is a slightly more efficient version in pseudocode:

#pseudo-code
solve ( words , grid ) : solve ( words , grid , None ) 

solve ( words , grid , filledPositions ) :
    if words is empty :
        if grid is solved :
            return grid
        else :
            raise ( no solution )
    for ( current position ) as the first possible word position in grid 
            that is not of filledPositions :
        # note : a word position must have no letters before the word
            # 'before the word' means, eg, to the left of a horizontal word
            # no letters may be placed over a ' ' 
            # no letters may be placed off the grid
        # note : a location may have two 'positions' : one across , one down
        for each word in words :
            make a copy of grid
            try :
                fill grid copy, with the current word, at the current position
            except ( cannot fill position ) :
                break
            try :
                return solve ( words\{word} , grid copy , 
                        filledPositions+{current position} )
            except ( no solution ) :
                break
        raise ( no solution )

Here is my code for fitting a word horizontally in the grid : http://codepad.org/4UXoLcjR

Here are some things I used from the STL:

http://www.cplusplus.com/reference/algorithm/remove_copy/

http://www.cplusplus.com/reference/stl/vector/

Chrysoprase answered 21/12, 2011 at 21:26 Comment(0)

Recommended topics

Hot tags