[kw-pm] test fish crossword test

[fishbot]

> When they do it by hand yes, but there is already software that does it
> starting from given layouts of blacked out squares. The word lists used are
> large, like tweaked dictionary lists. With a large enough word list and a
> reasonable layout I would think most grids could have many possible fills.
>
> From what I have read so far the problem seems to be one of efficiency and
> good backtracking, but much of the stuff is dated, what took hours when the
> paper was written may take seconds today.

One of the issues with this sort of fill problem is that it the
choice tree is not very deep, but insanely wide.  Realistically,
you likely want a list of 10k works to choose from, but only a
fraction of those will be candidates for a given slot.

Assume a naive recursive algorithm, where you fill one word,
recurse, if that fails, attempt the next.  On entry, our
subroutine has a partially completed grid, and we can pick which
slot we want to look at next.  We want to pick the most
constrained slot each time, to reduce the branches high on the
tree.  Most constrained should likely mean the slot for which
there are the fewest candidates.  Up high, that likely means the
longest slot, lower down it likely means the slots with the
highest percentage of committed letters.

It is similar to Sudoku solving, in that at each step, you make a
where and what decision.  As in the Sudoku problem, you likely
want the where to be deterministic, and the what to be
non-deterministic.  It would in theory be possible to use the
same DLX-inspired bitvector approach I used in the Sudoku
generator, but the scale might be stupid.  For a 15x15 grid, I
think we'd be looking at about 6000 columns, and the rows would
be in the 100k range.

Be worth trying, though, I think.  Do you have a grid and a
wordlist that we can experiment with?

Eric