I agree with @zeroexcuses that the goal should be killing branches aggressively. Here I suggest a way to do that.

Let's consider how you could proceed by choosing one word per column. Once you choose a word for the first column, the only words eligible for the first row are those that start with the first letter of the chosen word, the words eligible for the second row are those that start with the second letter of the chosen word, and so on.

**If you have a sorted list of all the words, each list of eligible words is a contiguous sublist.** Instead precomputing prefix lists, you could use binary search to shrink the eligibility lists. In this way, you can store a slice per row as the eligibility list, with no allocation. (If an eligibility list shrinks to zero, there are no solutions for the partially filled square.)

If instead you filled the top row, you could instead store and shorten lists of eligibility for each column.

So the next step is to combine these approaches, and at each step, choose to either fill the first unfilled column or fill the first unfilled row -- whichever has the smallest number of eligible words remaining.

Donald Knuth wrote a paper about the cubed version of this problem: "5 x 5 x 5 Word Cubes by Computer" (Word Ways 26 (1993); Selected Papers on Fun & Games (chapter 37)). He also discusses the square case; his dictionary of 5,757 five-letter words yielded 541,968 squares, 280 of which contained the same word more than once. (**Edit:** The solution counts were for symmetric squares only.)

They stated that they used Dancing Links for the problem. Dancing Links is linked-list based and not necessarily a great fit for Rust, but we can consider more generally how Dancing Links works: It solves exact cover problems.

## Exploration of an exact cover approach

How can we rework this problem as an exact cover problem? That is, you have a binary matrix, and you want to select a set of rows such that every column contains exactly one 1.

The columns here could be every unique combination of

- Axis (horizontal or vertical)
- Cell number (25 possibilities in your case)
- Letter of the alphabet

Every row represents a word placed horizontally or vertically in a specific row or column; thus every word from the dictionary will get 10 rows.

A horizontally placed word would have 1s in the columns

- Horizontal + occupied cell + letter in that cell
- Vertical + occupied cell + (every letter
*not* in that cell)

And vice-versa for vertically placed words. By this design, words that cross are forced to have the same letter in order to create an exact cover of the columns for that cell, and any two words in the same position always collide.

To make the description more concrete, below is an example solution to a 3x3 square over the alphabet "acent". The solution is

```
cat
ace
ten
```

```
horizontal vertical
1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9
acent acent acent acent acent acent acent acent acent acent acent acent acent acent acent acent acent acent
-----------------------------------------------------------------------------------------------------------
x x x x xxx xxxx xxxx
x x x xxxx x xxx xx xx
x x x xxxx xx xx xxx x
x xxx xxxx xxxx x x x
xxxx x xxx xx xx x x x
xxxx xx xx xxx x x x x
-----------------------------------------------------------------------------------------------------------
xxxxx xxxxx xxxxx xxxxx xxxxx xxxxx xxxxx xxxxx xxxxx xxxxx xxxxx xxxxx xxxxx xxxxx xxxxx xxxxx xxxxx xxxxx
```

The design can be expanded to cubes in a straightforward fashion.

To then solve the exact cover problem, you can use a backtracking reduction algorithm.

- If the table is empty, you're at a solution; visit the solution and return. Else,
- Choose the column with the least number of 1s
- A column with no 1s indicates a dead end; return

- For each row that has a 1 in the chosen column
- Include the row in the partial solution
- Build a reduced matrix
- For every column covered by the row, remove any row that covers that column (collisions)
- Remove those columns as well (or otherwise mark them as done)

- Recurse the algorithm on the reduced matrix
- Remove the row from the partial solution and continue looping on the non-reduced matrix

An empty table indicates a solution to the problem; a column with no 1s indicates a dead-end to backtrack out of.

The exact cover approach as outlined can be considered choosing an empty cell, and then iterating over either

- All horizontal words with a specific letter and all vertical words without that letter, or
- All vertical words with a specific letter and all horizontal words without that letter

The cell is chosen based on having the smallest number of words to iterate over. It's therefore close to a generalization of the prefix approach above, wherein you could choose any unfilled row or column, as opposed to just the first unfilled row or column.