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.
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
Keywords and Phrases
Complexity; Crozzle; NP-hard
Article - Conference proceedings
© 2023 Association for Computing Machinery, All rights reserved.
18 Feb 1996