Abstract
In an Australian Magazine, a Monetary Prize is Awarded to the Person with the Best Answer to a Word Puzzle Called a Crozzle. the Placement of Words into a Ten by Fifteen Grid Obtaining the Highest Score is the Best Answer. Various Search Techniques Have Been Employed to Solve This Problem, Yet No One Has Shown Whether There is a Polynomial-Time Algorithm to Find the Best Crozzle. This Paper Creates a Similar Word Puzzle, Called R-By-C Crozzle, by Lifting the Constraint on the Grid Size. R-By-C Crozzle is Not in NP, But There Exists a Polynomial Reduction to It from the Exact 3-Set Cover Problem. Thus the R-By-C Crozzle is NP-Hard. This Paper Also Explores Any Implications that the Complexity of the R-By-C Crozzle Might Have on the Complexity of the Original Problem.
Recommended Citation
M. Gower and R. W. Wilkerson, "R-By-C Crozzle: An NP-Hard Problem," Proceedings of the ACM Symposium on Applied Computing, pp. 73 - 76, Association for Computing Machinery, Feb 1996.
The definitive version is available at https://doi.org/10.1145/331119.331148
Department(s)
Computer Science
Keywords and Phrases
Complexity; Crozzle; NP-hard
Document Type
Article - Conference proceedings
Document Version
Citation
File Type
text
Language(s)
English
Rights
© 2023 Association for Computing Machinery, All rights reserved.
Publication Date
18 Feb 1996
