Autofilling Algorithm

Status: Draft | 2026

Author: Laureen Caliman

Reviewer: Jonathan Blandford

Summary

The Autofill algorithm generates a grid based on a depth-first search algorithm that uses recursion to backtrack dynamically and generate a grid with infinite boundary potential. The algorithm maps a list of user-defined words (strings) to a coordinate system starting at the origin (0,0) and branches from there based on intersections with shared characters. To ensure all words intersect, the algorithm will use DFS to use the longest word, then search inward in the list to try all possibilities against that word. Words that do not immediately intersect will prompt the algorithm to backtrack by popping one word at a time and trying a different intersection up until root. Words that do not intersect even with backtracking get put aside in the list, where they are then retried later. If no intersections are possible with a word, then it gets omitted from final grid.

Requirements

The words will be provided by the user and the algorithm must generate a valid intersecting grid based on a total word count of 0 <= N <= 30, where each string is limited to length 1 <= L <= 25. The grid will ideally be visually compact without islands. Words intersect at shared characters. The final structure must form a single connected graph. Every string placed after the parent node must intersect at least one existing character on the board.

Prior Art

Other related open-source games that utilize similar concepts would be Scrabble and Sudoku puzzles. Working backwards from the word-solver algorithm.

Approach

The grid will start at (0,0), and expand outward in all four directions. The user will input a list of their words, and hit a button to generate a final grid. The algorithm pushes forward down the list by placing them on the connected grid, and popping backwards to reconsider the structure when a node fails.

Word Placement

For now, the first word in the list will be placed in the center of an empty grid and infinitely expand in all directions. The following words in the list will test their letters against word(s) present on the board; if there is a valid intersecting match, it will place. If word(s) cannot be placed, then the board invalidates the structure and backtracks to find the next available intersection upon placed words, and try the new string again. This could lead to a whole rearrangement of the grid down to root.

Intersecting Words

Before placing words, the algorithm utilizes boundaries shelled around words. It must check the N + 1 and N - 1 coordinates surrounding words to ensure there is no parallel distribution of words which causes gibberish.

Areas For Improvement

Maybe in the future we can implement a GArray to store a word-bank of the unfitted words to be saved and used at a later date, rather than getting deleted if they don’t apply to the current grid.

Including the ability to detect to possible path for a word in the list from the start.

Heuristics for length, unique letters, common letters from the start

Make code asyncronous

// ======================================================================================================

pseudocode for steps of basic first draft to implement:

  1. List of words are formed *sort by length

  2. Algorithm takes first word it sees and places it as root at origin

  3. DFS goes down list trying words for connections *current grid gets checked for valid intersections *if intersection is found, word is placed there *algorithm then goes further down list

  4. If word is hit that has no intersections with current format, previous word gets popped off grid *previous word that was popped gets tried at another intersection *backtracking can go down to root word

  5. If every combination was tried and word still is invalid, it gets skipped in list *continues going down list *once edge has been hit, go back down list

  6. return false if word can’t be placed, use grid with most amount of words that are valid as final grid