While algorithms are in the process to be improved, some thoughts on the grids.

A "

selection" is the series of contiguous white boxes on the same horizontal line or on the same vertical line between two black boxes. A selection must have at least 2 (white) boxes. The proposed grid has 18 selections.

To fill the grid with words of a dictionary, one have to consider for each selection of n boxes, all the n letter words.

Let E(n) be the number of words in the dictionary having n letters .

In theory, the total number of cases to consider for the p selections is Ind = E(n1).E(n2)...E(np), where nk is the the number of letters of selection k.

Of course, Ind is a large upper bound of the cases to study by an efficient algorithm, but it gives an index of the complexity of the grid.

As Ind is a huge number, I chose Log(Ind) rather than Ind itself.

The proposed grid (18 selections) has an index = 178.

I tried to find 9x9 grids with the highest index of complexity. I came up with this kind of grids (13 black boxes, 34 selections, Ind = 258):

- Difficult grid.JPG (18.27 KiB) Viewed 771 times

JPF