Building a Crossword Puzzle Generator with JavaScript

It’s time once again for aJavaScript tutorial. This will be the most complex code I’ve introduced to date, so I hope you’ve been paying attention and not just copy and pasting! In this post you will learn how to build a crossword puzzle generator with JavaScript.

First I’ll give an introduction into what inspired this project, next I’ll discuss what the different components are and how they fit together, and finally I’ll talk about the performance optimizations I made.

You can try it out by clicking this link. Be patient after clicking the button though, as sometimes it takes a moment to create a crossword puzzle. You’ll see why soon enough.

And you can click here to check out the source code.

A Word of Encouragement

I’ve been programming for many years now and have made lots ofmistakesalong the way. I like to think of myself as somebody who knows a thing or two about building software. There is an enormous number of things I don’t know, but I’m confident in my skill set and my ability to learn new concepts and technologies as needed.

However, I didn’t get that confidence overnight. I used to be pretty bad, and when I get the chance to look at some of my code from years back it makes me cringe at the silly things I did.

So if that’s you right now don’t feel bad! We all have to start from the beginning to become good at anything worthwhile.

The Source of Inspiration

And this brings me to a little a story. I created this crossword puzzle generator by porting an oldJava program I wrote back when I first got out of college. I hadn’t looked at it in years, and let me tell you, it was pretty rough. You can check it out on GitHub if you want to laugh at me.

I began the porting process by going one Java method at a time. I replaced each one with a shiny new JavaScript function that replicated its logic. As I progressed I began to refactor it, fix bugs, and improve the performance.

The Fruits of My Labor

The finished product isn’t perfectly clean code, but it’s a whole lot better than it was before.

After finishing the JavaScript version of my crossword puzzle generator I began wondering to myself if it’s worth writing a tutorial for. I’m 100% certain there are betteralgorithmsthan the one I used, and I’m also 100% certain there are more readability and efficiency improvements I could make. I don’t want to teach you guys any bad habits.

It’s also very complex and not the easiest material to teach.

In the end I decided it would be a good idea. So many tutorials out there are really trivial, and don’t give you a good sense of what a typical company code base looks like. This will give you a better approximation of that. It’s a collaboration of multiple developers with varying ability levels on a fairly complex problem over many years. It just so happens that both of the developers are me. :joy:

It will also give you an opportunity add your own improvements, which is key to growing as a developer.

What Exactly Are We Building?

We are building a crossword puzzle generator with JavaScript, HTML, and CSS . The idea is to take a big list of words, pick some random ones, and try to make a crossword puzzle out of them.

We’ll start by placing a word on a grid. Then we’ll get another word that is a possible candidate to connect to that word. Then we’ll do the same for another word. We’ll continue this process on an on, picking a different word each time the a word is placed or doesn’t fit anywhere in the puzzle.

When do we stop trying to place words? That’s a complicated answer determined by two main factors:

• Have we already placed a bunch of words?
• Do we have a lot of word intersections?

Once a crossword puzzle is made, we’ll go ahead and create some more. Then we’ll find the one with the most word intersections and show it on the screen!

Breaking Down The Problem

I won’t go into the weeds as much in this post as I do in some of myprevious tutorials. There are just too many functions and edge cases to go through. Instead, I think it will be most helpful if I explain in detail the high-level components we will be creating. Knowing how all the pieces fit together is half the battle.

I really encourage you to study what each function is accomplishing while keeping in mind which variables are being changed. The comment section is a great way to reach out for help if you don’t understand something. Others will probably thank you for it.

The Big List of Words

The first thing we need is a big list of words to pick from.

In my original version I pulled the King James Bible in from a text file.

In the updated version I just made a JavaScript array with a bunch of words in it. You can check it out here .

Representing a Word

To place a word on the grid we’ll need to know a few things about it. Obviously we’ll need to know the text of the word itself, but we’ll also need to know about it’s positioning. We’ll need a row and a column to mark it’s starting position. We’ll also need a boolean value to represent whether the word is horizontal or vertical in orientation.

We’ll represent words using a word object we create ourselves. You can check it out here .

Representing the Crossword Puzzle

The crossword puzzle objects we’re creating arerepresentationsof fully completed crossword puzzles. Each one will have various functions serving different purposes. Here is the comprehensive list of each function and what it does:

• update : Try to add a word to the grid.
• canBePlaced : Check if a word can be added to the grid.
• getIntersections : Returns a count of the number of word intersections in the grid.
• placementLegal : Determines if a word can legally be placed at a specific row/column position.
• invadingTerritory : Determines if a word will invade another word’s territory at a certain position.
• endOfWord : Determines if a particular row/column position corresponds to the end of the word.
• doesCharacterExist : Determines if a character exists at a certain position.
• overwritingHorizontalWord : Determines if placing a character at a particular row/column would be overwriting a horizontal word.
• overwritingVerticalWord : Determines if placing a character at a particular row/column would be overwriting a vertical word
• isInterference : Checks for interference at a set of row/column positions.
• isLetter : Checks if there is a letter at a row/column position.
• isEmptyCell : Checks if a row/column position is empty.
• addWord : Adds a word to the grid.
• fitsOnGrid : Checks if a word fits within the bounds of the grid.
• isValidPosition : Checks if a row/column position is a valid one for the grid.

You can check it out here .

Generating the Best Crossword Puzzle

Once we have the ability to place words on a grid we need to start making a whole bunch of crossword puzzles. Then, we need to pick the best one and display it on the screen. The top-level function that does all this is called createCrosswordPuzzle .

The createCrosswordPuzzle function has several nested functions that help accomplish its goals. Here is the comprehensive list of each function and what it does:

• generateGrids : Generate a bunch of crossword puzzles.
• attemptToPlaceWordOnGrid : Take a given a word and try to place it on the crossword puzzle.
• getAWordToTry : Fetch a word that we want to try placing on the crossword puzzle.
• getBestGrid : Pick the best crossword puzzle from the ones we generated.
• isGoodWord : Determine if a word is a good candidate to try placing on crossword puzzle based on the letters on the board.
• displayCrosswordPuzzle : Show the crossword puzzle on the screen.
• pushUsedWords : Mark a word as used and add its letters to a list of ones present on the crossword puzzle.

In addition to the functions above, this file contains some helper functions for getting unused words and various random values.

You can check it out here .

Performance Optimizations

I hope the previous sections have helped you see how all the pieces fit together. A crossword puzzle generator is a non-trivial problem, but breaking it down into smaller problems is a good way to approach it. In fact, that’s a good approach for any programming task.

I would like to cover one more aspect in further detail. By default, this code isn’t very fast. There is a very large amount of nested looping.

I’m going to share with you the steps I took to make it faster. If you know of betteralgorithms I’d love for you to write me a comment. This is a life long craft, and I’m as much of a student as I am a teacher.

There are 4 steps I took to improve the performance. I’ll refer to them as Adjusting The Inputs, Smart Word Picking, Knowing When To Quit, and Calling It Good Enough.

Adjusting The Inputs

There are two variables that can have a major affect on the speed of the program. One controls the number of grids to make, and the other controls the number of attempts to fit words on the grid.

I found that a high number of attempts meant that I could lower the total number of grids to make. A high number of attempts helps ensure that the crossword puzzle will be densely packed with words.

Play around with these inputs yourself and notice how they affect the speed of the program and what the crossword puzzle looks like. I tried to optimize for creating a good looking crossword puzzle while not causing the page to timeout.

Smart Word Picking

One way to speed things up is to limit our word selection to words that have a chance at being placed on the grid.

At first I picked each word totally at random, but that resulted in trying to place words on the grid that had no possible way of fitting. So I wasted a bunch of time looping through the grid, and I also wasted attempts at fitting words on the grid.

To fix this I started keeping a list of which letters exist on the crossword puzzle. That way I could limit my word selection to only words that start with one of those letters. I created the function below to aid in identifying good words to try. It isn’t perfect, but it prevents some unnecessary looping.

Knowing When To Quit

Sometimes you just gotta know when to quit. As more words are added to the crossword puzzle, the likelihood of successfully placing another word goes down. There isn’t as much space for it, and the requirements for placement become stricter.

Eventually we’ll start failing for an exceedingly long time to place a word on the grid. I decided it would be better to just end things at that point. If we are having trouble placing words on the grid it is probably pretty full anyways.

It’s the law of diminishing returns at work.

Here is the section of code where this takes place. The number 470 is pretty arbitrary. It seemed about right after doing some testing.

Calling It Good Enough

The final step I took to improve performance was to stop generating crossword puzzles once I had created one with at least 4 word intersections.

A crossword puzzle with 4 word intersections usually looks pretty good, so stopping once we have one of those cuts down on our average generation time.

See below.

Conclusion

Wow that was a long and tedious post. I really hope somebody actually reads this far. If you do, leave me a comment. It will make me feel better about writing all of this :joy:

I hope you’ve been able to get your own crossword puzzle generator up and running. It’s a fun project with a lot of details to consider. If you can implement it yourself and understand how all the pieces work you’ll definitely be a better developer for it.

As always, thanks for reading. You cansubscribeto my blog if you’d like some tips on writing functions and to have my next post emailed to you.