Abstract | ||
---|---|---|
The crossword puzzle is a classic pastime that is well-known all over the world. We consider the crossword manufacturing process in more detail, investigating a two-step approach, first generating a mask, which is an empty crossword puzzle skeleton, and then filling the mask with words from a given dictionary to obtain a valid crossword. We show that the whole manufacturing process is NP-complete, and in particular also the second step of the two-step manufacturing, thus reproving in part a result of Lewis and Papadimitriou mentioned in Garey and Johnson's monograph [M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, 1979.] but now under real world crossword puzzle conditions. Moreover, we show how to generate high-quality masks via a memetic algorithm, which is used and tested in an industrial manufacturing environment, leading to very good results. |
Year | DOI | Venue |
---|---|---|
2012 | 10.1007/978-3-642-30347-0_15 | FUN |
Keywords | Field | DocType |
rationalized crossword puzzle manufacturing,real world crossword puzzle,empty crossword puzzle skeleton,industrial manufacturing environment,whole manufacturing process,high-quality mask,two-step manufacturing,crossword puzzle,s. johnson,valid crossword,crossword manufacturing process | Memetic algorithm,Manufacturing,Computer science,Artificial intelligence,Genetic algorithm,Manufacturing process | Conference |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Jakob Engel | 1 | 906 | 30.16 |
Markus Holzer | 2 | 27 | 6.73 |
Oliver Ruepp | 3 | 13 | 3.11 |
Frank Sehnke | 4 | 527 | 39.18 |