The New Sudoku Players' Forum

[Tomoka]

I was wondering if we can canonicalize all Sudokus. If we can't do all of them, then let's start the first 10, and then show the last one as a symbolic "closure".

The canonicalization is based grids, then Sudokus that fit the grid. Digits ordered from 1 through 9. For each grid, Sudokus are ordered from fewest clues to most clues. For Sudokus with the same number of clues, clues are ordered based on positions of the clues; from top to bottom, then left to right. Again, digits are ordered from 1 through 9, and canonicalized based on the numbers in the top row first, and then in cells from left to right. I notice this Sudoku by Rico Alan (rotated and rows re-ordered compared to how he posted it):

Code: Select all

1234.....
.....3456
.........
2345.....
.....4567
.........
3456.....
.....5678
.........

Based on the proposed canonicalizing scheme, can we say that this is the first Sudoku? If not, then what is the first Sudoku? Also, how many more Sudoku's will there be in the complete list?

[coloin]

Code: Select all

+---+---+---+
|123|4..|...|
|...|..1|234|
|...|...|...|
+---+---+---+
|582|7..|...|
|...|..3|549|
|...|...|...|
+---+---+---+
|759|8..|...|
|...|..4|671|
|...|...|...|
+---+---+---+



This may not be what you are looking for - but as ever its never straightforward - but this is a lexographically less - but by no means the least.
I guess there may be over 10 million [ maybe a whole lot more] ED puzzles [min and non min] with this pattern

this one is looking toward the end [ all bands are the largest minimum] but can be morphed smaller...]

Code: Select all

+---+---+---+
|123|4..|...|
|...|..5|671|
|...|...|...|
+---+---+---+
|987|6..|...|
|...|..4|327|
|...|...|...|
+---+---+---+
|479|8..|...|
|...|..1|539|
|...|...|...|
+---+---+---+

[Tomoka]

I checked your first one but not your second one. I just realized that neither your Sudoko nor mine is close to the front of the list because they aren't even from the first grid. (Grids are canonicalized before the puzzles of the grid). So to be early in the list, it has to be a Sudoku from this grid (I think):

Code: Select all

123456789
456789123
789123456
234567891
567891234
891234567
345678912
678912345
912345678

Both your Sudoku and mine are good (maybe within the top 1%) but I think we can do much better. There's lots of Sudokus.

[Maq777]

I was wondering if we can canonicalize all Sudokus. If we can't do all of them, then let's start the first 10, and then show the last one as a symbolic "closure".

Of course you can canonize all sudoku puzzles, in the simple case of sudoku 4x4 , you will get 12 sudokus, one for each of the 12 models (or invariant grids) that exist.

https://github.com/MiguelQuinteiro/ImagenesSudoku/blob/master/Canonicos%20de%20Shidoku.png

Unfortunately doing the same for sudoku 9x9 is a bit more difficult, since you will have to generate 18.383.222.420.692.992 lines, one for each of the invariant grids that Russell and Jarvis counted.

[Mathimagics]

(Grids are canonicalized before the puzzles of the grid). So to be early in the list, it has to be a Sudoku from this grid (I think):

Code: Select all

123456789
456789123
789123456
234567891
567891234
891234567
345678912
678912345
912345678

That grid is far from being the first. In the ED grid catalogue (grids in minlex order), it is grid #992769.

The first grid (grid #1) is this one:

Code: Select all

 +-------+-------+-------+
 | 1 2 3 | 4 5 6 | 7 8 9 |
 | 4 5 6 | 7 8 9 | 1 2 3 |
 | 7 8 9 | 1 2 3 | 4 5 6 |
 +-------+-------+-------+
 | 2 1 4 | 3 6 5 | 8 9 7 |
 | 3 6 5 | 8 9 7 | 2 1 4 |
 | 8 9 7 | 2 1 4 | 3 6 5 |
 +-------+-------+-------+
 | 5 3 1 | 6 4 2 | 9 7 8 |
 | 6 4 2 | 9 7 8 | 5 3 1 |
 | 9 7 8 | 5 3 1 | 6 4 2 |
 +-------+-------+-------+

123456789456789123789123456214365897365897214897214365531642978642978531978531642


Your definition of puzzle ordering is not clear to me, but clearly "first puzzle" means a puzzle on grid #1, with the minimum number of clues.

So, it's worth knowing that for grid #1, that means a puzzle with 19 clues. This is somewhat inconvenient - if the minimum puzzle size was 18, we could quickly identify that "first puzzle". All I can say for sure is that one example of a 19-clue puzzle on grid #1 is this:

Code: Select all

.2......9..678.1.....1.........6.8..3....7....9......5.3...2......9.......8...64.

[Maq777]

In a sense to canonize it would not matter much if it is a sudoku puzzle or a sudoku solution. what really needs to be canonized and ordered would be the invariant grids or models.

Working with the templates this task can be easily done

All you have to do is give the cells a logical order, then give a logical order for the templates they generate, to finally generate each of the invariant models or grids from gathering all the templates in a logical order in all its possible combinations.

I created a program that does just that.

Separating the templates into nine groups depending on those that pass through cell 1, or through cell 2, or through cell 3 and so on until cell 9.

https://github.com/MiguelQuinteiro/ImagenesSudoku/blob/master/Canonizar00.png

So I get the first model or grid invariants to be canonized, simply making sure to fill cell1 with digit 1, cell2 with digit 2 and so on until cell9 is filled with digit 9.

https://github.com/MiguelQuinteiro/ImagenesSudoku/blob/master/Canonizar01.png
Model(1) = 1.6340.12793.18214.24667.31006.31301.37703.43973

A program that sequentially reviews all combinations is easy to do but impossible to wait for it to finish running in an accessible period of time.

So we can jump to directly use the last template of digit1 and combine it with the last template available for digit2 and so on until we obtain the last of the canonicals.

https://github.com/MiguelQuinteiro/ImagenesSudoku/blob/master/Canonizar02.png
Model(18.383.222.420.692.992) = 5184.9208.13152.18069.22003.26003.36002.39771.44450

Of course the order dependent on the way to number the cells and templates in the first place, but at least this way helped me to understand the issue of canonizations.