Hodgepodge

Introduction

There are several types (formats) for crossword puzzles. Below shows what I will call "type A" and "Type B".

Type A

Image From: commons.wikimedia.org

Type B

Image From: commons.wikimedia.org

Project #1a

Create a "Type B" crossword puzzle using the pseudo code below. (Be sure to click on the link and read the information there first. This will help define the problem.)

Here is a list of words you can use for testing. (It is the first line of Shakespeare's play Richard III.) You should also develop your own test lists.

words = [ 'Now', 'is', 'the', 'winter', 'of', 'our', 'discontent',
'Made', 'glorious', 'summer', 'by', 'this', ',sun', 'of', 'York' ]

Note: Treat uppercase and lowercase letters the same.

Algorithm

Pseudo code from: Generating a Crossword Puzzle

algorithm IterativePlacement(words, maxWords): // INPUT // words = list of words to place on the crossword // maxWords = the maximum number of words to place // OUTPUT // crossword = the generated crossword grid shuffle(words) word <- pop(words) crossword <- place(word, null, 0, 0, HORIZONTAL) count <- 1 while count < maxWords and len(words) > 0: word <- pop(words) for letter in word: for y in rows(crossword): for x in cols(crossword): if crossword[y, x] = letter: placement, ok <- canPlace(word, crossword, x, y) if ok: crossword <- place(word, crossword, placement.x, placement.y, placement.direction) count <- count + 1 continue return crossword

Design Questions/Thoughts:

Coordinate 0,0 is the center of the grid/matrix, Not the upper-left corner?

Is it best to use an odd number of columns and rows? (This fits nicely with the idea that 0,0 coordinates being in the center.)

Project #1b

After creating a crossword, display it as a "Type B" (shown above).

Links

Algorithm to generate a crossword

algorithms/docs/crossword-puzzle.md

Generating a Crossword Puzzle

How we developed a scalable, incredibly fast crossword generator