The New Sudoku Players' Forum

[swb01]

I rewrote my puzzle minlexer to speed it up. For a test file, I randomly scrambled the digits, bands/rows, stacks/columns and randomly transposed each of the 49,158 17C puzzles. It can now minlex this test file in 9 seconds on a 2.80 GHz laptop.
The only SuDoKu-based assumption the routine uses is it assumes no stack permutations are possible past row 4. Otherwise, it will minlex any 9x9 grid containing digits 0 to 9, valid SuDoKu or not (I think). For example, provide no clues and it makes 3,359,232 possible minimum tests and provides a zero array as the minlex form. An example of a valid 20 clues might take 45 tests to identify the minlex. Another example with a full grid set of clues (all 81 cells filled in) the routine minlexes it with 54 tests (this might be faster than my Grid minlexer). The number of tests required varies depending on the particular arrangement of the clues.
I would like to test this routine on a wider set of cases, 18s and larger and covering more patterns. If anyone can provide me with a reference for suitable set of puzzles, I'd appreciate it.
Also, how does the 9 second processing time stack up against fast minlexers?
Also, if anyone knows of a valid puzzle with all zeros in stacks 1 and 2 through row 4, please let me know and I'll remove that assumption.

[JPF]

Is it this you are looking for?

Code: Select all

+---+---+---+
|...|...|123|
|...|...|.45|
|...|...|...|
+---+---+---+
|...|...|.31|
|6..|...|78.|
|9.7|.5.|...|
+---+---+---+
|2..|6..|...|
|36.|29.|...|
|89.|57.|...|
+---+---+---+


JPF

[Serg]

Hi, swb01!
Your timing for minlexing 49158 17-clue puzzles is rather good, but I think it's not sufficient to call your minlexer fast. Gridchecker processes these puzzles in 0.556 sec (on my rather old notebook with Intel Centrino CPU). So, you should fit in 1 second at least before discussing speed of your minlexer.

Minlexed puzzles must not be valid. I think they must obey Sudoku rules (digits "1"-"9" or "0" for empty cells, no repeating digits in rows/columns/boxes) only, empty puzzle (w/o clue digits) should be correctly processed.

It's essential that speed of minlexing depends on number of clues. There is very fast Michael Deverin's minlexing algorithm for 81-clue puzzles (Sudoku solution grids). Of course, universal algorithm (for arbitrary number of clues) cannot be so fast for solution grids minlexing, but it should be comparable in speed. I think, we should check speed of any minlexer for 3 bunches of puzzles - 17-clue, 81-clue and intermediate (say, 24-clue) puzzles.

For very fast minlexers read/write time of puzzles can be comparable with time of minlexing itself. So, timing program should read 10000 puzzles, minlex those puzzles 100 times and report time of minlexing.

Serg

[swb01]

Jpf wrote: Is it this you are looking for?

Thanks. There goes that assumption! I'll just take it out, and I don't think it will change the timing much.

Serge wrote: Your timing for minlexing 49158 17-clue puzzles is rather good, but I think it's not sufficient to call your minlexer fast.

Serg, thanks for your info, now I have some reference points - not that I think I can speed it up much more.

Serge wrote: Minlexed puzzles must not be valid. I think they must obey Sudoku rules (digits "1"-"9" or "0" for empty cells, no repeating digits in rows/columns/boxes) only, empty puzzle (w/o clue digits) should be correctly processed.

Did you mean to say "must be valid?' I assume the the minlexer routines being discussed do not include validating that the puzzles are valid or minimal. Is that correct?

Serge wrote: For very fast minlexers read/write time of puzzles can be comparable with time of minlexing itself. So, timing program should read 10000 puzzles, minlex those puzzles 100 times and report time of minlexing.

I didn't think about minlexing the same puzzles 100 times. (I would prefer to minlex 100,000 puzzles if I could find a source for them. Of course that would increase the I/O component.)
On "Report the time of minlexing." I understand this to mean "exclusive of read time." Is that correct? Are they written back out in their minlex form?

[Serg]

Hi, swb01!

Serge wrote: Minlexed puzzles must not be valid. I think they must obey Sudoku rules (digits "1"-"9" or "0" for empty cells, no repeating digits in rows/columns/boxes) only, empty puzzle (w/o clue digits) should be correctly processed.

Did you mean to say "must be valid?' I assume the the minlexer routines being discussed do not include validating that the puzzles are valid or minimal. Is that correct?

People at this forum usually mean that "valid puzzle" is a puzzle obeing Sudoku rules and having unique solution. I meant Sudoku puzzles minlexer must correctly process a puzzle no matter has this puzzle any/one/multiple solutions. Maybe we should use the term "correct" for puzzles obeing Sudoku rules. I think minlexer routine should not check minlexing puzzle for having any/one/multiple solutions and for minimality.

Serge wrote: For very fast minlexers read/write time of puzzles can be comparable with time of minlexing itself. So, timing program should read 10000 puzzles, minlex those puzzles 100 times and report time of minlexing.

I didn't think about minlexing the same puzzles 100 times. (I would prefer to minlex 100,000 puzzles if I could find a source for them. Of course that would increase the I/O component.)
On "Report the time of minlexing." I understand this to mean "exclusive of read time." Is that correct? Are they written back out in their minlex form?

It's not principal - to repeat minlexing (100 times) or not. But we should know time of pure minlexing, without read/write times.

Usually authors of such routines prepare those routines for embedding to other programs, so reading raw puzzles, writing results and timing should not be included into routine itself, but should be implemented as separate routines (to simplify embedding of minlexing routine to other programs).

Serg

[coloin]

I think it needs to be pointed out that gridchecker has a bug which means the output of some puzzles arnt actually minlex [presumably this shortcut makes it faster]
Is your program available for others ?

[swb01]

Serge, Thank you for clarifying this. I'm now thinking "service subroutine" for my time checks.
I clocked the file I/O time with no processing for the 49158 17C .txt file at 1.361 seconds. That's for reading the records in and writing them out with a comma and 81 periods appended to each. The minleser timing run simply inserts a call to the minlex between each read and write. That leaves my minlexer subroutine time still in the 8 second range. This is for minlexing the scrambled 17Cs. Minlexing the already minlexed 17C's comes in around 5.5 seconds (after subtracting 1.362 seconds for I/O).

It sure would be nice to have one or more published benchmark tests for checking timing. The 17C's are not very representative for testing the general problem. For example, there are 20 different possible right justified first rows. The 17C's only cover two "000000000" and "000000001", and these, by themselves, don't necessitate stack or column permutations. Benchmark tests would include a description of the types of puzzles included (symmetric, all 18s, random, etc.), a test file of say 100,000 entries and a file of expected results. Some rules of the road would also be needed like requiring single threading.

coloin wrote: Is your program available for others ?

Hi coloin,
At this point it's not. For one thing, I need to do a lot more testing to verify accuracy, hence a need for a test bed. Also, I'm doing this as a hobby and haven't ventured into publishing. Maybe, if someone could advise me on how to safely produce a publicly available routine, I could produce one. I work with MS Visual Studio and Visual Basic.

[swb01]

Update on my minlexer performance. On my 2.80 GHz laptop, it can now minlex the 49158 scrambled 17C puzzles in just under 2 seconds after subtracting 1.3 seconds for I/O and I think I'm just about out of ideas for making it any faster.
As I mentioned, I think it will minlex any 9X9 grid with the only SuDoKu constraints being columns permute within their stacks and rows within their bands and the cells contain digits 0 - 9.
If I understand patterns correctly (and I don't know anything about patterns) it will minlex a pattern by replacing Xs with a single digit, say 1s.
For example, given the pattern: ..XX....X.X..X..X.X....XX..X....XX...X..X..X...XX....XX....XX...X..X..X...XX....X, submitting ..11....1.1..1..1.1....11..1....11...1..1..1...11....11....11...1..1..1...11....1 to the minlexer gives: ..1..1..1.1..1..1.1..1..1....1..1..1.1..1..1.1..1..1....1..1..1.1..1..1.1..1..1..
or ..X..X..X.X..X..X.X..X..X....X..X..X.X..X..X.X..X..X....X..X..X.X..X..X.X..X..X.. in 110 milliseconds which is much longer than a valid puzzle since, in this case, the program identifies 18 possibilities for the first row and checks out each one, finding that they all produce the identical minimum. Also, the 18 first row right-adjusted pattern causes the program to check out 6 different stack permutations for each candidate.
I'm still looking for a test bed of more varied puzzles on which to test my program. If anyone has a reference tof a suitable set, I'd appreciate it.

[Serg]

Hi, swb01!
You wrote:

As I mentioned, I think it will minlex any 9X9 grid with the only SuDoKu constraints being columns permute within their stacks and rows within their bands and the cells contain digits 0 - 9.

Please clarify - do you account for all VPTs (Validity Preserving Transformations)? There are 3,359,232 VPTs. Any of them is some combination of "primitive" transformations:

1. Transposing - 2 ways (including "Do nothing" transformation).
2. Permuting bands - 6 ways.
3. Permuting stacks - 6 ways.
4. Permuting rows in the first band - 6 ways.
5. Permuting rows in the second band - 6 ways.
6. Permuting rows in the third band - 6 ways.
7. Permuting columns in the first stack - 6 ways.
8. Permuting columns in the second stack - 6 ways.
9. Permuting columns in the third stack - 6 ways.

Serg

[swb01]

Thanks for the question Serg.

Serg wrote: Please clarify - do you account for all VPTs?

By "account for" I'm understanding: "if a VPT exists that yields a more minimal minlex, does my code find it." The answer is yes - it should by design. (However, I still haven't tested it on other than the 49158 17Cs and a few random cases.)

My April 21, 2021 Minlexer pretty much tests all permutations and it is slow.

My newest routine tests all VPTs that need to be tested to derive the minlex.

As an example, using the pattern above - ..XX....X.X..X..X.X....XX..X....XX...X..X..X...XX....XX....XX...X..X..X...XX....X
or

Code: Select all

+---+---+---+             +---+---+---+
|..X|X..|..X|             |..X|..X|..X|
|.X.|.X.|.X.|             |.X.|.X.|.X.|
|X..|..X|X..|             |X..|X..|X..|
+---+---+---+             +---+---+---+
|X..|..X|X..|     ==>     |..X|..X|..X|
|.X.|.X.|.X.|             |.X.|.X.|.X.|
|..X|X..|..X|             |X..|X..|X..|
+---+---+---+             +---+---+---+
|X..|..X|X..|             |..X|..X|..X|
|.X.|.X.|.X.|             |.X.|.X.|.X.|
|..X|X..|..X|             |X..|X..|X..|
+---+---+---+             +---+---+---+


First, a comment. The routine is a general purpose puzzle minlexer not a pattern minlexer, so it treats the Xs (or 1s) as distinct digits, thus it tries all of the combinations described below.

The routine first notices that there are 18 candidates for row1, 9 direct and 9 for the transposition. All candidates right justify (column permutation within stack) to |..X|..X|..X|. This first row pattern requires 6 stack permutations to account for all possibilities. After the first row, no further stack permutation are permitted since the stacks are fixed by the first row. The two possible second rows right justify to |.X.|.X.|.X.| which fixes further column permutations for rows 3 - 9. For rows 4 - 9, each row has one possibility from band 2 and one from band 3.

The row visit counts for the minlex are: 1: 108 (6X18), 2: 216, 3: 216, 4: 432, 5: 432, 6: 432, 7: 432, 8: 432, 9: 432, Total = 3,132.

[Serg]

Hi, swb01!
What do you say about such example of two-row configuration to be reduced to minlex form:

Code: Select all

..1 ..2 .34
.3. .56 .7.

Let permuting of the rows is prohibited. Is given form minlex?

About tests for minlexer. Below is so called "The Most Canonical Grid" (given in minlex form):

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 3 1|5 6 4|8 9 7|
|5 6 4|8 9 7|2 3 1|
|8 9 7|2 3 1|5 6 4|
+-----+-----+-----+
|3 1 2|6 4 5|9 7 8|
|6 4 5|9 7 8|3 1 2|
|9 7 8|3 1 2|6 4 5|
+-----+-----+-----+

It is very difficult for minlexing algorithms (I think, it is the worst case, because this puzzle has maximum (648) number of automorphisms).

Serg

[swb01]

Serg wrote: Let permuting of the rows is prohibited. Is given form minlex?
..1 ..2 .34
.3. .56 .7.

It looks minlexed to me even with a row permutation. What am I missing?

On minlexing the "The Most Canonical Grid." I scrambled it to
893624157157389246246715893938246571571893462462157938715938624389462715624571389
and minlexed it in 92 milliseconds confirming its 648 automorphisms with the following row visit counts:
1: 23,328, 2: 46,656, 3: 648, 4: 3,888, 5: 1,296, 6: 648, 7: 1,944, 8: 1,296, 9: 648, Total = 80,352

[Serg]

Hi, swb01!

Serg wrote: Let permuting of the rows is prohibited. Is given form minlex?
..1 ..2 .34
.3. .56 .7.

It looks minlexed to me even with a row permutation. What am I missing?

I wanted to say that pattern of minlex form depends on clue values. In this example the value of the cell r2c2 ("3") lead to minlex form's pattern

Code: Select all

..X ..X .XX
.X. .XX .X.

But two-row form

Code: Select all

..1 ..2 .34
.2. .56 .7.

is not minlex, because digit "7" may move to r2c9 cell.

On minlexing the "The Most Canonical Grid." I scrambled it to
893624157157389246246715893938246571571893462462157938715938624389462715624571389

Please, print final minlex form of MC grid. (What does this sequence of digits mean?)

Serg

[swb01]

Serg,

Thank you for the pattern of minlex example. In my previous post I substituted 1's for each X in a pattern and minlexed it. I think what you have pointed out is that process is not useful in the study of patterns. Is that right?

Serg wrote Please, print final minlex form of MC grid. (What does this sequence of digits mean?)

In order to give my minlexer some work, I randomly scrambled the digits, bands/rows, stacks/columns of the MC grid to get:
893624157157389246246715893938246571571893462462157938715938624389462715624571389
or

Code: Select all

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


then minlexed it back to the MC with the following transformations:
Transposition = No, Digits 123456789 => 743586912, Rows 123456789 => 132465897, Columns 123456789 => 123564789