The New Sudoku Players' Forum

by **champagne** » Wed Mar 14, 2012 8:31 am

How was made the scan in the game 169

the pattern is the following

..1...1...1...1.1.1.......1.....1.1.....1.....1.1.1...1.......1.1.1...1...1...1..

I took that form as start to locate in the results the assigned cells

The first step has been to assign the band 1.

The command line contained the following 81 positions asking to assign first band

..B...B...B...B.B.B.......B.....1.1.....1.....1.1.1...1.......1.1.1...1...1...1..

the generation produced the next file.
so far no redundancy.
In fact, during the process, at any position,
assignment is made in decreasing order
the generation process is limited to the next free digit (unused before)

Hidden Text: Show

The following step has been to generate stack 1.
As the pattern has a main diagonal symmetry, generation is done in "pattern canonical" form.
The canonical form in that program is maxtext
The corresponding command line 81 bytes field is the following

The program found 4 permutations of rows and columns giving back the pattern (including no action)

..A...A...A...A.A.A.......A.....1.1.....1.....B.1.1...B.......1.B.1...1...B...1..

24141 partial puzzles were generated
7160 different puzzles were still there after elimination of morphs.

here after the start of the raw output just to show how it looks

..9...8...7...8.9.8.......7.....1.1.....1.....8.1.1...7.......1.9.1...1...8...1..
..9...8...7...8.9.8.......6.....1.1.....1.....8.1.1...7.......1.9.1...1...8...1..
..9...8...7...8.6.8.......7.....1.1.....1.....8.1.1...7.......1.9.1...1...8...1..
..9...8...7...8.6.8.......9.....1.1.....1.....8.1.1...7.......1.9.1...1...8...1..
..9...8...7...8.6.8.......5.....1.1.....1.....8.1.1...7.......1.9.1...1...8...1..
..9...8...7...8.9.8.......7.....1.1.....1.....8.1.1...6.......1.9.1...1...7...1..
..9...8...7...8.9.8.......7.....1.1.....1.....8.1.1...9.......1.6.1...1...7...1..

In my test, I made a third interim step generating bloc 5 in canonical form
The command line was the following

..A...A...A...A.A.A.......A.....B.1.....B.....A.B.B...A.......1.A.1...1...A...1..

that step generated a relatively small percentage of morphs, so I went from there directly to the end.
as already mentioned, to do that I split the file in about 10 pieces and started a parallel process,
but I had active in the command the immediate elimination of puzzles having a single as start.

At the end, I had in average about 3 to 4 times the final count of puzzles generated

Hope this is clear and i am open to any question.

champagne

by **champagne** » Wed Mar 14, 2012 12:03 pm

::: comment :::

coloin wrote:::: comment :::
The possibility that an exaustive count has been done is interesting.

Wonder if this [multi-solution] pattern has similar puzzles
Code: Select all
1 . . . . . 8 . . . 3 . . . 9 . 5 . . . 8 . . . . . 2 . . . . . 3 . 4 . . . . . 1 . . . . . 8 . 9 . 5 . . . 7 . . . . . . . 6 . 9 . 8 . . . 3 . . . 5 . . . 9 . .

- we probably would have been aware of SE>11 puzzles with the sk loop ...... ?

I see no way to process a multi-solution pattern with existing tools.

The minimum would be to split it in several patterns with a unique solution.

champagne

by **ronk** » Wed Mar 14, 2012 1:03 pm

::: comment :::

champagne wrote:The first step has been to assign the band 1.
The command line contained the following 81 positions asking to assign first band

..B...B...B...B.B.B.......B.....1.1.....1.....1.1.1...1.......1.1.1...1...1...1..

the generation produced the next file.
so far no redundancy.

Your list of 60 contains only 20 non-isomorphic sub-puzzles. Anticipating the next step, are you not allowing some pattern-preserving permutations? Which ones?

The 20 non-isomorphics: Show

by **champagne** » Wed Mar 14, 2012 1:27 pm

::: comment :::

ronk wrote:Your list of 60 contains only 20 non-isomorphic sub-puzzles. Anticipating the next step, are you not allowing some pattern-preserving permutations? Which ones?

you are likely right.

One of the final perms is to exchange rows 1;3 rows 7;9 columns 1;3 columns 7;9
This could be applied I guess in the first step.

I started, as I wrote, to consider canonical form when I reached a diagonal generation.

Lets say I preferred in that first test to stay on the safe side.

The result should be the same at the end of step 2 (peanuts in terms of performance).

It could be also that expanding the box 9 as a third step would lead to more eliminations.

box 9 is part of the perm .

The right test (I'll do it) is to check that applying perms earlier leads to the same result as applying it in a step where band1; stack1 and box9 are expanded

champagne

by **eleven** » Wed Mar 14, 2012 4:45 pm

::: comment :::

Thanks, champagne.

Another idea to avoid checking equivalent puzzles multiple times is this:
Every solution can be transformed to a minlex form in this pattern.

Code: Select all: +-------+-------+-------+ | 1 2 . | 3 . . | . . . | | Y . . | . . . | x . . | | . . x | . . . | . . . | +-------+-------+-------+ | a . . | x . . | x . . | | . . . | . b . | . x . | | . . . | . . d | . . x | +-------+-------+-------+ | . x . | x . . | x . . | | . . . | . x . | . x . | | . . . | . . x | . . x | +-------+-------+-------+

Then you can say, that Y is 3 or 4, a>=3, d>b, and the new digits (> 3, top down) are in the sequence 4 to 9. (Additionally at least 8 numbers must be given.)
Following these rules all resulting puzzles should be unique.

With a program i counted, that you get 51690 different ways having the first 12 cells fixed (down to d), 353984 to have the first 2 bands fixed.
So you would have to solve 51690 {+8} or 353984 {+9} for an exhaustive search (more than 200 bio possible puzzles). I guess, this would take me more than 2 weeks, but if your computer is 10 times faster ... (maybe also filtering the single starters saved much time).

by **dobrichev** » Wed Mar 14, 2012 8:53 pm

::: comment :::

eleven wrote:
Code: Select all
+-------+-------+-------+ | 1 2 . | 3 . . | . . . | | Y . . | . . . | x . . | | . . x | . . . | . . . | +-------+-------+-------+ | a . . | x . . | x . . | | . . . | . b . | . x . | | . . . | . . d | . . x | +-------+-------+-------+ | . x . | x . . | x . . | | . . . | . x . | . x . | | . . . | . . x | . . x | +-------+-------+-------+

Then you can say, that Y is 3 or 4, a>=3, d>b, and the new digits (> 3, top down) are in the sequence 4 to 9. (Additionally at least 8 numbers must be given.)
Following these rules all resulting puzzles should be unique.

With a program i counted, that you get 51690 different ways having the first 12 cells fixed (down to d), 353984 to have the first 2 bands fixed.
So you would have to solve 51690 {+8} or 353984 {+9} for an exhaustive search (more than 200 bio possible puzzles). I guess, this would take me more than 2 weeks, but if your computer is 10 times faster ... (maybe also filtering the single starters saved much time).

Hi eleven,
Does your counting program take into account additional conditions like a != Y?
What about fixing the four digits in the box 1 of your example to 1,2,3,4? It is valid even for non-symmetrical patterns and of course additional constraints might be applied to exploit the symmetry. The factor of 2 (for Y fixed instead of 3,4) * factor of 6 (or 7?) for the x in box 1 fixed = 12, / 7 for r1c4 floating ~ 2.
Can you examine this approach and compare to your original "band" approach? A possible extension is d>b>x in box 5. r4c1>r1c4 is still valid.

by **eleven** » Wed Mar 14, 2012 9:32 pm

Hi,

first it was a mistake, that a must be >=3, it can be 2 as well, giving 60305 {+8} and over 400000 {+7}.

dobrichev wrote:Does your counting program take into account additional conditions like a != Y?

Yes.

What about fixing the four digits in the box 1 of your example to 1,2,3,4? It is valid even for non-symmetrical patterns and of course additional constraints might be applied to exploit the symmetry. The factor of 2 (for Y fixed instead of 3,4) * factor of 6 (or 7?) for the x in box 1 fixed = 12, / 7 for r1c4 floating ~ 2.

Hm, i must not miss the puzzles, which for this pattern have a 3 in r2c1 in the minlex form.

Can you examine this approach and compare to your original "band" approach? A possible extension is d>b>x in box 5. r4c1>r1c4 is still valid.

Can't give it a deeper thought now, soccer running on tv

But what i can say is, that the (sub)puzzles i enumerated all were [edit:]non equivalent and multisolution.

by **ronk** » Wed Mar 14, 2012 9:43 pm

eleven wrote:Another idea to avoid checking equivalent puzzles multiple times is this:
Every solution can be transformed to a minlex form in this pattern.
Code: Select all
+-------+-------+-------+ | 1 2 . | 3 . . | . . . | | Y . . | . . . | x . . | | . . x | . . . | . . . | +-------+-------+-------+ | a . . | x . . | x . . | | . . . | . b . | . x . | | . . . | . . d | . . x | +-------+-------+-------+ | . x . | x . . | x . . | | . . . | . x . | . x . | | . . . | . . x | . . x | +-------+-------+-------+

Then you can say, that Y is 3 or 4, a>=3, d>b, and the new digits (> 3, top down) are in the sequence 4 to 9. (Additionally at least 8 numbers must be given.) Following these rules all resulting puzzles should be unique.

According to gsf's program, this pattern has four automorphisms, so it makes sense that two restrictions are permitted to limit this to one automorphism. One multiplier of 2 is due to diagonal symmetry, but I don't see how your a, Y, d and b limits "avoid" this diagonal symmetry. [edit: OK, dobrichev's [r4c1] >= [r1c4] rephrasing makes your a>=3 clearer.]

I don't readily see the cause for the other multiplier of 2. [edit: OK, I think I now see this one too. It's the cyclic swap r{56}{89}c{56}{89}, so your d>b works just fine too.]

by **champagne** » Thu Mar 15, 2012 9:11 am

eleven wrote:::: comment :::

Thanks, champagne.

Another idea to avoid checking equivalent puzzles multiple times is this:
Every solution can be transformed to a minlex form in this pattern.
Code: Select all
+-------+-------+-------+ | 1 2 . | 3 . . | . . . | | Y . . | . . . | x . . | | . . x | . . . | . . . | +-------+-------+-------+ | a . . | x . . | x . . | | . . . | . b . | . x . | | . . . | . . d | . . x | +-------+-------+-------+ | . x . | x . . | x . . | | . . . | . x . | . x . | | . . . | . . x | . . x | +-------+-------+-------+

Then you can say, that Y is 3 or 4, a>=3, d>b, and the new digits (> 3, top down) are in the sequence 4 to 9. (Additionally at least 8 numbers must be given.)
Following these rules all resulting puzzles should be unique.

With a program i counted, that you get 51690 different ways having the first 12 cells fixed (down to d), 353984 to have the first 2 bands fixed.
So you would have to solve 51690 {+8} or 353984 {+9} for an exhaustive search (more than 200 bio possible puzzles). I guess, this would take me more than 2 weeks, but if your computer is 10 times faster ... (maybe also filtering the single starters saved much time).

Hi eleven,

that post generated already many comments. Let me add some.

I am reluctant in principle to consider any "tailored made" adjustment to the code.

In that specific case, if other comments are correct, it seems that the new idea is another way to express the valid permutations in the pattern.

That discussion makes me even more cautious on use of permutations before all conditions are there.

I am restarting the scan in the following conditions:

first step expand rows 1;3;7;9 and columns 1;3;7;9
that step gives a valid configuration for all identified permutations.

second step expand box 5 (same remark)

then split the results in several lots and go to the end in parallel processing.

I made 10 lots and I am running part of them. (I don't have enough cores to run all them together)

It seems that you are pessimistic as far as run times are concerned. After one hour, I think that some lots will be finished by to-morrow.

Here below my partial results, but I have to check carefully now the validity of my "canonical in pattern" code. This is a relatively fresh code and it worth a deeper investigation.

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

Code: Select all: second step: add box 5 ..A...A...3...1.4.A.......A.....B.1.....B.....7.B.B...A.......A.8.4...7...A...A..

raw generation 74824
net generation 57990

The second step ends with 12 assigned cells, but not the same as in your example.
The order of magnitude of the result is the same

51690 different seeds in your case
57990 in that process.

champagne

by **eleven** » Thu Mar 15, 2012 11:14 am

Hi,

my main interest was, if it is feasible to make an exhaustive search in a 20 clue pattern on a pc. So i had to know the order of magnitude, how much puzzles have to be solved for that.

I saw, that my approach to enumerate all non equivalent puzzles for that pattern still is not perfect. I now got 62962 subpuzzles with 12 fixed givens, which indeed were non equivalent. But when i checked the 13 clue puzzles with my own normalization, it turned out, that almost 5% were equivalents. It was a mistake to use gsf's program with the "qFN -f'%#.c'" option for normalization, because the puzzles have multi solutions.

For those interested, here are 2 equivalent puzzles i enumerated:

Code: Select all: 12.3.....3.....1....4......5..1..3......6..4......7..8.1.2..5......4..7......8..6 12.3.....3.....1....4......5..1..3......6..7......8..4.1.2..5......7..8......4..6

So i am left now with 306283 non equivalent 12 clue puzzles for a {+7} search.
I counted the number of puzzles i get with adding digits in the remaining 7 cells and got 161 billions.

When using the bb_solver on my pc (dual core, 32 bit 3GHz), i can only do about 1 bio per hour, which means, that for me an exhaustive search would take a week. This is much less, than i had expected before. But in the moment i can't do that, so i am curiously expecting champagne's results.

by **ronk** » Thu Mar 15, 2012 12:08 pm

champagne wrote:I got the following results
Code: Select all
first step ..B...B...B...B.B.B.......B.....1.1.....1.....1.1.1...1.......1.1.1...1...1...1..
rows 1;3 columns 1;3
raw generation 354
net generation 123

Shouldn't the lower number be '60' so as to match the sixty sub-puzzles you listed here.

by **champagne** » Thu Mar 15, 2012 12:41 pm

ronk wrote:
champagne wrote:I got the following results
Code: Select all
first step ..B...B...B...B.B.B.......B.....1.1.....1.....1.1.1...1.......1.1.1...1...1...1..
rows 1;3 columns 1;3
raw generation 354
net generation 123

Shouldn't the lower number be '60' so as to match the sixty sub-puzzles you listed here.

I made a copy and paste mistake.
I edited my post

the first command has 'B' where we find 'A' in the second one, pointing on rows 1;3 7;9 columns 1;3 7;9
thanks

champagne

by **ronk** » Thu Mar 15, 2012 12:53 pm

champagne wrote:I made a copy and paste mistake.
I edited my post

the first command has 'B' where we find 'A' in the second one, pointing on rows 1;3 7;9 columns 1;3 7;9

I have no idea what the difference between your 'A' and 'B' might be. Did you define them somewhere?

For that matter, what exactly does "rows 1;3 7;9 columns 1;3 7;9" mean? Just the four rows and four columns? Or bands 1 and 3 and stacks 1 and 3? Or something else?

by **champagne** » Thu Mar 15, 2012 1:03 pm

ronk wrote:
champagne wrote:I made a copy and paste mistake.
I edited my post

the first command has 'B' where we find 'A' in the second one, pointing on rows 1;3 7;9 columns 1;3 7;9

I have no idea what the difference between your 'A' and 'B' might be. Did you define them somewhere?

For that matter, what exactly does "rows 1;3 7;9 columns 1;3 7;9" mean? Just the four rows and four columns? Or bands 1 and 3 and stacks 1 and 3? Or something else?

As shown in my first example, for each batch

'A' means already assigned position
'B' means position to assign in that batch

In that second run, my first step is to assign the 8 cells belonging to rows 1357 columns 1357
This is the smaller lot fitting with all available permutations

champagne

by **ronk** » Thu Mar 15, 2012 2:41 pm

champagne wrote: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?

The New Sudoku Players' Forum

Patterns Game Strategies

Re: Patterns Game

Re: Patterns Game

Re:

Patterns Game

Re: Patterns Game

Re: Patterns Game

Exhaustive generation of pzls for pattern game 0169

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