How Orca Works — a blog post style explanation of the algorithm and design.
A high-performance crossword grid filler.
Orca is designed for wide-open grids that are difficult for other solvers. It uses AC-3 propagation with cell-level branching, and tuned heuristics for rapid exhaustive search. Multi-threaded search is supported via partition-based parallelism.
Download from GitHub Releases.
cargo build --release
# Binary is at ./target/release/orca# Find all solutions
orca fill my_grid.grid my_words.dict
# Find first solution only
orca fill my_grid.grid my_words.dict -n 1
# Use 4 threads
orca fill my_grid.grid my_words.dict -j 4Orca takes any .dict file as a command-line argument, you supply your own dictionary.
Orca uses .dict files with one entry per line:
WORD;SCORE
- Words must be uppercase A-Z
- Words shorter than 3 letters are ignored
- Scores are currently unused
Orca uses .grid files. The first non-comment line is rows cols, followed by the grid:
# This is a comment
5 5
#..#.
.....
.....
.....
.#..#
| Character | Meaning |
|---|---|
# |
Black square |
. |
Empty cell (to be filled) |
* |
Wild cell (unconstrained) |
A-Z |
Prefilled letter |
[ABC] |
Letter subset constraint |
Comments (lines starting with #) are only allowed before the dimensions line.
Fill a crossword grid with words from a dictionary.
| Option | Default | Description |
|---|---|---|
-n, --max-solutions N |
0 (all) |
Stop after finding N solutions |
-j, --threads N |
1 |
# of parallel threads |
--disallow-shared-substring N |
6 |
Set to 0 to disable |
--symmetry-break "r1,c1,r2,c2" |
Enforce l(r1,c1) <= l(r2,c2) | |
--progress-interval N |
10000 |
Report progress every N nodes |
--split-timeout N |
3 (sec) |
Task timeout (multi-core only) |
Solutions are printed to stdout; progress and stats go to stderr.
Print grid layout, slot details, and dictionary statistics.
Check a dictionary file for format issues.
A benchmark grid and script are included. To get comparable results, we recommend using Spread the Wordlist (~465K entries) as a standardized dictionary:
mv ~/Downloads/spreadthewordlist_caps.dict dictionaries/
./bench.shThe script builds a release binary and runs an exhaustive search on a 15x15 grid. Use ./bench.sh --parallel N to benchmark multi-threaded search.
MIT
