This thread is prompted by the following grids that turned up in the "SudokuP Min Clue" project
- Code: Select all
1 2 3 | 4 5 6 | 7 8 9 1 2 3 | 4 5 6 | 7 8 9
4 5 6 | 8 9 7 | 2 3 1 5 6 4 | 8 9 7 | 2 3 1
9 7 8 | 3 1 2 | 4 5 6 9 7 8 | 3 1 2 | 6 4 5
--------------------- ---------------------
5 6 4 | 9 7 8 | 3 1 2 6 4 5 | 9 7 8 | 3 1 2
7 8 9 | 1 2 3 | 5 6 4 7 8 9 | 1 2 3 | 4 5 6
2 3 1 | 5 6 4 | 8 9 7 2 3 1 | 5 6 4 | 8 9 7
--------------------- ---------------------
8 9 7 | 2 3 1 | 6 4 5 8 9 7 | 2 3 1 | 5 6 4
3 1 2 | 6 4 5 | 9 7 8 3 1 2 | 6 4 5 | 9 7 8
6 4 5 | 7 8 9 | 1 2 3 4 5 6 | 7 8 9 | 1 2 3
For either grid, pick any 2 cells in the same row, r1, ie {r1, c1, c2}. Call the two cell values A and B. Find the row r2, with B in column c1. Then find the column c3 in row r2 with {r2, c3} = A. Now find the row r3 with B in c3, ie {r3, c3} = B.
That 3rd row will have an A in column c2, thus completing the (A, B) cycle. Every (A, B) cycle in these grids is of length 6 (3 pairs of cells, spread across 3 rows x 3 columns).
Every distinct (A, B) pair belongs to 1 of 3 distinct cycles, and so there are 108 individual 6-cycles. Each cycle that hits 2 cells in 3 different boxes gives us a UA set of size 6 for standard Sudoku.
(A fairly gentle introduction to the link between UA sets and cycles can be found here.)
These were found accidentally - the grids above are SudokuP grids, but none of the 6-cycles correspond to UA's for SudokuP because swapping A and B for each cycle for these grids does NOT produce another SudokuP grid. Each triplet of (A,B) cycles needs to be combined to form a UA of size 18. By overlooking this, I reported (wrongly) that these grids had NO SudokuP UA's.
For 9x9 Latin Squares, each of the 36 different (A, B) pairs forms from 1 to 4 cycles, with one of 6 possible combinations of cycle lengths:
- 18
- 14 + 4
- 12 + 6
- 8 + 6 + 4
- 6 + 6 + 6
- 6 + 4 + 4 + 4
For Sudoku grids, each individual (A,B) cycle must consist of pairs of cells in the same box, or we don't get a valid Sudoku grid by swapping A and B along the cycle. For SudokuP we additionally require the same condition applied to box-positions.
Let's call a grid perfectly cyclical if every (A,B) cycle has the same length. Clearly this can only happen for cycles of length 6 (as per our 2 examples) or 18.
Now all 3,359,232 isomorphisms of a Sudoku grid have the same cycle structure, so we only have to check essentially different Sudoku grids to find out how common is it for a grid to be perfectly cyclical?
A search of the catalog (5,472,730,538 grids) turned up just 6 cases of grids with all cycles having length 6, and 9 cases of grids with all cycles having length 18. That makes these grids very rare indeed!
The type 6 cases are:
- Code: Select all
123456789456789123789123456231564897564897231897231564312645978645978312978312645
123456789456789123789123456231564897564897231978312645312645978645978312897231564
123456789456789123789123456234567891567891234891234567372615948615948372948372615
123456789456789123789123456267591834591834267834267591375618942618942375942375618
123456789456789231789312456231564897564897312978231645312645978645978123897123564
123456789457289163689173452245968317316745928978312645564897231731524896892631574
The type 18 cases are:
- Code: Select all
123456789456789123798231564275943618369815472841627395587362941612594837934178256
123456789456789123897231645231564978645978231978312564369147852582693417714825396
123456789456789123897231645231564978645978231978312564369825417582147396714693852
123456789456789231789123645231564897564897312897231456375618924618942573942375168
123456789456789231789123645231564897564897312897231456375942168618375924942618573
123456789456789231789123645231564897564897312978312564395248176617935428842671953
123456789456789231789123645231564897564897312978312564395671428617248953842935176
123456789456789231789123645231564978564897123897231564375942816618375492942618357
123456789457289163698713254261847935579362841834591627315928476786134592942675318
