All the words in the following quote can fit, Boggle-style, in a 4ｘ4 grid:
Space is to place as eternity is to time.
Try it yourself: set letters in the grid so that all words in the above quote are underlined. One cell can even be left blank, there are multiple solutions.
The first Gridograms were created with pencil and paper, trial and error, using heuristics you may have discovered when filling in the grid above. It’s kind of a fun exercise, a little like sudoku.
But how did we know that a 4ｘ4 grid was the right size for the quote?
Take the letters used in “Space is to place as eternity is to time.”, noting that T and E are needed twice to spell “eternity”:
ACEEILMNOPRSTTY
That’s 15 letters, and for this quote 15 is also the actual number of cells needed. We use 4ｘ4 rather than 5ｘ3 to keep Gridograms near square, as 𝑛ｘ𝑛 or 𝑛ｘ𝑛−1.
Often, however, this counting exercise only provides a lower bound, not the exact number of cells needed. Let’s try another quote:
Thank heavens, the sun has gone in, and I don’t have to go out and enjoy it.
Letters used:
ADEEGHIJKNOSTUVY
That’s 16 letters, so another 4ｘ4 grid? Nope, that won’t be big enough to include all the words in the quote. Can you figure out a reason why? (I’ll come back to this.)
Why estimate grid size?
Grid size is one of the key criteria for deciding whether a quote can feature as a Gridogram. The majority of Gridograms are 4ｘ4 or 5ｘ4. An occasional 5ｘ5 makes the cut, but can take players significantly longer to solve — sometimes too long for what’s meant to be a fun casual daily game.
Large grids can also take significant amounts of time to find. We want to fit multiple words on paths in a grid, and a 4ｘ4 grid has 12,029,640 different paths. A 5ｘ5 grid has 115,066,382,913 paths. Yes, I have left an algorithm running for days trying to find a grid! But I have not yet tried a quote that needs a 6ｘ6 grid which would have 9,913,814,758,253,424 paths. [1]
So why can’t “Thank heavens, the sun has gone in, and I don’t have to go out and enjoy it” fit in a 4ｘ4 grid? Hint: look at those underlined letters.
Cells in a grid corner connect with 3 others. Cells along an edge connect with 5. Cells away from the edges have the most connections: 8.
The letter N in the quote is very friendly: it wants to be next to A, D, E, I, J, K, O, S, and U. That’s 9 different letters, more adjacencies than one grid cell can have!
So the grid will need more than one N. Updating the letter list to ADEEGHIJKNNOSTUVY gives us a new lower bound of 17 letters. The quote does indeed fit in a 5ｘ4 grid, you can try to create one below (3 cells can be left blank).
Thank heavens, the sun has gone in, and I don’t have to go out and enjoy it.
How can we programmatically take account of cases like this quote, to better estimate grid size? With undirected graphs!
[1]: The On-Line Encyclopedia of Integer Sequences (A236690). Even getting a count for how many paths exist is not trivial. I wrote a naive Fortran program (new language for me, wanted to try it) to exhaustively count the paths for 2ｘ2 (64), 3ｘ3 (10,305), and 4ｘ4 (12,029,640) grids. 5ｘ5 was taking some time to compute, fortunately pasting the path counts for smaller grids in Google led me to the OEIS.
contact@gridogram.com