The New Sudoku Players' Forum

by **eleven** » Tue Mar 20, 2012 5:45 pm

champagne wrote:The 20 clues pattern is much in favour of a start with rows 1379.
If we both follow the same way, we can compare results after 8 clues assigned
(I posted the results after rows 1357 in both modes but in maxtext form).

Ah, you posted in the meantime. Please see my edit above.

I only calculated the results for all 12/13 clues at once (as described).

by **ronk** » Tue Mar 20, 2012 8:35 pm

champagne wrote:
ronk wrote:
Code: Select all
..B...B...........B.......B...........................B.......B...........B...B.. # step 1, 8 clues in r1379 ..A...A...........A.......A...B.B...............B.B...A.......A...........A...A.. # step 2, add 4 clues in b5 ..A...A...B.....B.A.......A...A.A...............A.A...A.......A.B.....B...A...A.. # step 3, add 4 clues in b1379 At each step, apply permutations: 1) diagonal and 2) row{13}{79}column{13}{79} ... ... keeping only essentially-different sub-puzzles as inputs for the next step
nearly perfect except for ...

Even for just these three steps, this isn't precise or complete, is it?

by **champagne** » Tue Mar 20, 2012 10:52 pm

ronk wrote:Even for just these three steps, this isn't precise or complete, is it?

I don't know how to answer to that

Code: Select all: ..B...B...........B.......B...........................B.......B...........B...B.. # step 1, 8 clues in r1379 skmpp -i"_1c" -c"22|._1" -1..B...B...3...1.4.B.......B...9.6.1.....3.....7.8.2...B.......B.8.4...7...B...B.. ..A...A...........A.......A...B.B...............B.B...A.......A...........A...A.. # step 2, add 4 clues in b5 skmpp -i"_1cr1" -c"22|._1" -1..A...A...3...1.4.A.......A...B.B.1.....3.....7.B.B...A.......A.8.4...7...A...A.. ..A...A...B.....B.A.......A...A.A...............A.A...A.......A.B.....B...A...A.. # step 3, add 4 clues in b1379 skmpp -i"_1cr2" -c"22|._1" -1..A...A...B...1.B.A.......A...A.A.1.....3.....7.A.A...A.......A.B.4...B...A...A..

here is a comparison step by step of your post and my command line.

All 'A' and 'B' are correct.

for sure my command line requires also the 'unassigned positions at the end of the step",
but I doubt this is the reason for you question.

Could you be more precise on what is disturbing you

champagne

by **champagne** » Thu Mar 22, 2012 7:59 am

Some results after a tentative exhaustive search on coloin 21 clues pattern

Code: Select all: ..1...2.. .2...1.3. 4.......5 ...4.6.1. ....7.... .3.5.2... 6.......4 .8.3...9. ..2...6..

As I said it took me about one day using the full power of an I7 to scan the field, using as much as possible the symmetry.

The search has been made in three steps, applying symmetry at the end of each step

step 1 rows 1 3 7 9
step 2 adding box 5 without the central clue
step 3 adding missing clues in boxes 1 3 7 9

plus the final search.

at the end of step 3, the output contained about 10 millions seeds spread in five "nearly equal" lots.

The search gave in total

3981 "raw" puzzles
3301 different puzzles after clearance of morphs

The ratio net to raw is very low, which show that the process was very efficient to avoid generation of morphs.

Impossible to be 100% sure that we got all the puzzles, but, except may be for some puzzles with singles, I think we have all of them

If I look batch per batch, I got the following

Code: Select all: batch number of puzzles 1 7 2 1480 3 0 4 46 5 2458

which shows that wide areas of seeds have no puzzles.

Out of the 3303 puzzles, 3188 are minimal.
I have still to work on the sub minimal file to check if I get the 112 former puzzles and not more.

as far as ratings are concerned, congratulations to mike, he got the highest rating I have in hand.

serate is still working, and it's clear that there are many puzzles with ED 10.4
i'll add later the list of high ratings to that post

champagne

EDIT I receive through pm a question

why "tentative" exhaustive

In fact, as long as the results will not have been matched with another test from another program, I must stay very cautious.
All this is fresh code still far from what would be required to qualify it as "beta test".

EDIT 2

hereafter, the highest rating and all puzzles I found with ED 10.4

Hidden Text: Show

by **ronk** » Thu Mar 22, 2012 1:18 pm

champagne wrote:
ronk wrote:Even for just these three steps, this isn't precise or complete, is it?
Could you be more precise on what is disturbing you

I was referring to imprecision in the canonicalization process for each step. It says nothing about permutation of clue values.

ronk wrote:At each step, apply permutations: 1) diagonal and 2) row{13}{79}column{13}{79} ...
... keeping only essentially-different sub-puzzles as inputs for the next step[/code]

One could argue that clue permutation is included in "essentially different", but that no longer seems precise enough to me. How would you restate that?

by **champagne** » Thu Mar 22, 2012 2:13 pm

ronk wrote:
champagne wrote:
ronk wrote:Even for just these three steps, this isn't precise or complete, is it?
Could you be more precise on what is disturbing you

I was referring to imprecision in the canonicalization process for each step. It says nothing about permutation of clue values.

ronk wrote:At each step, apply permutations: 1) diagonal and 2) row{13}{79}column{13}{79} ...
... keeping only essentially-different sub-puzzles as inputs for the next step[/code]

One could argue that clue permutation is included in "essentially different", but that no longer seems precise enough to me. How would you restate that?

may be the simpler is to try to describe what does the code.

first of all, a parameter in the command line ask for use of perms -c"22|._1" (it is the digit '1' in that command)

At the start, working on the pattern given in the command line, the program try all valid moves (following the general rules of the sudoku)
(puzzle rotation+ band/stack permutations+permutations inside the band/stack)
and look whether the pattern is unchanged in that move.
If the code is valid, you get at the end a small number of valid perms depending on the symmetries of the pattern.
It can be any move and one move usually combine several elementary symmetries.

In that specific pattern, the program has found 15 morphs + the original pattern.
I did not check the validity, but you have in the pattern

. both diagonal symmetry
. central symmetry
. R90 symmetry
. possibility to exchange rows 13 79 and columns 13 79

The program checks also that all 'A' and 'B' are in line with the symmetry and cancel the process if one move is not valid.
This is likely to strict.

Once the list of moves is known, processing of the puzzles starts.
As noticed eleven, each morph has to be canonicalised after the move.

So if my code is correct, you should find 16 different ways to morphs each puzzle, including the original.

champagne

by **eleven** » Thu Mar 22, 2012 3:00 pm

ronk wrote:One could argue that clue permutation is included in "essentially different", but that no longer seems precise enough to me.

There are indeed some pitfalls, i was not aware, when i tried my count tests.

The last one was this. I noticed, that i got less puzzles to check, when - while filling in digits - i sorted out sub-puzzles, for which there is a mapping (according to the automorphisms of the complete pattern) to a puzzle with smaller minlex form. But then i saw this:

Code: Select all: ..1...2...3...1.4.2.......1...1.2.3.....3.....2.5.6...1.......2.7.2...8...2...1.. (multi-solution) puzzle in minlex form, minimal for all morphs ..1...2.......1...2.......1...1.2.3.....3.....2.5.6...1.......2...2.......2...1.. sub-puzzle ..1...2.......1...2.......1...1.2.3.....3.....2.4.5...1.......2...2.......2...1.. sub-puzzle in minlex form ..1...2.......1...2.......1...1.2.3.....3.....1.4.5...1.......2...2.......2...1.. morphed sub-puzzle in minlex form

Therefore i missed the complete puzzle, when i deleted the "eqivalent" sub-puzzle.

In fact i dont know, how to repair that.

by **champagne** » Thu Mar 22, 2012 4:46 pm

eleven wrote:
ronk wrote:One could argue that clue permutation is included in "essentially different", but that no longer seems precise enough to me.

There are indeed some pitfalls, i was not aware, when i tried my count tests.

The last one was this. I noticed, that i got less puzzles to check, when - while filling in digits - i sorted out sub-puzzles, for which there is a mapping (according to the automorphisms of the complete pattern) to a puzzle with smaller minlex form. But then i saw this:
Code: Select all
..1...2...3...1.4.2.......1...1.2.3.....3.....2.5.6...1.......2.7.2...8...2...1.. (multi-solution) puzzle in minlex form ..1...2.......1...2.......1...1.2.3.....3.....2.5.6...1.......2...2.......2...1.. sub-puzzle ..1...2.......1...2.......1...1.2.3.....3.....2.4.5...1.......2...2.......2...1.. sub-puzzle in minlex form ..1...2.......1...2.......1...1.2.3.....3.....1.4.5...1.......2...2.......2...1.. morphed sub-puzzle in minlex form
Therefore i missed the complete puzzle, when i deleted the "eqivalent" sub-puzzle.

In fact i don't know, how to repair that.

It seems to me that I don't have that problem.
I start morphing just before writing in the output file, this can not affect the generation process.
Morphing is done in the output buffer (or something equivalent)
But as explained before, a preliminary check has been done to verify that the run is compatible with all morphs

champagne

by **ronk** » Thu Mar 22, 2012 5:33 pm

eleven wrote:then i saw this:
Code: Select all
..1...2...3...1.4.2.......1...1.2.3.....3.....2.5.6...1.......2.7.2...8...2...1.. (multi-solution) puzzle in minlex form, minimal for all morphs ..1...2.......1...2.......1...1.2.3.....3.....2.5.6...1.......2...2.......2...1.. sub-puzzle ..1...2.......1...2.......1...1.2.3.....3.....2.4.5...1.......2...2.......2...1.. sub-puzzle in minlex form ..1...2.......1...2.......1...1.2.3.....3.....1.4.5...1.......2...2.......2...1.. morphed sub-puzzle in minlex form
Therefore i missed the complete puzzle, when i deleted the "eqivalent" sub-puzzle.

eleven, for each sub-puzzle at each generation step, I think one must relabel clues in row minlex order for each automorph existing in the final pattern, and choose the lexicographically minimum one for that sub-puzzle. Maxlex like champagne is doing should be OK too.

I don't have a software program to do this and don't have plans to write one, so have no way to verify my statement.

by **eleven** » Thu Mar 22, 2012 6:43 pm

champagne wrote:It seems to me that I don't have that problem.
I start morphing just before writing in the output file, this can not affect the generation process.
Morphing is done in the output buffer (or something equivalent)
But as explained before, a preliminary check has been done to verify that the run is compatible with all morphs

Ehm, in the sets you generate after each of your 3 steps, aren't sub-puzzles eliminated, which have equivalent morphs to others ? If not i wonder, how your counts can be that low.

by **eleven** » Thu Mar 22, 2012 6:49 pm

ronk wrote:eleven, for each sub-puzzle at each generation step, I think one must relabel clues in row minlex order for each automorph existing in the final pattern, and choose the lexicographically minimum one for that sub-puzzle. Maxlex like champagne is doing should be OK too.

Don't you see my puzzle as example, that this way you are missing possible puzzles with all clues of the pattern filled ? The lexicographically minimum of its sub-puzzle is higher than the lexicographically minimum of a morph (different to the complete puzzle). But if you eliminate it, you will not find the complete puzzle.

by **champagne** » Thu Mar 22, 2012 7:46 pm

eleven wrote:
champagne wrote:It seems to me that I don't have that problem.
I start morphing just before writing in the output file, this can not affect the generation process.
Morphing is done in the output buffer (or something equivalent)
But as explained before, a preliminary check has been done to verify that the run is compatible with all morphs

Ehm, in the sets you generate after each of your 3 steps, aren't sub-puzzles eliminated, which have equivalent morphs to others ? If not i wonder, how your counts can be that low.

compression of the output file is done outside the generation of puzzles in my case (just entering the file in ACCESS and cleaning redundancy)
The other way is for sure to have a built in sorting table in the program, but i don't like that

So I have just to write the canonical form instead of the puzzle generated in the process;

champagne

by **ronk** » Thu Mar 22, 2012 8:23 pm

eleven wrote:Don't you see my puzzle as example, that this way you are missing possible puzzles with all clues of the pattern filled ? The lexicographically minimum of its sub-puzzle is higher than the lexicographically minimum of a morph (different to the complete puzzle). But if you eliminate it, you will not find the complete puzzle.

My response wasn't directed to your counter-example, and I should have said so. However, I'm not convinced you have an applicable counter-example. I find the subject of canonicalizing sub-puzzles (in this post, puzzles with multiple solutions) very confusing. For example, why should "downsizing" and "upsizing" between sub-puzzles even follow reciprocal paths?

The only thing I'm convinced of is that starting with a sub-pattern of a puzzle's pattern, generating all appropriate non-isomorphic sub-puzzles for that sub-pattern, expanding the generation by upsizing through larger sub-patterns and finally to the original pattern, should produce all non-isomorphic puzzles with that pattern, including the original puzzle (or morphs thereof). [edit: AFAIK, even this has yet to be proven.]

Doing the "equivalent" with sub-puzzles only may not need to have an equivalent result.

by **eleven** » Thu Mar 22, 2012 9:56 pm

ronk wrote:My response wasn't directed to your counter-example, and I should have said so. However, I'm not convinced you have an applicable counter-example.

Thats right, there is still a chance to find this puzzle from other normalized sub-puzzles.

The only thing I'm convinced of is that starting with a sub-pattern of a puzzle's pattern, generating all appropriate non-isomorphic sub-puzzles for that sub-pattern, expanding the generation by upsizing through larger sub-patterns and finally to the original pattern, should produce all non-isomorphic puzzles with that pattern, including the original puzzle (or morphs thereof). [edit: AFAIK, even this has yet to be proven.]

Thats the point, its not proven and i am sure, that its wrong. Just cant look for a complete counter-example now.

by **ronk** » Thu Mar 22, 2012 11:04 pm

eleven wrote:
ronk wrote:AFAIK, even this has yet to be proven.
Thats the point, its not proven and i am sure, that its wrong.

I've got a parallel process running, at a snail's pace unfortunately, but I'm more concerned with accuracy right now.

It's a two step process for the pattern of game 0169. The first step generated 650,000+ sub-puzzles for the 13 cell pattern excluding r28c28, r4c6, r5c5 and r6c4. This pattern has 4 automorphs just like the full pattern, so little chance for error there (using gsf's program).

The second step has been running for several days now. Neglected to add "progress markers", so have little idea of the completion percentage, only that there are 88 non-equivalent puzzles so far. Every one is in the list posted by dobrichev here.

I'm hoping the computer won't restart before it finishes (knocking on wood).

The New Sudoku Players' Forum

Patterns Game Strategies

Re: Patterns Game Strategies

Re: Patterns Game Strategies

Re: Patterns Game Strategies

Re: Patterns Game Strategies

Re: Patterns Game Strategies

Re: Patterns Game Strategies

Re: Patterns Game Strategies

Re: Patterns Game Strategies

Re: Patterns Game Strategies

Re: Patterns Game Strategies

Re: Patterns Game Strategies

Re: Patterns Game Strategies

Re: Patterns Game Strategies

Re: Patterns Game Strategies

Re: Patterns Game Strategies