However, this approach can be greatly improved if we can reduce the number of combinations that we have to try from the dictionary at each step. A naive approach for solving the crossword construction problem is to try all combinations of filling in the grid with potential answers from the dictionary. Our Solution Image of poster presented at NCUR 2021 (source )Īlthough the crossword construction problem is NP-complete, we think that heuristics can be used to solve the problem efficiently for small grid sizes and large dictionaries. In other words, we do not yet know if there are efficient algorithms that solve these problems in all cases.įor more information about the crossword construction problem and NP-completeness, we refer the reader to GP14 in Computers and Intractability: A Guide to the Theory of NP-Completeness by Michael Garey and David Johnson. From a practical point of view, NP-complete problems are widely considered to be computationally hard. NP-completeness is an important mathematical property in Computer Science.
In particular, the crossword construction problem is NP-complete. In general, crossword construction is considered to be a challenging computational problem. Generating clues is a separate and important problem that we have not yet pursued. This problem asks for a filling to a given crossword grid so that every horizontal and vertical answer is a valid word within a given dictionary.įor this problem, we do not generate the clues. Now, we can define the Crossword Construction Problem. Such restrictions can make the crosswords more dense with answers and more challenging to construct. For example, some publishers require crosswords to have 180-degree symmetry and for all answers to be at least 3 characters in length. There are many common restrictions that are applied to crosswords. The empty squares are meant to be filled in with alphabet characters to form horizontal and vertical answers that match the given clues. A crossword takes the form of a grid containing empty and shaded squares along with a list of clues. īefore, we discuss our web application, we need to tell you a bit more about crosswords and the concept of computational hardness.Īlso Read: Can AI Write the Dictionary? Does AI Know What Words Mean? CrosswordsĬrosswords are fun and educational word puzzles that are commonly found in newspapers, media, websites, and mobile apps. So with the support of Swarthmore College, we were able to pursue a research project to build a crossword construction web application at. The more we talked together about crosswords, the more convinced we were that we could build our own application for crossword construction. He was even working on constructing his own crossword puzzle too.
But then, I met a talented student named Otis Peterson who has been solving crosswords since he was a kid. Because I struggle with solving crosswords, I felt like constructing a crossword was an unobtainable goal for me. But, to be honest, I am not very good at solving crosswords.
0 kommentar(er)
