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