Minlex Library (9x9)

Programs which generate, solve, and analyze Sudoku puzzles

Minlex Library (9x9)

Postby Mathimagics » Mon Feb 01, 2021 4:33 am

Here you will find attached my version of Michael Deverin's Minlex code.

A summary of my modifications/improvements over the original code can be found at the top of Minlex9.c

To compile the demo program:

  • gcc -O3 -o Demo.exe Demo.c Minlex9.c

The demo program shows how to call the library functions, and should produce the following output (example by JPF):

Code: Select all
.3.89......5.....4.17....5.9......8.....76....5.12............7...5.38.2..1.6...5 # Puzzle
432895176895617324617432958976354281128976543354128769543281697769543812281769435 # Solution

123456789456789123789123456231564897564897231897231564315672948672948315948315672 # Minlex grid

.....67..45.....2..89......2.156.......8......9.2....4.....2.4867.....1....3....2 # first CP
.......89..67.........2.45.2....4.9.56....2.18........3....2.....2.48.......1.67. # minlex CP

.....67..45.....2..89......2.156.......8......9.2....4.....2.4867.....1....3....2 # CP 1
..3.5.7........1..78....4.6.31......5.4..7......2...6.....7.9..6.2..8.......15.7. # CP 2
1........4.678....7....3.5....5.4..7.6....2......31......6.2..8.7.....159......7. # CP 3
...4.678..5.7....3...1.....2...6...........31..7...5.4.15.7.....7.9.......8...6.2 # CP 4
.2.45........89...7.......6......8....4.9.2.....2.156..1.67......2...3...48.....2 # CP 5
.......89..67.........2.45.2....4.9.56....2.18........3....2.....2.48.......1.67. # CP 6
Attachments
Minlex9PP.zip
Update #2
(144.53 KiB) Downloaded 49 times
Last edited by Mathimagics on Wed Feb 03, 2021 4:08 am, edited 4 times in total.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1804
Joined: 27 May 2015
Location: Canberra

Re: Minlex Library (9x9)

Postby denis_berthier » Mon Feb 01, 2021 6:22 am

[Deleted] now irrelevant
Last edited by denis_berthier on Mon Feb 01, 2021 9:18 am, edited 1 time in total.
denis_berthier
2010 Supporter
 
Posts: 2673
Joined: 19 June 2007
Location: Paris

Re: Minlex Library (9x9)

Postby Mathimagics » Mon Feb 01, 2021 6:34 am

Unix clients will need to tweak the code slightly, by disabling the WINDOWS definition in Minlex9.c (line 66) and Demo.c (line 2).
Last edited by Mathimagics on Mon Feb 01, 2021 10:31 am, edited 5 times in total.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1804
Joined: 27 May 2015
Location: Canberra

Re: Minlex Library (9x9)

Postby denis_berthier » Mon Feb 01, 2021 6:43 am

[Deleted] Now irrelevant
Last edited by denis_berthier on Mon Feb 01, 2021 9:19 am, edited 2 times in total.
denis_berthier
2010 Supporter
 
Posts: 2673
Joined: 19 June 2007
Location: Paris

Re: Minlex Library (9x9)

Postby Mathimagics » Mon Feb 01, 2021 7:02 am

[deleted]
Last edited by Mathimagics on Mon Feb 01, 2021 10:32 am, edited 1 time in total.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1804
Joined: 27 May 2015
Location: Canberra

Re: Minlex Library (9x9)

Postby denis_berthier » Mon Feb 01, 2021 7:23 am

[Deleted now irrelevant parts]

Can the program be used to find the/a minlex form of a pattern, eg --XX----X-X--X--X-X----XX--X----XX---X--X--X---XX----XX----XX---X--X--X---XX----X (or whatever syntax for it)?
Last edited by denis_berthier on Mon Feb 01, 2021 9:20 am, edited 1 time in total.
denis_berthier
2010 Supporter
 
Posts: 2673
Joined: 19 June 2007
Location: Paris

Re: Minlex Library (9x9)

Postby Mathimagics » Mon Feb 01, 2021 8:21 am

denis_berthier wrote:Can the program be used to find the/a minlex form of a pattern, eg --XX----X-X--X--X-X----XX--X----XX---X--X--X---XX----XX----XX---X--X--X---XX----X (or whatever syntax for it)?

No, these functions all have a solution grid as the first argument.

Mladen has done much work with patterns. GridChecker has a puzzle-only minlex function (subcanon.cpp), maybe he has a pattern-only version?
Last edited by Mathimagics on Mon Feb 01, 2021 10:41 am, edited 1 time in total.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1804
Joined: 27 May 2015
Location: Canberra

Re: Minlex Library (9x9)

Postby denis_berthier » Mon Feb 01, 2021 9:23 am

Mathimagics wrote: can we then "reset" this thread by removing the now-redundant posts?

It works and I've deleted (as much as one can delete) the irrelevant posts or parts of posts.
Thanks

Mathimagics wrote:
denis_berthier wrote:Can the program be used to find the/a minlex form of a pattern, eg --XX----X-X--X--X-X----XX--X----XX---X--X--X---XX----XX----XX---X--X--X---XX----X (or whatever syntax for it)?

No, these functions all have a solution grid as the first argument.
Mladen has done much work with patterns. GridChecker has a puzzle-only minlex function (subcanon.cpp), maybe he has a pattern-only version

I tried to compile Gridchecker once, but it's Windows only.
denis_berthier
2010 Supporter
 
Posts: 2673
Joined: 19 June 2007
Location: Paris

Re: Minlex Library (9x9)

Postby Mathimagics » Mon Feb 01, 2021 10:40 am

I will look into the addition of Minlex9 functions for Puzzle/Pattern arguments ...
User avatar
Mathimagics
2017 Supporter
 
Posts: 1804
Joined: 27 May 2015
Location: Canberra

Re: Minlex Library (9x9)

Postby dobrichev » Mon Feb 01, 2021 1:10 pm

Hi Mathimagics,

Thank you for publishing your code.

denis_berthier wrote:Can the program be used to find the/a minlex form of a pattern, eg --XX----X-X--X--X-X----XX--X----XX---X--X--X---XX----XX----XX---X--X--X---XX----X (or whatever syntax for it)?

Do you need something of this sort? It canonicalizes firstly to pattern-row-min-lex, then identical patterns to row-min-lex, and doesn't care whether puzzle is solvable. Similar does Deverin's subgrid min-lex canonicalization but it is purely row-min-lex. Both canonical representations match for inputs [0-1], but differ for inputs [0-9].
dobrichev
2016 Supporter
 
Posts: 1816
Joined: 24 May 2010

Re: Minlex Library (9x9)

Postby Mathimagics » Mon Feb 01, 2021 1:28 pm

Mathimagics wrote:I will look into the addition of Minlex9 functions for Puzzle/Pattern arguments ...


Hi Mladen!

I will not pursue this, as gsf's sudoku tool is capable of minlex-ing both puzzles and patterns (see here)

That should be adequate for Denis's needs, I think ...
User avatar
Mathimagics
2017 Supporter
 
Posts: 1804
Joined: 27 May 2015
Location: Canberra

Re: Minlex Library (9x9)

Postby Serg » Mon Feb 01, 2021 5:13 pm

Hi, Denis!
denis_berthier wrote:Can the program be used to find the/a minlex form of a pattern, eg --XX----X-X--X--X-X----XX--X----XX---X--X--X---XX----XX----XX---X--X--X---XX----X (or whatever syntax for it)?

I know at least 2 ways to get patterns minlex forms - using gsf's "sudoku" tool and using Mladen Dobrichev's "gridchecker" ("gridchecker" is much more faster).
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 '.'.


Serg
Serg
2018 Supporter
 
Posts: 768
Joined: 01 June 2010
Location: Ukraine

Re: Minlex Library (9x9)

Postby denis_berthier » Tue Feb 02, 2021 7:06 am

Hi dobrichev, serg
Thanks for your answers
dobrichev wrote:
denis_berthier wrote:Can the program be used to find the/a minlex form of a pattern, eg --XX----X-X--X--X-X----XX--X----XX---X--X--X---XX----XX----XX---X--X--X---XX----X (or whatever syntax for it)?

Do you need something of this sort? It canonicalizes firstly to pattern-row-min-lex, then identical patterns to row-min-lex, and doesn't care whether puzzle is solvable.

I downloaded it and I can compile it on my Mac, so it should work. However, there's zero documentation and I don't know how to launch it.
I tried the simplest idea I had:
sudoku-minlexing-tool.exe 001100001010010010100001100100001100010010010001100001100001100010010010001100001
but it only gives (after a minute or so):
................................................................................. 0
...

dobrichev wrote:Similar does Deverin's subgrid min-lex canonicalization but it is purely row-min-lex. Both canonical representations match for inputs [0-1], but differ for inputs [0-9].

I tried to compile with g++ -m64 -O3 -march=native -msse4.2 -mavx -g3 -gdwarf-2 -Wall *.cpp
but I get : subcanon.cpp:1:10: fatal error: 'malloc.h' file not found (and I can't find any malloc.h file in gridchecker. I guess it's a Linux-only system file).

Serg wrote:I know at least 2 ways to get patterns minlex forms - using gsf's "sudoku" tool and using Mladen Dobrichev's "gridchecker" ("gridchecker" is much more faster).
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 '.'.

gsf's program doesn't give the expected result when given a pattern (see http://forum.enjoysudoku.com/dephased-waves-8-3-t38634-18.html)
As expected, I have the same compilation problem with gridchecker as with the subcanon part.

What do the people playing the Patterns Game use to check that their patterns are new?
denis_berthier
2010 Supporter
 
Posts: 2673
Joined: 19 June 2007
Location: Paris

Re: Minlex Library (9x9)

Postby m_b_metcalf » Tue Feb 02, 2021 7:33 am

denis_berthier wrote:What do the people playing the Patterns Game use to check that their patterns are new?

One submits the requisite puzzle and gets told by g.r.emlin whether it's new/old/insufficiently symmetric.

Mike
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 12268
Joined: 15 May 2006
Location: Berlin

Re: Minlex Library (9x9)

Postby denis_berthier » Tue Feb 02, 2021 8:22 am

m_b_metcalf wrote:
denis_berthier wrote:What do the people playing the Patterns Game use to check that their patterns are new?

One submits the requisite puzzle and gets told by g.r.emlin whether it's new/old/insufficiently symmetric.
Mike

ok, but then what software does gremlin use to do the check?
denis_berthier
2010 Supporter
 
Posts: 2673
Joined: 19 June 2007
Location: Paris

Next

Return to Software