R-By-C Crozzle: An NP-Hard Problem

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.