Perfectly Cyclical Sudoku's

Everything about Sudoku that doesn't fit in one of the other sections

Perfectly Cyclical Sudoku's

Postby Mathimagics » Fri Mar 09, 2018 9:57 am

.
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
User avatar
Mathimagics
2017 Supporter
 
Posts: 756
Joined: 27 May 2015

Return to General