The New Sudoku Players' Forum

[Serg]

Hi, Afmob!

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.

[Afmob]

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.

[eleven]

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 ...

[Serg]

Hi, eleven!

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

[Afmob]

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.


[eleven]

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.

[Afmob]

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


[eleven]

Congratulations on pattern #117 !

[coloin]

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

[Afmob]

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.

[Serg]

Hi, Afmob!

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

[coloin]

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

[Afmob]

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.

[Serg]

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

[Afmob]

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.