Symmetric 18s

Everything about Sudoku that doesn't fit in one of the other sections

Re:

Postby Serg » Mon Jun 10, 2013 10:48 am

Hi, Afmob!
Afmob wrote:This means that I "only" have to check about 66,000 patterns and then we know all symmetric 18 clue Sudokus having a unique solution. I think it's fair to estimate that the computation finishes this year.

Glad to hear you are doing exhaustive search for vertically symmetric 18-clue patterns (or puzzles?). It would be fine to know your future plans to do this search. It would be not so rational to do the same works in parallel (though it's important to verify results). Have you already done partial search? (What does "66,000 patterns" mean?)

Serg

P.S. I used not all known maximal patterns to filter out impossible patterns. (I used "one-crossing-free" patterns only, but about 30 extra maximal patterns are known that are not "one-crossing-free" patterns.) I am planning to use remaining maximal patterns coming weeks (I should modify my filter's code.) So, It can be quite possible to reduce 100000 patterns list further in rather short time.
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Postby Afmob » Mon Jun 10, 2013 11:07 am

I've already checked several patterns therefore I don't need to check all 100,728 patterns. Of course, I would appreciate further reductions if they are are verified by blue or someone else besides you.
Afmob
 
Posts: 130
Joined: 28 June 2011

Re: Symmetric 18s

Postby eleven » Mon Jun 10, 2013 7:21 pm

Serg wrote:It turns out, 18-clue vertically symmetric valid patterns containing 8 clues in the central column (c5) are impossible.

Ah, i was sure they would not be possible, but i could not prove it.

There is another kind of patterns, for which both olimpia and i searched for valid puzzles in vain, so it seems improbable for me, that they have one. These are patterns with diagonals within a box such as:
Code: Select all
X . . . . . . . X
. X . . . . . X .
. . X . . . X . .

But to check them all, will still be a long task, i guess - and therefore i can't be sure at all ...
eleven
 
Posts: 1559
Joined: 10 February 2008

Re: Symmetric 18s

Postby Serg » Wed Jun 12, 2013 7:07 am

Hi, eleven!
eleven wrote:There is another kind of patterns, for which both olimpia and i searched for valid puzzles in vain, so it seems improbable for me, that they have one. These are patterns with diagonals within a box such as:
Code: Select all
X . . . . . . . X
. X . . . . . X .
. . X . . . X . .

But to check them all, will still be a long task, i guess - and therefore i can't be sure at all ...

I analyzed all types of boxes in the current possible 18-clue patterns list (100728 patterns). Here is statistics - how many patterns contain (at least one) box of the type
considered.
Code: Select all
Box types frequency

. . .     Box participates 28822 patterns
. . .
. . .

. . .     Box participates 93876 patterns
. . .
. . x

. . .     Box participates 61425 patterns
. . x
. x .

. . .     Box participates 51086 patterns
. . .
. x x

. . .     Box participates 48388 patterns
. . x
. . x

. . .     Box participates 18248 patterns
. . x
. x x

. . .     Box participates 16387 patterns
. . .
x x x

. . x     Box participates  5691 patterns
. . x
. . x

. . .     Box participates 46327 patterns
. . x
x x .

. . x     Box participates 14005 patterns
. . x
. x .

. . x     Box participates  4145 patterns
. x .
x . .

. . x     Box participates 10261 patterns
. . x
x x .

. . .     Box participates 15930 patterns
. . x
x x x

. . x     Box participates   839 patterns
. . x
. x x

. . .     Box participates   507 patterns
. x x
x . x

. . x     Box participates   692 patterns
. x .
. x x

. . .     Box participates 18232 patterns
. x x
. x x

. . x     Box participates  1299 patterns
. x .
x . x

. . x     Box participates  3079 patterns
. . x
x x x

. . .     Box participates  9010 patterns
. x x
x x x

. . x     Box participates    15 patterns
. x x
. x x

. . x     Box participates    11 patterns
. x x
x . x

. . x     Box participates    11 patterns
. x .
x x x

x . .     Box participates  6889 patterns
. x x
. x x

. . x     Box participates    18 patterns
. x x
x x .

. . x     Box participates     0 patterns
. x x
x x x

. . .     Box participates  2078 patterns
x x x
x x x

. x x     Box participates  1314 patterns
. x x
. x x

. x x     Box participates     0 patterns
. x x
x . x

. . x     Box participates  3072 patterns
x x .
x x x

. x x     Box participates     0 patterns
x . x
x x .

. x x     Box participates     0 patterns
x . x
x x x

. . x     Box participates   569 patterns
x x x
x x x

. x x     Box participates   573 patterns
. x x
x x x

. x x     Box participates   117 patterns
x x x
x x x

x x x     Box participates    14 patterns
x x x
x x x

Number of processed patterns : 100728

Total program execution time: 2 seconds

As you can see, some box configurations having 6 or 7 clues can be excluded only at the moment. Even box containing all 9 clues was found in 14 patterns!

Serg
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Re: Symmetric 18s

Postby Afmob » Mon Aug 05, 2013 9:57 am

I might have found a new vertical symmetric 18 clue puzzle:
Code: Select all
....1.......2.3.....4...5.....3.4.....5...6....7...8.....587....2.....1..4.....3.

Validation would be appreciated since I didn't find it in eleven's list though there is another puzzle with the same pattern.
Code: Select all
....1.......2.3.....4...5.....3.4.....5...6....7...8.....765....2.....1..4.....3.
Afmob
 
Posts: 130
Joined: 28 June 2011

Re: Symmetric 18s

Postby eleven » Mon Aug 05, 2013 11:49 am

Yes, it's new, at least it was never posted afaik.
I wondered, that i did not find it with neighbourhood search. But the puzzle with the same pattern is the last in my list, posted by Coloin, and i had stopped any search at that time.
After that only 2 more puzzles were posted by Coloin, both with new patterns. So i don't know, if Coloin had found more, but only posted new patterns.
eleven
 
Posts: 1559
Joined: 10 February 2008

Re: Symmetric 18s

Postby Afmob » Tue Aug 06, 2013 6:21 am

It seems I've found another new one, this time with a new pattern:

Code: Select all
............1.2.....3...4......3.....5.....1.1...4...6...3.5.....6...7..7.4...8.9
Afmob
 
Posts: 130
Joined: 28 June 2011

Re: Symmetric 18s

Postby eleven » Tue Aug 06, 2013 8:53 am

Congratulations on pattern #117 !
eleven
 
Posts: 1559
Joined: 10 February 2008

Re: Symmetric 18s

Postby coloin » Tue Aug 06, 2013 9:50 am

Yes ! Congratulations on finding that !

Maybe i would have better methods now - I will have to think back on how i came up with my contributions..... !
Was it as a result of a specific pattern search ?

C
coloin
 
Posts: 1637
Joined: 05 May 2005

Re: Symmetric 18s

Postby Afmob » Tue Aug 06, 2013 9:59 am

I'm just going through the patterns provided by Serg. Still got 51,000 left to analyze but I hope to finish the computation this year.
Afmob
 
Posts: 130
Joined: 28 June 2011

Re: Symmetric 18s

Postby Serg » Tue Aug 06, 2013 10:56 pm

Hi, Afmob!
Afmob wrote:It seems I've found another new one, this time with a new pattern:

Code: Select all
............1.2.....3...4......3.....5.....1.1...4...6...3.5.....6...7..7.4...8.9

Congratulations! You've found new (#117) vertically symmetric pattern! (This puzzle is minimal.) I'll update my list of observed patterns.

Serg
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Re: Symmetric 18s

Postby coloin » Thu Aug 08, 2013 10:57 pm

Afmob wrote:I'm just going through the patterns provided by Serg. Still got 51,000 left to analyze but I hope to finish the computation this year.

If you are serious .... thats fairly impressive [ > 300 /day ] and a lot of iterations !

Maybe it can be improved furthur

Looking back .... My method was to generate minimal [and non-minimal] symmetrical 19s [3 or 5 clues in c5]
I reckoned that it was pointless to try to find 18s with 6 or more clues in c5. [as with 6 or more clues in a row or box]
I then performed a {-1} on the non-minimals
gsf's program would then confirm the symmetry [v]
This effectively searched 3 or 5 patterns simultaeously. Eventually I got new patterns with puzzles.

Maybe you could generate symmetrical puzzles with a complete c5 [123456789]
with either 8 or 7 symetrical clues either side of c5 [1 clue needed either side in c4 and c6]
thus you could search for up to 36 [9*8 / 2] or 126 [9!/ 4!*5!] patterns each time, picking 2 from 9 or 4 from 9 respectivly.
I am not sure if this will increase your iterations needed per 16+9 or 14+9 pattern........
.......
on a basic 18 clue pattern
maybe thats ~ 4 fixed plus iterating 7 pairs of clues ..... using clever reductions .....
.......
on a 9 plus 14 pattern
that would be 9 fixed plus 1 clue each in c4 and c6 [2 ED ways] plus iterating 6 pairs of clues

I may be way off here if i havent fully understood how you are iterating those patterns so fast !

C
coloin
 
Posts: 1637
Joined: 05 May 2005

Re: Symmetric 18s

Postby Afmob » Fri Aug 09, 2013 4:14 am

coloin wrote:I may be way off here if i havent fully understood how you are iterating those patterns so fast !

I use parallel computing (31+1 cores) and the modified version of ZhouSolver provided by Jason.
Afmob
 
Posts: 130
Joined: 28 June 2011

Re: Symmetric 18s

Postby Serg » Sun Aug 25, 2013 3:39 pm

Hi, people!
I've just finished verification of eleven's list of possible 18-clue non-equivalent vertically symmetric patterns (patterns having 2 empty rows/columns in a band/stack were filtered out). I confirm correctness of eleven's list (it contains 294,313 patterns).

I generated also 18-clue non-equivalent vertically symmetric patterns w/o filtering out patterns having 2 empty rows/columns in a band/stack (so called "raw" patterns). There are 712,663 such patterns. This number can be useful for mathematical cross-check of this result. Zipped file can be downloaded here.

Serg
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Re: Symmetric 18s

Postby Afmob » Fri Oct 11, 2013 8:39 pm

Here is (hopefully) another new symmetric 18 clue Sudoku:
Code: Select all
............123.....4...5..............456....1.....3....2.1.....6...4..4.5...7.8

There are still about 34,000 patterns left to be analyzed but I'm less optimistic that the computation will be finished this year. This is due to a lot of the current patterns having billions of essentially different puzzles and I'm using some CPU power for other purposes such as the subset & superset method.

Edit: As noted by Serg and coloin, this puzzle is not new since it is isomorphic to this one.
Last edited by Afmob on Sat Oct 12, 2013 8:28 pm, edited 1 time in total.
Afmob
 
Posts: 130
Joined: 28 June 2011

PreviousNext

Return to General