The New Sudoku Players' Forum

[champagne]

I got the following results

Code: Select all

first step ..B...B...3...1.4.B.......B.....6.1.....3.....7.8.2...B.......B.8.4...7...B...B..


rows 1;3 columns 1;3
raw generation 354
net generation 123

OK, I can duplicate your count of 354, so I assume we're counting the same list. But what does "net generation" mean? IOW on what basis are you making the reduction from 354 to 123? Full-fledged canonicalization would reduce it to 56, so that can't be it.

Also, why are most pattern cells here shown with tokens other than '1' or 'B''? To be consistent with your prior posts, shouldn't all digits be '1'?

Lastly, I seem to be the only one having trouble intrepreting or duplicating your posted data and I'm about ready to throw in the towel. Is no one else trying to follow, or is everyone else smarter?

I think I do my best to explain what I did.

Regarding the command line I wrote earlier

I added in the command line a 81 bits field having
‘A’ for already assigned position
‘B’ for positions to assign in that step
Any digit for other positions of the pattern.

this is in line with the post

I usually take care to start the generation with a template having all active cells set to '1', to have an easier reading of the output, but it could be any digit as well.
it's not so important in the command line. I sometimes use an existing puzzle.

As I wrote, I apply only morphing valid for the full pattern (here four possible morphs), so I go from 'raw' to 'net' clearing all morphs with that restrictive definition.

I hope the process is correct.

I don't know what is "Full-fledged canonicalization"

champagne

EDIT: I see anomalies in my "canonicalization in pattern". I'll fix it and see if it leads to the 56 found by ronk

[eleven]

Is no one else trying to follow, or is everyone else smarter?

I am not that interested in the details. I guess the principle is clear, how you could make it, e.g. :
Take the pattern in whatever form you like,
- fill in some fixed digits 1,2,.. in a unit (preferably a unit with maximum pattern cells),
- select a subset of pattern cells leaving N (say up to 8) cells free (preferably all pattern cells in some units)
- fill these cells with all possible combinations of digits and write these sub-puzzles to a file (a step where some optimization can be done, but which is not much time consuming anyway)
- normalize the sub-puzzles and eliminate all equivalents (ev. restore the original pattern after that)
- do a {+N} search for the empty pattern cells for each sub-puzzle

I just had tested this for a reflection symmetric 18 clue pattern. This way i can do an exhaustive search in about an hour on a single core.

[champagne]

I am not that interested in the details.

I just had tested this for a reflection symmetric 18 clue pattern. This way i can do an exhaustive search in about an hour on a single core.

I agree basically with your statement.

Each of us has it's own code and can be much more efficient just picking up ideas to put them in it.

If your goal is a full scan, for sure it works better with less clues just due to the fact that in that case you have usually more morphs for the same pattern.

If the pattern has no morph, the process just brings one easy way to end in a parallel process.

The main reason why I entered in that process is not to make an exhaustive search, but to have some way for selective search.

However, even with more clues, symmetric patterns can offers a significant reduction in the search.
a highly symmetric pattern (2 diagonals or R90) offers by construction many morphs.

champagne

[m_b_metcalf]

When I thought about performing a full scan for this pattern myself, I thought a suitable algorithm would be:

Step 1: Number the cells 1 to 81.

Set empty cells to zero.

Take all valid combinations of values in the cells defined by the pattern, subject to the usual sudoku constraints, plus the additional condition that:

s(n) <= max(s(1), ..., s(n-1)) + 1

Step 2: (in order to handle the symmetry around the main diagonal)

Make a transposed copy of the candidate puzzle.

Renumber the clues from 1 upwards, such that each first occurence of a value is in ascending order.

If all cells in this transposed version also fulfil the additional condition above, [edited beyond this point] the puzzle is one of a duplicate pair, and a check is made to see whether it has already been seen by maintaining an appropriate list. If it has already been seen, it is rejected.

A similar procedure is required to handle the r{13}{79}c{13}{79} morph.

Is this correct or is here a flaw?

Regards,

Mike Metcalf

[champagne]

May be one very simle example could clarify the permutations issue

In my first step of the second run, the generaton is reduced to 8 cells.

If we reduce the puzzle to rows 1378 columns 1378, the appearance of one soution is the following

Code: Select all

.a b.
c. .d

e. .f
.g h.


with the boxes 1;3;7;9

Lets consider only partial generation using 3 digits
with only one occurence of the 'third' digit

Working in maxtext form, my generator could come to the following raw puzzles
(to make it simpler I assume the generator fills first box 1)

Code: Select all

.9 7.   .9 8.   .9 8.   .9 8.   .9 8.   .9 8.
8. .9   8. .7   8. .9   8. .9   8. .9   8. .9

9. .8   9. .8   7. .8   9. .8   9. .7   9. .8
.8 9.   .8 9.   .8 9.   .7 9.   .8 9.   .8 7.

If we use freely the symmetries of that reduced pattern, we come to a unique "net" puzzle
It will be the last one in maxtext form

This is what is doing my previous generator and IMO this does not lead to an exhaustive search.

The only permutations authorised in our pattern are

- the diagonal symmetry
- exchange of rows 13 78 columns 13 78 (all in once)

The digit '7' can be moved from box 3 to box 7
but if the digit '7' is in box 9, it will stay there

At the end, after relabelling, we have 2 permutations, number 4 and number 6 (in maxtext mode)
raw puzzles 1;2;3 are morphs of puzzle 4 and raw puzzle 5 is a morph of puzzle 6

champagne

[champagne]

When I thought about performing a full scan for this pattern myself, I thought a suitable algorithm would be:

Step 1: Number the cells 1 to 81.

Set empty cells to zero.

Take all valid combinations of values in the cells defined by the pattern, subject to the usual sudoku constraints, plus the additional condition that:

s(n) <= max(s(1), ..., s(n-1)) + 1

Step 2: (in order to handle the symmetry around the main diagonal)

Make a transposed copy of the candidate puzzle.

Renumber the clues from 1 upwards, such that each first occurence of a value is in ascending order.

If all cells in this transposed version also fulfil the additional condition above, reject the puzzle as a duplicate.

Is this correct or is here a flaw?

Regards,

Mike Metcalf

Well mike,

If I get it correctly, you formula in step one means that you use only digits already assigned plus one.
This is correct for me

I have more difficulties with your step 2

A puzzle in itself can never be rejected.
It's only when you see morphs of an existing puzzle (already generated) that you can forget the new one;

I know 2 ways to achieve that:

- keeping in memory track of generated puzzle
- writing a file and sorting the file with existing tools.

I don't see that in your wording.

champagne

[ronk]

[edit: list of 56 ED sub-puzzles deleted]

[m_b_metcalf]

I don't see that in your wording.

Yes, as worded it rejects all puzzles that are one of a pair of morphs arising from the symmetery. Step 1 will generate all valid puzzles, without morphs due to renumbering permutations,but with morph pairs based on the symmetry. We want to reject one of the morph pairs in step 2, because it's saying that if the transpose also fulfils the condition, its partner has either already been generated, or it will be generated later. The original wording (about to be edited) rejects both morphs in a pair. It needs to say that puzzles identified as one of a morph pair should be written to a separate file. That can subsequently be purged of duplicates in a separate step, as you say. All other puzzles can go to a different file that is known to be free of morphs.

Regards,

Mike

[champagne]

I don't see that in your wording.

Yes, as worded it rejects all puzzles that are one of a pair of morphs arising from the symmetery. Step 1 will generate all valid puzzles, without morphs due to renumbering permutations,but with morph pairs based on the symmetry. We want to reject one of the morph pairs in step 2, because it's saying that if the transpose also fulfils the condition, its partner has either already been generated, or it will be generated later. The original wording (about to be edited) rejects both morphs in a pair. It needs to say that puzzles identified as one of a morph pair should be written to a separate file. That can subsequently be purged of duplicates in a separate step, as you say. All other puzzles can go to a different file that is known to be free of morphs.

Regards,

Mike

may be some more comments taking in account my ongoing test on that pattern.

In that way, you don't account the permutation rows 13 79 columns 13 79 producing more morphs.
Clearing morphs has some value only if it is done early in appropriate conditions, saving some generation time
A full process on that 20 clue pattern will last anyway days and days.

The ongoing test started nearly one day ago.
- having applied symmetry potential on 12 cells
- having activated parallel processing
- using cores around 3Ghz

I have not yet done half of the work, so I now think the search will last 3 days.

champagne

[m_b_metcalf]

In that way, you don't account the permutation rows 13 79 columns 13 79 producing more morphs.
Clearing morphs has some value only if it is done early in appropriate conditions, saving some generation time

You're right. I had naively thought that would be taken care of. Another edit, but I'm not going to try this anyway!

Happy hunting!

Mike

[champagne]

Happy hunting!

Mike

I am convinced that all puzzles have been found, so it's just a test of the process and a confirmation somehow that this is not a tool for the game as such.

champagne

[coloin]

Interesting indeed.

For this particular pattern It might even be quicker to generate "all" the 21 clue puzzlles with 5 clues in box 5 [in an "X" pattern] -instead of 4 - and then test for possible removal of a clue.

It doesnt result in more clue possibilities [less actually]
There is another factor of 2 [or more] to factor for the symmetry

Edit -

Code: Select all

+---+---+---+
|...|...|...|
|...|..1|...|
|...|...|...|
+---+---+---+
|...|123|.4.|
|...|456|...|
|.1.|789|...|
+---+---+---+
|...|...|...|
|...|2..|...|
|...|...|...|
+---+---+---+   6^4 = 1296 of which 183 are ED

+---+---+---+
|...|...|...|
|...|..1|...|
|...|...|...|
+---+---+---+
|...|1.3|.2.|
|...|.5.|...|
|.1.|7.9|...|
+---+---+---+
|...|...|...|
|...|2..|...|
|...|...|...|
+---+---+---+   7^4 = 2401 0f which 66 are ED

+---+---+---+
|...|...|...|
|...|..1|...|
|...|...|...|
+---+---+---+
|...|1.3|.2.|
|...|.5.|...|
|.1.|7..|...|
+---+---+---+
|...|...|...|
|...|2..|...|
|...|...|...|
+---+---+---+  64*49 = 3136 of which 129 are ED

I have actually now found a puzzle [and submitted] with a modified diagonal 20 clue pattern for you to "play" when the pattern comes up in the game.

C

[ronk]

The ongoing test started nearly one day ago.
- having applied symmetry potential on 12 cells

Please post the list of sub-puzzles remaining after "having applied symmetry potential on 12 cells."

[champagne]

The ongoing test started nearly one day ago.
- having applied symmetry potential on 12 cells

Please post the list of sub-puzzles remaining after "having applied symmetry potential on 12 cells."

nothing objects to posting the file except that it contains 57990 puzzles.
I have to upload the results in my website.
I'll edit that post as soon as it is ready giving the link


also an interim position in the ongoing test.

I surely passed 2/3 of the generation and the current results are

raw puzzles 584
net puzzles 102

I did not check yet that they all have already been found

champagne

[champagne]

Interesting indeed.

For this particular pattern It might even be quicker to generate "all" the 21 clue puzzlles with 5 clues in box 5 [in an "X" pattern] -instead of 4 - and then test for possible removal of a clue.

It doesnt result in more clue possibilities [less actually]
There is another factor of 2 [or more] to factor for the symmetry

C

your proposal seems to work .

In the process I followed in my ongoing test
- the count would have been more or less halved in the first step,
- the situation is unclear in the second one. We have in theory 5 possibilities for the 5th digit,
but in many cases it will be less.

Another issue is to accept non minimal puzzles at generation.
I have to check that that option is working with my new code

It's easy anyway to do the test for the first 13 cells as in my example.
I'll do it to-day

champagne

EDIT:

I made a quick test reproducing the 2 first steps of my test run.

with 13 clues, I end with 54339 seeds instead of 57990.

I think that to take full benefit of the symmetry, another step(s) has to be done before the final search

EDIT 2 : I got disappointing results with more clues.

Either there is a bug in my permutations handling or it's better to go direct after 11 clues.

Even in direct mode, it should be faster than with 20 clues just because we have reduced the number of authorised digits in some cells;