Abstract

In an Auslralian magazine, a monetary prize is awarded to the person with the best answer to a word puzzle called a Crozzle. Each valid placement of given words into a 10x 15 grid is given a score, and the best answer is the placement with the largest score. Various search techniques have been utilized lo solve this problem. No one has shown whether there is a polynomial-time algorithm to find the best Crozzle. This paper proves that the Crozzle is in NP. It also 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. This paper also explores any implications that the complexity of the R-by-C Crozzlc might have on the complexity of the Crozzle.

Department(s)

Computer Science

Comments

The first Author is a Graduuate Student

This report is substantially the M.S. thesis of the first author, completed Winter 1994.

Report Number

CSc-94-16

Document Type

Technical Report

Document Version

Final Version

File Type

text

Language(s)

English

Rights

© 1994 University of Missouri - Rolla, All rights reserved

Publication Date

1 November, 1994

Download

Share

 
COinS