The New Sudoku Players' Forum

[Serg]

Hi, Mladen!
I don't understand, are your questions serious or joky (or rhetoric), but anyway I consider them seriously.

So, you can see that rows pair with MI = 7 (no two-row UA) is the most probable event!

Is this phenomenon similar to this observation for sudoku grids in Minlex Form: Min and Max Lists / Chaining?

Yes, variant of two-row configuration for Sudoku solution grid when that configuration doesn't contain any UA sets is the most probable too (as for 9 x 9 Latin Squares). Michael Deverin's article contain data necessary for calculation of probability. This case (no UA sets in two-row combination) takes place for Ranks: 3, 9, 11, 12 - totally for 144+432+1296+1296 = 3168 (variants of the 2-nd row). Probability to observe such case is 3168/12096 = 26.2 %. The next nearest (frequent) case is U4+U14 case - probability to observe it is 21.4 %.

In just over 70% of the cases, the lowest ranking pair was of rank = 4. This is especially fortuitous, since there is only one way to convert the row pair to minlex form.

It is possible to estimate probability to get the lowest ranking pair of rank = 4 for random Sudoku solution grid.

Code: Select all

Rank   Frequency   Probability to observe (approx.)
1        72        0.00595
2       216        0.01786
3       144        0.01190
4      1296        0.10714
   ...
In total 12096 r2 row form when r1 = 123456789

Probability not to get Rank1 in one two-row (two-column) pair is 1 - 0.00595 = 0.99405 . Probability not to get Rank1 in 18 two-row/column pairs is 0.8981. Probability not to get Rank2 in 18 two-row/column pairs is 0.7230. Probability not to get Rank3 in 18 two-row/column pairs is 0.8062. Probability to get Rank4 at least once in 18 two-row/column pairs is 0.8700. Multiplication of all these probabilities gives 0.455 or 45.5 %. This is substaintially less, than 70%. Probability of 70% is observed during random Sudoku solution grids simulation. It seems different row/column pairs in Sudoku solution grids may not considered as independent (especially rows/columns in the same band/stack). So, this model doesn't work well for Sudoku, but works rather good for 9 x 9 LS.

Serg

[Serg]

Hi, Mathimagics!

A quick review of the methodology:

• LSMIN function returns minlex canonical form for a complete grid.

• LRMIN function returns "relative minlex form" for a partial (Latin Rectangle) grid, given the first NR rows. Paratopic transformations are not considered.

For each MI value (0 to 6), we can use LRMIN to generate a list of "candidate bands". We fix R1 and R2 for the MI index value, and for each possible R3 setting we add the resulting band B = R1+R2+R3 to the list of candidates if, and only if, LRMIN(B) = B.

Did you checked MI of pairs R1+R3 and R2+R3 for candidate band before adding the band to candidate list? I mean condition MI(R1+R3) >= MI(R1+R2) AND MI(R2+R3) >= MI(R1+R2).

I don't understand why candidate band with MI = 0 can be rejected. (List of "Known bands" is shorter, than list "Candidate bands" for MI = 0.) Maybe I am wrong, but it seems to me, every correct Latin Rectangle can be extended to some Latin Square.

Serg

[Mathimagics]

Did you check MI of pairs R1+R3 and R2+R3 for candidate band before adding the band to candidate list? I mean condition MI(R1+R3) >= MI(R1+R2) AND MI(R2+R3) >= MI(R1+R2).

Yes, this test is applied whenever a row is added.

I don't understand why candidate band with MI = 0 can be rejected. (List of "Known bands" is shorter, than list "Candidate bands" for MI = 0.) Maybe I am wrong, but it seems to me, every correct Latin Rectangle can be extended to some Latin Square.

A candidate band B is rejected if there are NO grid completions, G(B), for which LSMIN(G) = G. Conversely, a "valid band" is one that occurs as the first 3 rows of some minlex Latin Square.

Candidate bands for MI = 0 are less likely to be rejected than for other MI values, but still there are 37 cases where this happens. Here is a list of these candidates:

Failed candidate bands with MI=0: Show

Code: Select all

123456789214365897352789146
123456789214365897352789164
123456789214365897352789416
123456789214365897352789461
123456789214365897352789614
123456789214365897352789641
123456789214365897352798146
123456789214365897352798164
123456789214365897352798416
123456789214365897352798461
123456789214365897352798614
123456789214365897352798641
123456789214365897356789124
123456789214365897356789142
123456789214365897356789214
123456789214365897356789241
123456789214365897356789412
123456789214365897356789421
123456789214365897356798142
123456789214365897356798214
123456789214365897356798421
123456789214365897375819246
123456789214365897375819264
123456789214365897375819462
123456789214365897375819624
123456789214365897375829146
123456789214365897375829164
123456789214365897375829416
123456789214365897375829461
123456789214365897375829614
123456789214365897375829641
123456789214365897375892146
123456789214365897375892461
123456789214365897375892614
123456789214365897375918264
123456789214365897375918426
123456789214365897375918642

These all satisfy LRMIN(3, B) = B. But I think that you will find that NO minlex grid can start with these bands. In some cases, complete grids can be obtained which satisfy LRMIN(NR, G) = G (where G is the first NR rows), for NR = 4 to 9, but in every such case the final grid is not itself in minlex form, some paratopic transformation gives a lesser minlex grid.

In most cases, however, no grid completions are actually tested, because all partial grid tests return LRMIN(NR, G) < G somewhere between NR = 4 and 8.

Cheers
MM

[dobrichev]

I cannot say even that I was not aware of his ideas...

We know how good is after a very dynamic day to get a long deep sleep, and how on the next morning the whole world looks simple, ordered and beautiful.

[Serg]

Hi, Mathimagics!

Candidate bands for MI = 0 are less likely to be rejected than for other MI values, but still there are 37 cases where this happens.

If I am not mistaken, candidate bands for MI = 0 can never be rejected because of other MI values, since MI = 0 is minimal possible value of MI. Isn't it? So, candidate band for MI = 0 can be rejected only if this band cannot be extended to full Latin Square. But Wiki says Hall's marriage theorem: "The marriage theorem is used in the usual proofs of the fact that an (r × n) Latin rectangle can always be extended to an ((r+1) × n) Latin rectangle when r < n, and so, ultimately to a Latin square." So, any valid band forever can be extended to some LS. Contradiction! I am thinking about counterexample - to find a way of extending some of your 37 cases to full LS.

Serg

[Serg]

Hi, Mathimagics!
The first band from your "37 cases" list:

Code: Select all

123456789
214365897
352789146
.........
.........
.........
.........
.........
.........

is expandable to LS (hope, I am not wrong):

Code: Select all

123456789
214365897
352789146
431278965
546891273
675912438
789123654
897634512
968547321

Do you consider it non-expandable?

Serg

[Mathimagics]

Hi Serg,

If I am not mistaken, candidate bands for MI = 0 can never be rejected because of other MI values, since MI = 0 is minimal possible value of MI. Isn't it? So, candidate band for MI = 0 can be rejected only if this band cannot be extended to full Latin Square.

It is certainly true that every candidate band with MI = 0 can be extended to a complete Latin Square with MI = 0.

But that is not enough for what we are doing. We want to identify which bands actually do occur as the first 3 rows in some minlex canonical form (CF) Latin Squares.

(Consider Sudoku grids. There are 416 "candidate bands" but 15 of these are empty - there are no ED (minlex CF) grids for those bands).

Your example, for a LS with R3 = 352789146, is not in Canonical Form. The CF has different form, still MI = 0, but different R3, and this corresponds to one of the 67 "known bands" for MI = 0:

Code: Select all

123456789
214365897
341578926  * known band (#3 of 67) for MI = 0
438197265
567932418
695784132
786219543
879621354
952843671


Cheers,
MM

[Serg]

Hi, Mathimagics!
At last I understood your method, please excuse me for my multiple questions on this theme.
All is OK. If you get at least one completion to full LS for band with MI = 0, then there exist ED LS with this first band. Otherwise (no completions to full LS), we can be sure that any LS with given first band has not minimal minlex form, so given band cannot be found among 19 billions of ED LS.

Thanks for clarification!

Serg

[1to9only]

I've written some generic code to calculate minlex/maxlex for classical sudokus. By 'generic', I mean the code should (easily) convert to work with other sudoku sizes!
At present, I'm converting the code (for classic sudokus) to work with latin squares.

Code: Select all

1234.....4...............56234.....................56734...............5.....5678 backcirculant


BC as classic sudoku:

Code: Select all

.................1.....2.....1.....3..3.1...4..4.3..15.2...6....6...72...7.2.86.. minlex
9876.....6..............54.876............435.........76...........5.324.......5. maxlex


BC as latin square:

Code: Select all

.................1.......12......123.....1234....5.......56......567.....5678.... minlex
9876.....876......76.......6............5432.....432......32.......2............. maxlex


Can someone/anyone confirm that my outputs are correct? Thanks.

[Serg]

Hi, 1to9only!
At the moment I can confirm only "BC as classic sudoku" in Minlex form. Very fast LS canonicalization algorithm, which is discussed in this thread, is only applicable to complete Latin Squares, not for LS puzzles (partially filled LS).

What algorithm do you use? How fast is your program? What programming language do you use?

Serg

[1to9only]

Hi Serg,

Thanks for taking the time. I can check my minlex output against output from other programs: dclamage's, and kaityo256's or kaityo256's with my modifications.
Paquita posts grids in maxlex form on the hardest sudokus thread, and my maxlex output checks out. I think my minlex/maxlex code is working correctly, but want the LS minlex/maxlex independently verified.

[Updated] BackCirculant from 1st post:

Code: Select all

1234.....4...............56234.....................56734...............5.....5678 backcirculant
123456789456789123789123456234567891567891234891234567345678912678912345912345678 solution
123456789231564897312645978456789231564897312645978123789231564897312645978123456 lcf (in later posts)


BC as classic sudoku:

Code: Select all

.................1.....2.....1.....3..3.1...4..4.3..15.2...6....6...72...7.2.86.. minlex
9876.....6..............54.876............435.........76...........5.324.......5. maxlex


BC as latin square:

Code: Select all

.................1.......12......123.....1234....5.......56......567.....5678.... minlex [*]
9876.....876......76.......6............5432.....432......32.......2............. maxlex [*]


What algorithm do you use? How fast is your program? What programming language do you use?

Nothing fancy as discussed here, and elsewhere. No sets, no tables, no arrays. Except for 2 arrays for row and column indexes for cells! For my program to be portable to other sudoku sizes, I just iterate over all stacks, columns within stacks, bands, rows within bands, then rotate grid and re-iterate. For latin squares, it's just columns and rows, rotate and redo. The programs also work on solution grids. The current code is multi-threaded. The LS minlex code is 'portable' - 8 lines changed make it maxlex, and 5 lines changed for (declaring) a new grid size.

OP posted some non-9x9 LSs:

Code: Select all

1234....234.....34......4......................5......56.....567 8x8 16 clues
...............1......12.....123....1234...5......56.....567.... minlex [*]
8765....765.....65......5...........432.....32......2........... maxlex [*]

123....23.....3...................4.....45....456 7x7 12 clues
.............1.....12....123...4.....45....456... minlex [*]
765....65.....5.........432....32.....2.......... maxlex [*]

123...23....3................4....45 6x6 9 clues
...........1....12...123..4....45... minlex [*]
654...54....4........32....2........ maxlex

12...2.............3...34 5x5 6 clues
.........1...12..3...34.. minlex [*]
54...4......32...2....... maxlex

12..2..........3 4x4 4 clues
.......1..12.3.. minlex [*]
43..3.....2..... maxlex


I don't think my programs are as fast as some of the figures (LS/sec) quoted in this thread. But they are fast enough for my purposes. I'm not really into program speeds (i.e. I don't spend (waste) too much time doing timings!), just want the programs to work (correctly)! I posted my minlex/maxlex programs (Windows exes only, no source) on github (links below), the programs are single-thread, the timings shown below are for running the program on BC grid in a text file.

BC as classic sudoku, using 9,216 bytes minlex/maxlex programs:

Code: Select all

.................1.....2.....1.....3..3.1...4..4.3..15.2...6....6...72...7.2.86.. minlex: 25 ms
9876.....6..............54.876............435.........76...........5.324.......5. maxlex: 183 ms


BC as classic sudoku, using 172,544 bytes minlex/maxlex programs:

Code: Select all

.................1.....2.....1.....3..3.1...4..4.3..15.2...6....6...72...7.2.86.. minlex: 11 ms
9876.....6..............54.876............435.........76...........5.324.......5. maxlex: 60 ms


All 'C' programs.

[Edit: 2024/01/28] Some of the grids have been corrected (bugs in my programs!). These are marked with [*]