The New Sudoku Players' Forum

[swb01]

I would like to thank the commenters on my March 7,2021 post - "Equivalence Sets for Completed Grids of 17 Clue Puzzles." Before that, I wasn't aware of the row-based MinLex process and its role in identifying essentially equivalent puzzles and full grids. I used an unavoidable set process to identify the equivalence sets described in my previous post.
So I wrote a couple of routines to derive MinLex forms for clues and full grids and used Gordon Royle's list of 49157 puzzles as a part of my code verification process.

I was surprised to find 339 17C entries that appear to not be in MinLex form, documented in the attached text file. I confirmed that the apparently smaller puzzles do not match any other puzzle in the list, so the count of 49,157 doesn't change.

I also noticed that an updated 17 Clue list has been posted to https://sites.google.com/site/dobrichev ... ollections:
(Gordon Royle's list of 49158 puzzles as of March 25, 2021). It raises another question. The new puzzle is inserted into the list at #48862 as:

........1.....2.3...4..5..6........3.1..7....87.............8.....81..7.52.......

On March 8, coloin responded to my previous post and included the new 17C puzzle as: (Thank you coloin)

"........1.....2..3.45.............1...6.....237..6.......1..4.....2.35...8.......#49158

Yes the solution grid with the 29 puzzles was termed the SF grid .... [Strangely familiar !]
coloin, Posts: 2012, Joined: 05 May 2005"

My routine confirms that entry #48862 in the new list has coloin's smaller representation with the following transformations:
Transposition first = Yes, Digit Order = 356847219, Row Order = 456789123, Column Order = 132645978.

Am I misunderstanding anything here?

[Mathimagics]

dobrichev inserted the puzzle in what was thought to be its minlex order position, based on current puzzle minlex function.

Recently, coloin found that smaller minlex form for the same puzzle. So it seems that the puzzle minlex function has some sort of problem, which I believe is being investigated ...

[Mathimagics]

Hmmm, I had told coloin previously that I did not have a minlex function for puzzles, but it turns out that I did, after all.

And while that function is terribly slow, it is guaranteed to get the right answer !

So, I ran it against Mladen's 49158 17-clue puzzle set, and found that 1505 of those puzzles are NOT minlex. So there is definitely a bug in GridChecker (subcanon.cpp) ...

[coloin]

Hmmm ... i thought the fault [ which is in both gsfs and dobrichevs programs] was confined to puzzles with 27+ clues with all rows having 3 or more clues
but now it seems it is more widespread. The fact that both programs have the same bug and consistantly give an identifying version of the puzzle has meant that we were oblivious !
I spoke to dobrichev - he seemed to think it was the buffer was exceeeded but this may well not be the case here !!.

The initial puzzle #49158 was found [and obviously minlexed] by blue, gsf's program and dobrichev's do give a "larger" version ...after all this time - well spotted !!!

Code: Select all

sudoku-64 -f%#mc
........1.....2..3.45.............1...6.....237..6.......1..4.....2.35...8.......
........1.....2.3...4..5..6........3.1..7....87.............8.....81..7.52.......

[Mathimagics]

.
In 1190 of those 1505 cases, the correct puzzle has a minlex pattern that is greater than the reported puzzle's pattern, and so that made me wonder whether GridChecker was choosing a minlex pattern, and then "normalising" the clues ...

But in the other 315 cases, including the one that you (coloin) first found, the correct minlex puzzle has a pattern that is also less than that of the reported puzzle.

Perhaps I can put some effort into making my function a little faster, without sacrificing its accuracy ... it took an hour to do those 49158 puzzles ...

If the problem is deep in the entrails of Mike Deverin's original code (and not a simple buffer size problem), then an alternative function might be useful ...

[coloin]

indeed ... im sure dobrichev will have the explanation soon !!!
but it might be that the minlex puzzle of the minlex pattern could be a simpler format to use, except we have used the minlex puzzle albeit flawed for a long time now !!

[dobrichev]

One good and several not so good news from me.

The good news is that despite the bugs, Deverin's code is beleived to be deterministic. This means it assigns unique canoinical representation of a particular subgrid and all its morphs.

The representation is expected to be minlex but it actually isn't - this is a bug.
GSF's implementation possibly has "improvements" over original code.
My implementation is based on GSF's and has few more "improvements".
This large portion of actually non-minlex puzzles is surprising me. Are all wrong canonicalizations for 17-clue puzzles reproducible on both gridchecker and gsf's solver?
The algorithm is based on several wrong assumptions sort of "no such distribution exists". It is known from years.
All the above is a big problem only for those, who search for actual minlex forms

I found better to use pattern minlex representation for puzzles and subgrids. For published puzzle sets I am avoiding it because I have no independent process to compare mine results to. In other words I can easily introduce a bug and nobody will see it.

Finally, the list of 17s was updated weeks ago, but when I was pushed to migrate from "classic google sites" to "new google sites" the conversion procedure did a mess, and now I have to rebuild the site. At the moment the published list doesn't exist.

I have no time for sudoku at the moment. I will be glad if you provide better algorithms. And don't forget canonicalization of pencilmarks

[swb01]

Well, apparently I have more work to do ... I only found 339 cases and there are 1505!

I wrote my minlex routine as a coding exercise. It's rather intuitive and straight forward, not optimized for speed. In its current less than fully accurate form, it takes 3 minutes to process the 49158 17C puzzles on a 2.80 GHz laptop. It does a little more work in keeping track of digit, row and column permutations, but that shouldn't cost much process time. In case some readers might be interested, here is a brief overview of the routine:
For each puzzle, it starts by counting row/stack and column/band non-zeros. Then it determines the minimal row and column values based on the non-zero "right-justified" patterns using this table:

Code: Select all

000   {0,0,0,0,0,0,0,0,0}
001   {0,0,0,0,0,0,0,0,1}
002   {0,0,0,0,0,0,0,1,2}
003   {0,0,0,0,0,0,1,2,3}
011   {0,0,0,0,0,1,0,0,2}
012   {0,0,0,0,0,1,0,2,3}
013   {0,0,0,0,0,1,2,3,4}
022   {0,0,0,0,1,2,0,3,4}
023   {0,0,0,0,1,2,3,4,5}
033   {0,0,0,1,2,3,4,5,6}
111   {0,0,1,0,0,2,0,0,3}
112   {0,0,1,0,0,2,0,3,4}
113   {0,0,1,0,0,2,3,4,5}
122   {0,0,1,0,2,3,0,4,5}
123   {0,0,1,0,2,3,4,5,6}
133   {0,0,1,2,3,4,5,6,7}
222   {0,1,2,0,3,4,0,5,6}
223   {0,1,2,0,3,4,5,6,7}
233   {0,1,2,3,4,5,6,7,8}
333   {1,2,3,4,5,6,7,8,9}


If row and column minimums are equal, then direct and transposition passes are required, otherwise just one pass is needed. For each pass, for each of the 1,296 stack/column permutations it uses the identified first-row non-zero positions to qualify candidates for full row checking. Then each band and each band row are permuted and positionally checked against the previously identified minimum at each step, stopping the drill-down if found to be positionally greater. If a candidate survives to the 9th row, digits are relabeled and the grid is compared to the previously identified minimum. Replacing the previously identified minimum if smaller.

[JPF]

In a way, I should plead guilty.

I mentioned this error to Mladen via private message in December 2014.
At that time, I had found 1504 errors for the MinLex of the 49157 17 clue-puzzles (compared to those calculated by my personal program which had lasted a night…).
The errors were found identically in gsf' program and in gridchecker.
Mladen recognized the bug for obtaining the MinLex of a puzzle, but told me he was sure that the result f given by these programs was a canonical form, therefore : f (P) = f (Q) if and only if P and Q are two "equivalent" puzzles.
Which was a sufficient tool for me at the time.
I have never encountered any problems in its intensive use in the Patterns Game where it is necessary to eliminate a large number of non ed puzzles.

Since then, this question completely disappeared from my mind and I had subconsciously thought that Mladen had fixed this bug, until recently I had this absurd idea to post topics relating to MinLex puzzles and patterns!

Anyway, I want to thank Mladen for all his helpful and super fast programs.

JPF

[Mathimagics]

This large portion of actually non-minlex puzzles is surprising me. Are all wrong canonicalizations for 17-clue puzzles reproducible on both gridchecker and gsf's solver?

Yes, I get identical results from both gsf sudoku tool and gridchecker, for the 17c puzzle set ...

At that time, I had found 1504 errors for the MinLex of the 49157 ...

Now he tells us ...

And it gets blue's puzzle number 49158 wrong too, for a total of 1505

[swb01]

What a strange way to get heavyweight, timely debugging help. I fixed my bug - skipping over quite a few row/band permutations. Now it finds 1505 non-minlex cases in 16 minutes 30 seconds.

[Serg]

Hi, swb01!
Just to compare your program performance with dobrichev's gridchecker - please run gridchecker on your computer for all 17-clue puzzles canonicalization:

gridchecker --similar --subcanon <input_file >output_file

How long time does gridchecker need to process all those puzzles?

Serg

[coloin]

How long time does gridchecker need to process all those puzzles?

Program performance .... speed isn’t everything as gridchecker has le bug !!
It seems both gsfs program and gridchecker give up when the puzzle doesnt have an obvious empty row
That would explain the speed...
As has been pointed out - they still offer reliable canonical identification

[swb01]

Serge wrote:
Just to compare your program performance with dobrichev's gridchecker - please run gridchecker on your computer for all 17-clue puzzles canonicalization:

My routine is rather pedestrian in the performance arena, nowhere close to what's needed to canonicalize a large number of puzzles. I used a 2.80 MHz laptop and converted all 49158 17C puzzles in 16 minutes and 30 seconds. Performance wise, it surely helps that most of the puzzles were already in minlex form. It will minlex any grid with zero to 81 givens (the givens do not have to be in valid SuDoKu form, just digits 0 - 9) with high numbers of givens taking significantly longer. My Full Grid minlex routine requires valid SuDoKu grids and processes much faster than the Clue minlex routine with 81 givens. My full grid routine also tracks digit/row/column mappings and, if clues are highlighted on the full grid, shows the transformed set of clues.

[coloin]

This is currently the"largest" found minlex [minimal] puzzle ...

Code: Select all

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

perhaps you could confirm with your program that it is actually minlex !!!