Mathimagics wrote:.
On the subject of transformations, I have a question for blue.
For SudokuP (9x9) we had 2592 transformations, to which E and F expanded this by factor of 4 to 10,368.
My naive solution canonicalisation approach (which generally has to work with much smaller transformation sets, eg PX, PWX, etc) simply applies all transformations and chooses the "smallest" representation. But in that original SudokuP canonicalisation function you gave me, you only test 16, I think, all combinations of your E,D,F,G.
(...)
It seems both suspect, and yet at the same time miraculous!
It was more complicated than you remember.
There was an outer loop over the 8 transformations generated by {D,F}.
Inside that, there were loops over 9 rows that can map to the row 1 position, and 6*6 ways to permute stacks & columns.
A speedup factor of ~4, was in the works ... 4 * (8*9*6*6) = 10368.
I guess it's just me failing to grasp something elementary - after all, I'm sure that with standard Sudoku nobody actually checks all 3.35 million different transformations, or do they?
It's very slow on a long list of grids -- even on a short list.
If the SudokuP code was modified for vanilla Sudoku, the number of inner loop itterations would be 2*9*6^4 = 23328, with a speedup factor of ~144 in the works.
There are other canonical forms (for full grids), where the inner loop needs only 648 itterations -- "Anchor 5" and "box-minlex", for example.
For "Anchor 5", the 648 comes from
- a transpose option (2)
- 6 * 6 ways to permute bands & stacks
- 9 choices for a cell from box 5, to be mapped to r5c5
Alternatively, it comes from
- 9 digit templates to choose from
- 2 * 6 * 6 ways to map the choice to a fixed template
For "box-minlex", the 648 comes from
- a transpose option (2)
- 9 boxes to choose from, to be mapped to the box 1 position
- 6 * 6 ways to permute rows & columns in band 1 & stack 1
Cheers.
