Canonicalizing all Sudokus

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

Canonicalizing all Sudokus

Postby Tomoka » Thu Apr 06, 2017 6:16 pm

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?
Tomoka
 
Posts: 6
Joined: 06 April 2017

Re: Canonicalizing all Sudokus

Postby coloin » Fri Apr 07, 2017 10:07 pm

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|
|...|...|...|
+---+---+---+
coloin
 
Posts: 2004
Joined: 05 May 2005

Re: Canonicalizing all Sudokus

Postby Tomoka » Fri Apr 07, 2017 10:43 pm

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. 8-)
Tomoka
 
Posts: 6
Joined: 06 April 2017

Re: Canonicalizing all Sudokus

Postby Maq777 » Wed Mar 31, 2021 11:55 pm

Tomoka wrote: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.
Maq777
 
Posts: 48
Joined: 30 April 2016

Re: Canonicalizing all Sudokus

Postby Mathimagics » Thu Apr 01, 2021 6:19 am

Tomoka wrote: (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.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1677
Joined: 27 May 2015
Location: Canberra

Re: Canonicalizing all Sudokus

Postby Maq777 » Thu Apr 01, 2021 1:00 pm

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.
Maq777
 
Posts: 48
Joined: 30 April 2016


Return to General