Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Computerized Generation of Crossword guzzles

IP.com Disclosure Number: IPCOM000128517D
Original Publication Date: 1974-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 7 page(s) / 27K

Publishing Venue

Software Patent Institute

Related People

Kurt Maly: AUTHOR [+4]

Abstract

In this paper we exploit the semblance of generating corssword puzzles and generating sentences of a language with a two-dimensional grar-r-ar. A tap-down algorithm for the solution is presented as a first step towards a general solution together with a discussion. of a new, supporting, data structure; the C-trie. Backtracking involves a critical reion analysis to eliminate redundant searches i=- C> the wordspace of the crossword puzzle. Due to a lack of a sufficiently large data base the resulting puzzles do not compare favorably to sophisticated puzzles containing themes and very long words. However, the puzzles we were able to generate are on. the legal o= those published in the averGFe daily ne;*rsp =p er` .. Keywords and Phrases: recreational problem solving, data structure, key search, retrieval time, crossword puzzle. CR categories: 3.42, 3.49, 3.64, 3.74, 3.75 This research was partially supported by a grant from the University of 'Mianesot Computer Center.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 18% of the total text.

Page 1 of 7

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Computerized Generation of Crossword guzzles

by

Kurt Maly and Kenneth Ng

Technical Report 74-29 December, 1974

Computer, Information, and Control Sciences Department Institute of Technology University of Minnesota Minneapolis, Minnesota 55455 Cover design courtesy of Ruth and Jay Leavitt Computerized Generation of Crossword Puzzles by Kurt Maly and Kenneth Ng^

Department of Computer and Information Sciences w University of Minnesota rLinneapolis, Minnesota 55455

Abstract

In this paper we exploit the semblance of generating corssword puzzles and generating sentences of a language with a two-dimensional grar-r-ar. A tap-down algorithm for the solution is presented as a first step towards a general solution together with a discussion. of a new, supporting, data structure; the C-trie. Backtracking involves a critical reion analysis to eliminate redundant searches i=- C> the wordspace of the crossword puzzle. Due to a lack of a sufficiently large data base the resulting puzzles do not compare favorably to sophisticated puzzles containing themes and very long words. However, the puzzles we were able to generate are on. the legal o= those published in the averGFe daily ne;*rsp =p er` ..

Keywords and Phrases: recreational problem solving, data structure, key search, retrieval time, crossword puzzle.

CR categories: 3.42, 3.49, 3.64, 3.74, 3.75

This research was partially supported by a grant from the University of 'Mianesot Computer Center.

Introduction

Artificial intelligence as a branch of computer science encompasses a wide variety of fields which range from natural language.comrlunications with computer, automatic pro ra=nning, heuristic problem solving to roboticss. In this paper ere -wish to address ourselves to a sorm~a'nat minor but, none the less, integral gars of artificial inte'l-igence, nausly, recreational problem solving. :*iore specifically, w8 pro-pose to computerize part of a century old past-time of man: creating and solving crossword puzzles. We do not propose to solve crossword puzzles by means of a computer; rather, we wish to broach the problem of creating a crossword puzzle which care be difficult and tedious indeed. Consider the pattern (i.e., distribution of black squares) of the puzzle in Figure 1; it would require a considerable degree of experience and literacy for a human to find words which fit the two-dimensional pattern. (For a computer generated solution see result section)

University of Minnesota Page 1 Dec 31, 1974

Page 2 of 7

Computerized Generation of Crossword guzzles

(Image Omitted: Figure 1: Pattern of 3 cross-word guzzle)

l

Before we continue, we challenge the reader to construct 'the crossword puzzle whose pattern is given in Figure 2. The solution of this t4sk will provide the reader with an estimate of the difficulties involved in theiconstruction of a puzzle such as.the one in Figure 1. !

(Image Omitted: Figure 2: A puzzle to be con...