I am implementing a new type of crossword puzzle in GNOME Crosswords this summer. The current options are static crosswords of ‘known’ location. My project does the opposite, where it takes the words and places them wherever we can get the maximum amount of connections between the words. The pinnacle of this is a DFS backtracking algorithm because we want the words on the grid to be malleable in their placements in order to include the next word going down the list.

Previously, what I had done was attempt to erase the word letter-by-letter recursively writing NULL to each cell. However, this removed every element in the string, including the letter shared at a node between two words, leaving a gap in the word left in place.

My most current version instead focuses on state preservation. Before we even write a new word to the grid, we read the existing state of cells with focus on those connections. Now when the recursive function attempts to place a word that ends up being impossible to connect with the current setup, we look for those ‘?’ characters, erase the string, and rewrite the cushioned letter to leave the other word fully intact.

Imagine a board with CAT written across the center, and we want to place MACAW on the grid vertically. Before the algorithm writes MACAW, it inspects the board at the calculated intersection point(s) and reviews the cells of the string length.

Cell 1: Empty, Cell 2: Empty, Cell 3: C, Cell 4: Empty, Cell 5: Empty.

The board saves this state in memory using a ‘?’ in place of the empty cells as ‘? ? C ? ?’. Hypothetically this makes our board look temporarily like this in memory:

?

?

C A T

?

?

MACAW is written to the grid and then checked in the next recursive function call to ensure if it can be kept or not in that hypothetical place. If it runs successfully, we leave it as is:

M

A

C  A  T

A

W

If it returns false, we need to backtrack and erase MACAW. Rather than totally erasing the word like before, we send the ? ? C ? ? state back to our overlay function – which is responsible for writing to the grid. If it sees a ‘?’, it empties the cell. If it sees a letter, it rewrites it. That way we are only backtracking and erasing the word creating an obstacle in our program. MACAW is erased, CAT remains there for the next word to be attempted.