The New Sudoku Players' Forum

by **dobrichev** » Wed Jan 27, 2021 2:17 pm

Paid version of GridChecker has some functions unlocked

by **Mathimagics** » Wed Jan 27, 2021 3:06 pm

Hmmm ... that looks eerily familiar!

:lol:

by **Mathimagics** » Fri Jan 29, 2021 5:47 am

.
SudokuM 3-clue Puzzles

The catalog scan found 12,983 minimal 3-clue puzzles. Like the 2-clue puzzles listed above, the band range is 348 to 416, with a small number (12) of notable exceptions. Surprisingly, there were 12 puzzles found for bands 29,30,31:

3-clue puzzles (Bands 29-31): Show

Minimal Puzzle Generation

We can take any valid Sudoku puzzle (SP), convert it to canonical puzzle form (CP, so it solves to a minlex grid), and then enumerate all the minimal SudokuM puzzles that can be derived from that CP. Typically we find puzzles with 9, 10, or 11 clues. These examples show only the least-clue puzzles:

Example 1: Show

Example 2: Show

Example 3: Show

Example 4: Show

by **JPF** » Fri Jan 29, 2021 8:48 pm

Hi Mathimagics!

Impressive results for the exhaustive list of 3-clue puzzles!
now you practically have to figure out the list of all the minimal puzzles

Concerning the minimal puzzleM generation, I have two questions:
Is there somewhere a definition of what you call canonical form CF of the puzzle SP?

My guess is: if S is the solution of SP and if MLS is its minlex equivalent, then there exists a transformation f such that MLS=f(S)
A canonical form CF is f(SP).
CF is not unique if S has more than one automorphism, say n>1.
Actually, there are n different CF.

You wrote:...and then enumerate all the minimal SudokuM puzzles that can be derived from that CF.

What does it mean and how do you do that?

Thanks!

JPF

by **coloin** » Fri Jan 29, 2021 9:56 pm

Very impressive 1,2 and 3 clue puzzles .....

Heres a project !!!

If the intention was ever to get a SudokuM puzzle for each minlex grid ...[ eeeek] [ perhaps to potentially trim down a compressed catalogue of puzzles -> grids [? would it ]

How difficult / fast would it be to generate a nonminimal 27 plus 6 [per band] plus 6 [per band] puzzle [ or less] and end up having one for each minlex solution grid ? :geek:

EDIT its pretty quick to generate these puzzles 27 plus 6 plus 6 .... but only 1/6 of them will be able to be morphed to a minlex grid with band 1 full, ... but for every puzzle, potentially we have the 44 gangster -> 416 band expansion ...

Once we had the puzzles ....Solving would be quick .... coupled with the 27 clues [of the 416] plus the exception clues, Band choice would be from a choice of 2. ~ 1M puzzles solved per sec therefore 5000 secs 1.5 hrs only :roll:

Or do we already have a compressed file of puzzles [ 1 for each minlex grid ] with 20C ... how big is this file ?

by **Mathimagics** » Sat Jan 30, 2021 4:07 am

JPF wrote:Is there somewhere a definition of what you call canonical form CF of the puzzle SP?

Not really, as far as I can tell, but it seems to me to be a fundamental concept.

On reflection, perhaps a better term would be CP, ie Canonical Puzzle.

Congratulations, JPF, your guess above is absolutely correct! If SP solves to G, and f(G) transforms G to minlex, then f(SP) is a CP. There is a CP for each automorphism of G.

I wrote:...and then enumerate all the minimal SudokuM puzzles that can be derived from that CP.

What does it mean and how do you do that?

Perhaps "derived" was misleading. I meant only the normal "reduce to minimal" algorithm, which is a standard recursion that can be applied to any puzzle, in Sudoku or any variant. Given a valid puzzle P, you can use a simple recursion to find all the valid sub-puzzles (subsets of P). The recursion is applied to each removable clue at each level. Any terminal node (no removable clues) in the search tree corresponds to a minimal puzzle.

by **coloin** » Sat Jan 30, 2021 12:40 pm

Mathimagics wrote:
JPF wrote:Is there somewhere a definition of what you call canonical form CF of the puzzle SP?

Using gsf's software

Code: Select all: sudoku-64 -qFN -f%#0c prints puzzle in minlexgrid

After all these years it must treat automorphic puzzles in a standard way - otherwise we would have encoutered duplicates w.r.t the min lex puzzle
I presume it gives us the min lex puzzle in the min lex grid !

by **JPF** » Sat Jan 30, 2021 5:56 pm

wording...
Here is an example of a grid S with 6 automorphisms:

Code: Select all: n #automorphisms 6 SP Valid Puzzle .3.89......5.....4.17....5.9......8.....76....5.12............7...5.38.2..1.6...5 S Solution Grid 432895176895617324617432958976354281128976543354128769543281697769543812281769435 MLS MinLex(S) 123456789456789123789123456231564897564897231897231564315672948672948315948315672 CP1 Canonic puzzle .......89..67.........2.45.2....4.9.56....2.18........3....2.....2.48.......1.67. CP2 Canonic puzzle .....67..45.....2..89......2.156.......8......9.2....4.....2.4867.....1....3....2 CP3 Canonic puzzle ...4.678..5.7....3...1.....2...6...........31..7...5.4.15.7.....7.9.......8...6.2 CP4 Canonic puzzle ..3.5.7........1..78....4.6.31......5.4..7......2...6.....7.9..6.2..8.......15.7. CP5 Canonic puzzle .2.45........89...7.......6......8....4.9.2.....2.156..1.67......2...3...48.....2 CP6 Canonic puzzle 1........4.678....7....3.5....5.4..7.6....2......31......6.2..8.7.....159......7. MLSP MinLex(SP) ........1.....2345..1.3........436....7.......3.86.....6.1....345.7..9..9.......8

and yes:

Code: Select all: sudoku-64 -qFN -f%#0c SP

gives CP1=MinLex(CP1,CP2,...,CPn) which is compatible with

Code: Select all: sudoku-64 -qFN -f%#0c S

giving MinLex(S)

but I don't know how to use gsf's program to get all the CP when S is automorphic.

JPF

by **dobrichev** » Sat Jan 30, 2021 7:54 pm

Hi JPF,

See one possible implementation for listing all puzzles.
Unfortunately it is yet another hidden feature of this tool, now unused.

Firstly a mapping from original grid ( == puzzle solution) to its canonical form is produced in
void transformer::byGrid(const char* sol)

For automorphic grids all mappings are produced and the first refers to the next by the field named "next". Zero is end of the list.

Then the puzzle is transformed on the base of the collected mappings in the referred above
void transformer::transform(const char *in, char *out)

If empty cell is found, then it is a puzzle, and the procedure tries all mappings but returns only the minlex.

Just below is the procedure which adds all possible mappings to the output.
void transformer::transformAll(const char *in, char *out)

I double checked - transformAll isn't called from anywhere and isn't accessible from any command line parameters combination.

by **JPF** » Sun Jan 31, 2021 12:12 pm

Thank you Mladen!

JPF

by **Mathimagics** » Sun Jan 31, 2021 1:44 pm

Would it help if I posted my minlex code? The code is standard "C", with very fast minlexing, and includes an entrypoint for retrieving all the CP's for automorphic grids.

I was going to make it available at some point, but there seemed to be little evidence of demand, and so I never got around to it

by **JPF** » Sun Jan 31, 2021 5:01 pm

Yes please.
Either way it will be a great exercise for me to see how you coded M. Deverin's algorithm.
Thanks!

JPF

by **Mathimagics** » Mon Feb 01, 2021 4:38 am

I have posted the code in the Software area ... have fun!

BTW, I didn't actually encode his algorithm, I just hammered his existing code into submission :lol:

by **Serg** » Mon Feb 01, 2021 5:24 pm

Hi, Mathimagics!

Mathimagics wrote:I have posted the code in the Software area ... have fun!

BTW, I didn't actually encode his algorithm, I just hammered his existing code into submission

But Michael Deverin's code "hammered" by you runs 1.5 times faster than original code, isn't it?

Serg

by **Mathimagics** » Tue Feb 02, 2021 5:19 am

Serg wrote:But Michael Deverin's code "hammered" by you runs 1.5 times faster than original code, isn't it?

1.45 is probably closer to the mark. Also, in addition to the hammering, there was some sawing ...

The New Sudoku Players' Forum

MinLex Puzzles

Re: MinLex Puzzles

Re: MinLex Puzzles

Re: MinLex Puzzles

Re: MinLex Puzzles

Re: MinLex Puzzles

Re: MinLex Puzzles

Re: MinLex Puzzles

Re: MinLex Puzzles

Re: MinLex Puzzles

Re: MinLex Puzzles

Re: MinLex Puzzles

Re: MinLex Puzzles

Re: MinLex Puzzles

Re: MinLex Puzzles

Re: MinLex Puzzles