The New Sudoku Players' Forum

[Serg]

Hi, colleagues!
Does anyone know the way to canonicalize given pattern? I use gsf's "sudoku" tool to canonicalize puzzles, but I don't know how to canonicalize patterns by means of this tool. Maybe any else tool is available. Please, help.

Serg

[champagne]

Hi Serg

I am sure gsf or ronk knows how to do that using gsf's program
I am suspecting gridchecker (contatct dobrichev through pm) can do it as well, but I only used the "pattern mode" option

I have also a canonicalization process, delivering a maxtext canonical form performing well.
If you have no other answer or if you need a high speed process, i can arrange to give you the exec file (PC) and the command line to use

champagne

[ronk]

Does anyone know the way to canonicalize given pattern? I use gsf's "sudoku" tool to canonicalize puzzles, but I don't know how to canonicalize patterns by means of this tool.

gsfsudoku -f%#xc file.dat

... where file.dat contains standard line-formatted puzzles. "Comments" following the puzzle must be removed. Appending these comments to each canonicalized pattern is a bit tougher, but can usually be done too.

[Serg]

Hi, champagne!

Hi Serg

I am sure gsf or ronk knows how to do that using gsf's program
I am suspecting gridchecker (contatct dobrichev through pm) can do it as well, but I only used the "pattern mode" option

I have also a canonicalization process, delivering a maxtext canonical form performing well.
If you have no other answer or if you need a high speed process, i can arrange to give you the exec file (PC) and the command line to use

champagne

Thank you for your help. Please, take into account that patterns should be processed. So, input (for alone pattern) should contain a sequence of 81 symbols "." or "X" ("." denotes free cell, "X" denones cell containing clue), or other two-symbols patterns representation.

Speed is not sufficient. I need a tool to cross-check my own pattern generator. It would be fine if you could give me you tool as exec file (MS Windows PC) .

Serg

[Serg]

Hi, ronk!

Does anyone know the way to canonicalize given pattern? I use gsf's "sudoku" tool to canonicalize puzzles, but I don't know how to canonicalize patterns by means of this tool.

gsfsudoku -f%#xc file.dat

... where file.dat contains standard line-formatted puzzles. "Comments" following the puzzle must be removed. Appending these comments to each canonicalized pattern is a bit tougher, but can usually be done too.

Thank you for your reply. I am using gsf's "sudoku" tool mainly for canonicalization of puzzles just in the same mode as you mentioned. But I don't know how to present correctly pattern as input. Format like "XXX.....X...X ..." sudoku tool doesn't understand.

Serg

[ronk]

Format like "XXX.....X...X ..." sudoku tool doesn't understand.

Revisit gsf's post to you here. If the result is correct, albeit with '/'s instead of 'X's, there might be a command-line option to use 'X's instead. Patterns in line-format is OK.

[coloin]

As ronk says
sudoku-64 -f%#xc gives the minlex pattern [ with xx.x.xx.xxx...]
looking at the manual

#X: Like #x, but list original puzzle in row order minlex canonical order.

so try sudoku-64 -f%#Xc
ah ha this works - except it just needs to be relabeled ..... ?
ah ha
which can be done with a very quick
sudoku-64 -f%#Pc

#P: Row order pattern minlex canonical.

pity i didnt know this untill now !!

and for completeness the minlex puzzle is
sudoku-64 -f%#mc

which frequently can be the same but usually isnt the same as minlexpatternpuzzle

C

[dobrichev]

gridchecker --similar --subcanon < in > out

or

gridchecker --similar --puzzles in --mspuzzles out

The second command removes duplicates and orders the list. Applicable for several millions of puzzles in the list.

Input is '11...11.1.1', just use the same number for all givens and 0 or not a number for non-givens. Extra chars are ignored.
Output is '1' and '.'.

BTW it was fun this night near Sofia. 19 earthquakes starting with 5.7 at 3:00AM and still counting.

Cheers,
MD

[Serg]

Hi, colleagues!
Thanks to ronk, he reminded me about gsf's post in the thread "How to calculate number of pattern's automorphisms?" at setbb.com/sudoku forum. I have no access to this forum, but but but... I used some trick to circumvent this limitation. I searched for "setbb.com/sudoku" at www.google.com site. Then I clicked on link "translate into Russian". Now I can see setbb.com/sudoku forum start page in Russian. I am clicking on button "original" and can see forum's start page in English (links in that page work well).

So, I looked at gsf's post in the thread "How to calculate number of pattern's automorphisms?" and started with experiments.

It turns out that input file containing patterns must look like this (sample file contains 4 patterns):

Code: Select all

#!exemplar
.................X..X..X...................XX..X..X...XXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXX.................X..X..X..................XX...X..X...
.................X..X..X.................X.....X....XXXXXXXXXXXXXXXXXXXXXXXXXXXXX
.................X..X..X..........XX.....X.....X......XXXXXXXXXXXXXXXXXXXXXXXXXXX


As you can see it is necessary to add first string "#!exemplar".
Symbol "X" denoting cell with clue can be replaced by "/", but it is not necessary. Other representations such as "1" - for clue cells and "." - for empty cells, or "1" for clue cells and "0" - for empty cells - don't work.

We can use command line "sudoku -f%#xc input-file >output-file" to obtain result (if this command line is used in Windows bat-file, symbol "%" must be replaced by "%%"). Here is result of tool's running:

Code: Select all

.................X..X..X...................XX..X..X...XXXXXXXXXXXXXXXXXXXXXXXXXXX
.................X..X..X..................XX...X..X...XXXXXXXXXXXXXXXXXXXXXXXXXXX
.................X..X..X.................X.....X....XXXXXXXXXXXXXXXXXXXXXXXXXXXXX
.................X..X..X..........XX.....X.....X......XXXXXXXXXXXXXXXXXXXXXXXXXXX


It looks like right minlex form.

Other variants of command line (proposed by coloin), like "sudoku -f%#Xc input-file >output-file" or "sudoku -f%#Pc input-file >output-file" unfortunately didn't work.

Colleagues, thank you all for your help and patience.

Serg

[Edited: I corrected typos.]

[Serg]

Hi, Mladen!

gridchecker --similar --subcanon < in > out

or

gridchecker --similar --puzzles in --mspuzzles out

The second command removes duplicates and orders the list. Applicable for several millions of puzzles in the list.

Input is '11...11.1.1', just use the same number for all givens and 0 or not a number for non-givens. Extra chars are ignored.
Output is '1' and '.'.

Thank you very much for your reply. I am keeping your info in mind. I am sure I'll use your great tool in some time (I see many people say your tool has excellent performance).

BTW it was fun this night near Sofia. 19 earthquakes starting with 5.7 at 3:00AM and still counting.

Thanks for interesting link. Did you feel real quake near Sofia?

Serg

[dobrichev]

Hi Serg,

I just implemented Michael Deverin's puzzle canonicalization algorithm from 2007 which doesn't care about puzzle validity and as a side effect is capable to canonicalize patterns. From this perspective it is not optimal for pattern canonicalization. I will be happy if somebody spend some time in removal of the unnecessary relabeling loops from the original code, extend it to finding pattern automorphisms, test it, and eventually publish the source code

The epicenter of the earthquakes was in 10 - 20 kilometers from Sofia and they were felt in all their power. Some people left their homes and sleep in their cars. 4 - 5 shocks were strong enough to rouse you from sleep and all citizens were with red eyes in the next day. The first quake prolonged about 2 minutes. No serious damages.

[Serg]

Hi, Mladen!
I've just tried your gridchecker (v. 1.15) for canonicalization a bunch of patterns. It works fine and more faster than gsf's "sudoku" tool (I mean patterns' canonicalization function only.). It took me typically minutes to canonicalize 500 patterns by "sudoku" tool, but your gridchecker did it for less than second. Nice tool! Well done.

Serg

[coloin]

Sorry it didnt work for you - not sure why
On re-reading I appreciate that you just want the min lex pattern.

Anyway - this is what it does for me....

Code: Select all

random puzzle - test.txt
9..46....5.......714..5..9.6..8....9..2...5..8....1..4.6..8..453.......1....72..8

minlex pattern
sudoku-64 -f%#xc test.txt 
........X..X..X....X.XXXXX.........X..X..X...XXX.X.XX....X...X.X.....X..X.XX.X... 

puzzle with minlex pattern
sudoku-64 -f%#Xc test.txt > test1.txt
........2..6..4....3.95186.........5..4..9...815.7.49....4...8.2.....1..7.86.5...

puzzle with minlex pattern with minlex clues
sudoku-64 -f%#Pc test1.txt
000000001002003000040567820000000006003005000876090350000300080100000700908206000

minlex puzzle
sudoku-64 -f%#mc test.txt
000000001002003000040561230000000007003008000215900860000070050300000600801046000

puzzle with representative from its minlex solution grid
sudoku-64 -f%#0c test.txt
020450700000100006089200000200300007000004090001500002000800004570000003040030501

note the minlexpatternminlexpuzzle is different from the minlex puzzle [this rattles my brain without the earthquakes ]

perhaps to be useful the output for the minlex pattern with minlex clues should be combined - then the puzzles with the pattern could be sorted.
eg x..x...x..xx # 1..2...3..45

I will try dobrichev's program ...... it could well do just that

Edit

Code: Select all

gridchecker --similar --subcanon < test.txt > test2.txt
9..46....5.......714..5..9.6..8....9..2...5..8....1..4.6..8..453.......1....72..8   ........1..2..3....4.56123.........7..3..8...2159..86.....7..5.3.....6..8.1.46...

Well this is the minlex puzzle ........ not to be confused with ......... the minlex pattern

C

[coloin]

7 puzzles with the same pattern

Code: Select all

.2..7.1..5....4..3..........7....82...13........5.....6...8..7.3..9............8.
.4..7.1..5....6..3..........7....82...13........5.....6...8..7.3..2............9.
.4..7.1..5....6..3..........7....82...83........5.....6...8..7.3..2............4.
.8..4.1..5....6..3..........4....82...13........5.....6...8..7.3..2............4.
.8..4.1..5....7..3..........4....82...13........5.....6...8..7.3..2............4.
.8..7.1..5....4..3..........7....28...13........5.....6...8..7.3..2............2.
.8..7.1..5....4..3..........7....82...13........5.....6...2..7.3..4............8.

Code: Select all

gridchecker --similar --subcanon < test3.txt > test3a.txt
...........1..2..3.4..5..6.......1...6.47....5.....2.....7.......2...8....96...7.
...........1..2..3.4..5..6.......1...6.78....5.....2.....9.......2...7....36...8.
...........1..2..3.4..5..6.......1...5...72...6.8........4.......2...8.77..6.....
...........1..2..3.4..5..6.......1....2.4.7..8...6.........18.25........6..3.....
...........1..2..3.4..5..6.......1....2.7.4..8...6.........18.25........6..3.....
...........1..2..3.4..5..6.......1...6.47....5.....2.....7.......2...7....86...4.
...........1..2..3.4..5..6.......1...6.5......7...82.....4.......2...8.13..6.....  *** same as below

Code: Select all

sudoku-64 -f%#mc test3.txt
000000000001002003040050060000000100060470000500000200000700000002000800009600070
000000000001002003040050060000000100060780000500000200000900000002000700003600080
000000000001002003040050060000000100050007200060800000000400000002000807700600000
000000000001002003040050060000000100002040700800060000000001802500000000600300000
000000000001002003040050060000000100002070400800060000000001802500000000600300000
000000000001002003040050060000000100060470000500000200000700000002000700008600040
000000000001002003040050060000000100060500000070008200000400000002000801300600000  *** same as above

sudoku-64 -f%#Xc test3.txt
...........1..2..7.3..5..4.......5.....1..3..2.8..7.......3.9..8........7...6...8
...........1..4..7.3..5..6.......5.....1..3..2.8..7.......3.2..9........7...6...8
...........1..4..7.3..5..6.......5.....8..3..2.8..7.......3.2..4........7...6...8
...........1..8..4.3..5..6.......5.....1..3..2.8..4.......3.2..4........7...6...8
...........1..8..4.3..5..7.......5.....1..3..2.8..4.......3.2..4........7...6...8
...........1..8..7.3..5..4.......5.....1..3..8.2..7.......3.2..2........7...6...8
...........1..8..7.3..5..4.......5.....1..3..2.8..7.......3.4..8........7...6...2

sudoku-64 -f%#Xc test3.txt > test4.txt

sudoku-64 -f%#Pc test4.txt
000000000001002003040050060000000500000100400207003000000040800700000000300090007
000000000001002003040050060000000500000100400708003000000040700900000000300060008
000000000001002003040050060000000500000700400807003000000040800200000000300060007
000000000001002003040050060000000500000100400702003000000040700300000000800060002
000000000001002003040050060000000500000100400702003000000040700300000000600080002
000000000001002003040050060000000500000100400207003000000040700700000000300080002
000000000001002003040050060000000500000100400702003000000040600200000000300080007

changing all the clues to 1 of course gridchecker gives us the minlex pattern

Code: Select all

...........1..1..1.1..1..1.......1.....1..1..1.1..1.......1.1..1........1...1...1

C

[Serg]

Hi, coloin!
Unfortunately it is quite possible, that 2 puzzles having equivalent patterns will have not coinciding minlex form patterns. I think it is a property of minlex metric itself. Maybe one can invent another metric, giving forms with the same patterns for all puzzles having equivalent patterns.

Let's consider puzzle number 1 and puzzle number 3 from your 7 puzzles sample set.

Code: Select all

gridchecker --similar --subcanon < test3.txt > test3a.txt
...........1..2..3.4..5..6.......1...6.47....5.....2.....7.......2...8....96...7.
...........1..2..3.4..5..6.......1...6.78....5.....2.....9.......2...7....36...8.
...........1..2..3.4..5..6.......1...5...72...6.8........4.......2...8.77..6.....
...........1..2..3.4..5..6.......1....2.4.7..8...6.........18.25........6..3.....
...........1..2..3.4..5..6.......1....2.7.4..8...6.........18.25........6..3.....
...........1..2..3.4..5..6.......1...6.47....5.....2.....7.......2...7....86...4.
...........1..2..3.4..5..6.......1...6.5......7...82.....4.......2...8.13..6.....


Here are these puzzles in minlex form:

Code: Select all

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


Let's now transform puzzle N3 to puzzle N1 (I consider one possible way only).

Code: Select all

        N3: swap rows r2/r3 and columns c2/c3, c5/c6, c8/c9
+-----+-----+-----+
|. . .|. . .|. . .|
|. . 4|. . 5|. . 6|
|. 1 .|. 2 .|. 3 .|
+-----+-----+-----+
|. . .|. . .|1 . .|
|. . 5|. 7 .|2 . .|
|. . 6|8 . .|. . .|
+-----+-----+-----+
|. . .|4 . .|. . .|
|. 2 .|. . .|8 7 .|
|7 . .|6 . .|. . .|
+-----+-----+-----+

        N3: swap stacks B258/B369
+-----+-----+-----+
|. . .|. . .|. . .|
|. . 4|. . 6|. . 5|
|. 1 .|. 3 .|. 2 .|
+-----+-----+-----+
|. . .|1 . .|. . .|
|. . 5|2 . .|. 7 .|
|. . 6|. . .|8 . .|
+-----+-----+-----+
|. . .|. . .|4 . .|
|. 2 .|8 7 .|. . .|
|7 . .|. . .|6 . .|
+-----+-----+-----+

        N3: swap bands B456/B789
+-----+-----+-----+
|. . .|. . .|. . .|
|. . 4|. . 6|. . 5|
|. 1 .|. 3 .|. 2 .|
+-----+-----+-----+
|. . .|. . .|4 . .|
|. 2 .|8 7 .|. . .|
|7 . .|. . .|6 . .|
+-----+-----+-----+
|. . .|1 . .|. . .|
|. . 5|2 . .|. 7 .|
|. . 6|. . .|8 . .|
+-----+-----+-----+

        N3: relabel: 4 -> 1, 6 -> 2, 5 -> 3, 1 -> 4, 3 -> 5, 2 -> 6, 8 -> 7, 7 -> 8
+-----+-----+-----+
|. . .|. . .|. . .|
|. . 1|. . 2|. . 3|
|. 4 .|. 5 .|. 6 .|
+-----+-----+-----+
|. . .|. . .|1 . .|
|. 6 .|7 8 .|. . .|
|8 . .|. . .|2 . .|
+-----+-----+-----+
|. . .|4 . .|. . .|
|. . 3|6 . .|. 8 .|
|. . 2|. . .|7 . .|
+-----+-----+-----+


So, you can see that puzzle N3 after transformation has higher minlex metric than original N3.

Serg

[Edited: I changed phrase "the same essentially different patterns" to "equivalent patterns".]