Crossword Genetic Algorithm
A Python search engine for generating crossword layouts.
- Problem
- Find connected crossword layouts while respecting intersections and placement constraints.
- My role
- Built the evolutionary search and fitness function in Python.
- Result
- A script that processes word lists and outputs grid coordinates using the Python standard library.
What I delivered
Give the script a list of words and it searches for valid intersections on a 20×20 grid. It initializes a population of candidate layouts, evaluates how words cross and connect, and evolves higher-scoring candidates across generations using only the Python 3 standard library.
A real generated layout
Input: eager, violin, server, house, evening. This example uses the first five words from the repository’s first input file.
- Generate candidates
Start with random word positions and orientations.
- Evaluate and select
Reward matching crossings and connectivity; penalize conflicts and unwanted neighbors. Retain the higher-scoring half.
- Combine and mutate
Exchange placements between parents and occasionally relocate a word, then evaluate the next generation.
This is one reproducible sample, not a guarantee of an optimal layout. Inspect the search implementation ↗
The problem
Words need to share matching letters, leave space around their edges, and form a connected grid. A placement that helps one word can create a conflict elsewhere. This project explores a genetic algorithm for searching those combinations.
Engineering decisions
Represent each layout as word placements
Each candidate stores a row, column, and horizontal or vertical direction for every word. The default run starts with 2,000 random candidates on a 20 by 20 grid.
Score crossings, conflicts, and connectivity
Matching letters earn points. Conflicting letters, adjacent parallel words, and occupied cells at word ends incur penalties. A depth-first search counts connected components, rewarding a unified single-component grid.
Keep, combine, and mutate
Each generation retains the top-scoring half of the population. Parent pairs produce offspring by exchanging slices of word placements, with a 15% mutation rate relocating individual words over 200 generations.
Read words in, write coordinates out
Built with zero external dependencies using the Python 3 standard library. It processes batch word lists and outputs each word's starting row, column, and orientation.
Implemented in Python 3 using standard-library data structures, depth-first connectivity analysis, and generational crossover.
Delivered outcomes
- Implemented a complete evolutionary search loop with truncation selection, slice crossover, and random mutation
- Combined letter intersection scoring, adjacency penalties, and DFS graph connectivity into a unified fitness function
- Processed batch word datasets into coordinate-mapped grid layouts using only the Python 3 standard library
Let’s talk engineering
Have a role or project in mind?
I’m available for remote software & cloud engineering roles and B2B contracts.
Email me View résumé ↗Explore another project
Commercial client delivery: Barnicoat CRM →