Crossword algorithm ?

[dobrzan]

Any idea for algorithm that as parameters get dimension of
crossword (width and height) and dictionary file.
The result should be a file with crossword.
The crossword should have fewest empty squares.

Only idea I have was to write recurency algorithm put word,
then try next until no more words can fit into crossword.
Check the number of empty squares, and save that crossword if
it is the best.

If anyone have any idea about other solutions or some simplification of recurency search please write.

[j0nas]

You can always convert recursive algorithms to iterative.

I don't know how to write a crossword generator.

After some searching on www.google.com, I found out that solvning or generating (is there a difference?) crosswords is a NP-complete problem. This is an extract from below link:

Number: 55
Name: Crossword Puzzle Construction [GP14] 5

Input: A finite set of characters SIGMA={sigma1,...,sigmak}; a finite set, W={w1,...,w2n} each wi being a sequence of n characters from SIGMA, i.e. a string.

Question: Can an n by n crossword puzzle be built using all of the 2n words (strings) in W, i.e. if C is an n by n table of `blanks', is there an assignment, f, that maps each entry (i,j) of C to some character in SIGMA in such a way that the word formed by taking the n consecutive characters in a row corresponds to a word in W; the word formed by taking the n consecutive characters in a column (reading from top-to-bottom) corresponds to a word in W?

Comments: The definition may look complicated but it isn't. Here is a simple example instance for which a crossword can be constructed. Let SIGMA={A,B,C,D,E,G,O}, n=3, and W={AGE,AGO,BEG,CAB,CAD,DOG}. A 3 by 3 crossword puzzle for this is given by the assignment C(1,1)=C; C(1,2)=A; C(1,3)=B; C(2,1)=A; C(2,2)=G; C(2,3)=E; C(3,1)=D; C(3,2)=O; C(3,3)=G. This results in the grid


CAB
AGE
DOG

whose correctness is self-evident.

Ref: http://www.csc.liv.ac.uk/~ped/teachadmin/COMP202/annotated_np.html

[Jon_Kinsey]

Here's a hint, type "Crossword algorithm" into google...

Here's the first hit...

http://www.cs.auc.dk/~larsch/cwc/

Looks like a crossword algorithm :)

[kfuntak]

Here You can see advanced powerful crossword algorithm performance. Test it with English database with 700.000 words.


Professional Crossword Software project is started.

Professional Crossword Software Official Site:
www.professionalcrosswordsoftware.com

Professional Crossword Generator
Professional Crossword Publisher
Professional Crossword Solver

Professional Crossword Generator preview version 1.0 is available for free download.

[GCDEF]

What's with noobs and old threads.:rolleyes:

Note to noobs. After six years, I doubt the OP is still looking.