Question: What are the maximum and minimum lengths of the sequences of consecutive completed Sudoku which occur when order 9 Latin squares are generated in (standard) lexicographic order?
A minimum length of 192 and a maximum of 3072 have been found by experiment. Are these also the theoretical limits?
Interestingly, all lengths are multiples of 12 and every multiple of 12 from 240 to 1152 occurs. A subsidiary question is whether it can be proved that lengths are always multiples of 12.
Note: in this discussion "Sudoku" or "completed Sudoku" refers to a complete 9x9 Latin square which adheres to the properties or constraints which define a Sudoku
Background
When I generated a random Sudoku I was surprised to discover that the next Latin square in lexicographic order also had the Sudoku property. Repeating the process on the resultant Sudoku produced yet another with this property.
Actually, with a little thought, this was not so surprising because if the upper two thirds of a Sudoku remain fixed, any changes (which still maintain the Latin square property) to the lower third can be shown to result in a Sudoku. It is only if moving to the next Latin square in lexicographic order results in row six being changed that there is a possibility of the resulting Latin square not having the Sudoku property.
I then wondered how long this would go on for and so repeated the process until a non-Sudoku resulted, thus producing a sequence of Sudoku Latin squares. After repeating the experiment with different random starting Sudoku I was even more surprised at how long these sequences were with most having over 100 members.
Given that each sequence was most likely the second part of a much longer sequence, a modified program was used to process back from the initial random Sudoku until the start of the sequence was found. Thus it was possible to calculate the total length of the sequence.
The range of sequence lengths found by repetitions of the above experiment ranged from a minimum of 192 to a maximum of 3072 with the majority being between 200 and 500.
An example of a sequence of length 2304 starts with the Latin square:
[ 3, 1, 8, 6, 2, 7, 5, 4, 9 ],
[ 2, 7, 5, 4, 1, 9, 6, 8, 3 ],
[ 6, 4, 9, 8, 3, 5, 1, 7, 2 ],
[ 9, 2, 6, 7, 8, 3, 4, 1, 5 ],
[ 7, 3, 4, 1, 5, 2, 8, 9, 6 ],
[ 5, 8, 1, 9, 4, 6, 2, 3, 7 ],
[ 1, 5, 2, 3, 7, 4, 9, 6, 8 ],
[ 4, 6, 3, 2, 9, 8, 7, 5, 1 ],
[ 8, 9, 7, 5, 6, 1, 3, 2, 4 ]
and ends with:
[ 3, 1, 8, 6, 2, 7, 5, 4, 9 ],
[ 2, 7, 5, 4, 1, 9, 6, 8, 3 ],
[ 6, 4, 9, 8, 3, 5, 1, 7, 2 ],
[ 9, 2, 6, 7, 8, 3, 4, 1, 5 ],
[ 7, 3, 4, 1, 5, 2, 8, 9, 6 ],
[ 5, 8, 1, 9, 6, 4, 3, 2, 7 ],
[ 8, 9, 7, 5, 4, 6, 2, 3, 1 ],
[ 4, 6, 3, 2, 9, 1, 7, 5, 8 ],
[ 1, 5, 2, 3, 7, 8, 9, 6, 4 ]
The question is: are 192 and 3072 also the theoretical limits to the lengths of the sequences of consecutive Sudoku? Interestingly, 192 = 3x2^6 and 3072=3x2^10.
Subsidiary question
Is there a proof of the subsidiary question that the lengths of the sequences of contiguous Sudoku which occur when Latin squares are placed in lexicographic order are always multiples of 12?
It was noted above that every multiple of 12 from 240 to 1152 occurs.
Given that the last three rows of a Sudoku can be rearranged in 3! ways without destroying the Sudoku property, one can see how a factor of 6 could arise. However it also needs to be shown that all 6 arrangements occur before the process generates the next non-Sudoku Latin square.
Still need to explain the further factor of 2 arises.
Other findings and questions
The distribution of sequence lengths is highly irregular and multi-modal. 100,000 repetitions were performed and the distribution of the sequence lengths plotted. This was done a second time producing a second distribution the shape of which was very close to the first.
Local maxima occur for lengths of 336, 384, 456 and 480 with over 600 occurrences at each and there are minima in between these of under 400 occurrences. A particularly low minimums occurs for length 420 where only 107 occurrences were registered.
Local maxima also occur for occurrences of sequence lengths of 336, 384, 456 and 480 with over 600 occurrences at each and there are local minima in between these each of under 400 occurrences. A particularly low minima occurs for length 420 where only 107 occurrences were registered.
After a very low minimum (28) of occurrences for length 528 another local max of 380 occurs for length 576. After this the number of occurrences is low (under 50) until a maximum of 92 occurs for length 768 followed by 94 for 804. From then on the tail of the distribution has very low numbers of occurrences except for a 'blip' at sequence length 1152 with 57 occurrences.
Need to investigate whether the program used to generate a random Sudoku produces a sufficiently uniform distribution and does not have anomalies which cause the sequence length distribution to be irregular.
The properties of the lengths of the sequences of contiguous Sudoku is a particular case of a more general situation where a subset of Latin squares of a specified order has been defined by some constraints. The question then revolves around the properties of the lengths of contiguous sequences within the standard lexicographical ordering which exhinit those properties. The simplest example is the length of contiguous sequences in which a defined cell position in the Latin squares has a specified value.
