How to get multiple solutions for a crossword?

Question

I have already seen the forums and different questions on this.

But i want to ask something different. I have two wordlist of different words and one grid specified by 0 and 1. i will have to select word from wordlist 1 for rows and 2 for columns.

The main problem is i have to find multiple solution within given time constraint. Can someone suggest me some good algorithm for that. I am not getting what kind of algorithmic approach should i take.

Another thing, I have two language options. Either c++ or java which would be better to implement.

thank you

Answer 1

You may be able to use something called the Dancing Links or DLX algorithm. This is an extremely efficient algorithm for solving exact cover problems.

There are several programs out there that use this to solve Sudoku puzzles.

• http://www.ocf.berkeley.edu/~jchu/publicportal/sudoku/sudoku.paper.html

I honestly don't know enough about exact cover problems to say that this will definitely work for your needs but it's worth taking a look.

Answer 2

When doing a crossword, one usually finds oneself looking for a word of a certain length, with a certain letter at a certain position in it. So, you're probably going to want a function like this:

List<String> findWord(int ofLength, char withLetter, int atIndex) {/*implementation*/}

Which could probably use a set of pre-built HashMaps to produce a set of candidates quickly. (You'll probably also want to be able to track whether the word is currently used already in the crossword...assuming duplicates aren't allowed)

The other thing people do is guess using hints. I figure you're probably not looking for strong AI, so that leaves brute force algorithms...in which case, try to fill in the crossword starting with the biggest words first, since there are generally fewer possibilities there.

Skeleton algorithm:

private void checkPuzzleOn(Row row, SolutionSet s) {

    List<Row> crossingRows = row.getCrossingRows();

    if(allAlreadyFilled(crossingRows)) {
        //This part of the crossword works; store info in solution set.
        return;
    }

    crossingRows.sortBiggestToSmallest();

    foreach(Row crossing in crossingRows) {

        int index = row.getIndexOfIntersectionWith(crossing);
        char c = row.charAt(index);

        List<String> candidates = findWords(crossing.length, c, index);
        foreach(String candidate in candidates) {
            verifyAgainstPresentWords(crossing, candidate); //check that using this word won't collide with others; important because of cycles.
        }

        if(candidates.isEmpty()) {
            //This part of the crossword won't match! store info in solution set.
            return;
        }

        foreach(String candidate in candidates) {
            crossing.setWord(candidate);
            checkPuzzleOn(crossing, s);
        }
    }
}

Answer 3

I found a solution that does what you want. Sadly I can't take credit for it :)

Here is an example. You feed it a pattern file, like pattern1:

    ##   ##    
    #     #    
    #     #    
           #   
###   ###    ##
#      #      #
   #     #     
    #     #    
     #     #   
#      #      #
##    ###   ###
   #           
    #     #    
    #     #    
    ##   ##    

You invoke the program on it, like e.g. so:

./cword pattern1 /etc/dictionaries-common/words

The output is

SODS##HOG##AMPS
APIA#RADON#LAUE
TESS#ALONE#ERNA
ENCHANTRESS#GYM
###ADS###TUTU##
#PAYDAY#ESPIES#
REV#SCALD#SCRIP
ARON#KNOWS#SITE
MCCOY#KNITS#TET
#HARASS#NAPPED#
##TACT###DIE###
MCI#COORDINATES
ELOY#AMARU#ROLL
SINE#TARIM#LIMA
SOSA##REP##SLOT

Or, run another time:

PAWN##HOT##BEST
OLEO#SURYA#OMAR
LOAN#AGAPE#ABLE
SELFISHNESS#RTE
###ASH###OKAY##
#KATMAI#EPILOG#
INN#SYNOD#MULES
SETH#SCHWA#MONA
MEIER#AMIDS#GEM
#SPLATS#NOWAYS#
##APSE###RAY###
WIS#PATRONYMICS
ALTA#CHOKE#AREA
SLOP#HEARD#ROBS
PSST##ERA##ANUS

Of course, with larger patterns or smaller wordlists your mileage may vary (wildly). I was able to do 1000 generations in 26.5 seconds on a Q9550 processor, using

time for a in $(seq 1 200)
do 
    for a in 1 2 3 4 5
    do 
        ./cword pattern1 /etc/dictionaries-common/words | md5sum&
    done
    wait
done | sort | uniq -c | sort -n | tee >(wc -l)

The output confirmed that these were in fact 1000 unique solutions. Not bad, if you ask me. (The timing included the time to calculate the md5sums per solution)