Mathimagics wrote: ... moving from MG-16 to MG-81 is a bit like moving from a search space the size of a pea to one the size of Jupiter.

I call this combinatorial explosion "P2P" (pea-to-planet) syndrome.

Another case where P2P is evident, sadly, is in what I

thought might not be too hard - finding a pair of Orthogonal 16 x 16 Sudoku's.

Finding OPs (orthog pairs) with 9 x 9 grids is done very easily - enumerate the transversals, look for a set of 9 that are mutually disjoint (ie that hit every cell).

The average number of transversals for 9 x 9 Sudoku is just 21 (the absolute maximum is 279). You can find ALL orthog pairs for a batch of 10,000 grids in just a few seconds.

But, among the few 16 x 16 grids that I have tested, there is an average of 500,000 transversals!

Finding just one subset of 16 disjoint transversals among this huge pool is, inevitably, very, very hard ... none of these tests have run to completion, even after many hours.

[Note: we need one example of a pair of orthog 16 x 16 Sudoku's in order to construct an MG-256]