The New Sudoku Players' Forum

by **gfroyle** » Sat Apr 22, 2006 12:23 pm

JPF wrote:Earlier in this thread, Ruud made the same comment, that I still have in mind :
Ruud wrote:Have you considered that simultaneous permutation of rows 1-3 & 7-9 and columns 1-3 & 7-9 allow you to reduce the number of patterns that you need to find?

Actually there are (a very few) more equivalences than that available..

The simultaneous permutations as outlined above gives 6 operations that all have the property that the number of orbits of each size are preserved in the 6 equivalent patterns. So if the original has 1 orbits of length 8, 2 of length 4 and 1 of length 1, then so will all the 5 others.

But this is not necessary.... in some circumstances it is possible to use a different type of operation that "splits" an orbit of length 8 into two orbits of length 4 or "merges" two of length 4 to give one of length 8, yet still gives an equivalent puzzle.

Here is an example:

Take this pattern: 16-8-4-0-0

Code: Select all: x.. ... ..x .x. ... .x. ..x ... x.. ... ... ... ... ... ... ... ... ... ..x ... x.. .x. ... .x. x.. ... ..x

If we apply the permutation C2 <-> C3 and C7 <-> C8 then we get 16-4-0-0-0

Code: Select all: x.. ... ..x ..x ... x.. .x. ... .x. ... ... ... ... ... ... ... ... ... .x. ... .x. ..x ... x.. x.. ... ..x

In fact, we end up with 4 equivalent configurations

16-8-4-0-0 16-4-0-0-0 8-0-4-0-0 4-8-0-0-0

Anyway, here is a list of all the 20-clue S-equivalence classes.. one per line. Of course, some of these can immediately be seen to be impossible patterns for a valid puzzle, so there are slightly fewer again to check.

Code: Select all: 20: 16-13-0-0-0 16-4-5-0-0 25-0-4-0-0 21-8-0-0-0 8-9-4-0-0 4-8-5-0-0 20: 16-12-4-0-0 24-8-4-0-0 20-8-4-0-0 20: 16-12-1-0-0 16-5-4-0-0 24-1-4-0-0 20-8-1-0-0 9-8-4-0-0 5-8-4-0-0 20: 16-12-0-2-0 16-4-4-2-0 24-0-4-2-0 20-8-0-2-0 8-8-4-2-0 4-8-4-2-0 20: 16-12-0-1-0 16-4-4-1-0 24-0-4-1-0 20-8-0-1-0 8-8-4-1-0 4-8-4-1-0 20: 16-11-0-0-0 16-0-7-0-0 19-8-0-0-0 19-0-4-0-0 0-11-4-0-0 0-8-7-0-0 20: 16-10-4-0-0 16-8-6-0-0 18-8-4-0-0 18-4-0-0-0 8-0-6-0-0 4-10-0-0-0 20: 16-10-1-0-0 16-1-6-0-0 18-8-1-0-0 18-1-4-0-0 1-10-4-0-0 1-8-6-0-0 20: 16-10-0-2-0 16-0-6-2-0 18-8-0-2-0 18-0-4-2-0 0-10-4-2-0 0-8-6-2-0 20: 16-10-0-1-0 16-0-6-1-0 18-8-0-1-0 18-0-4-1-0 0-10-4-1-0 0-8-6-1-0 20: 16-9-5-0-0 16-5-1-0-0 17-9-4-0-0 17-8-5-0-0 9-1-4-0-0 5-8-1-0-0 20: 16-9-4-2-0 16-8-5-2-0 17-8-4-2-0 17-4-0-2-0 8-0-5-2-0 4-9-0-2-0 20: 16-9-4-1-0 16-8-5-1-0 17-8-4-1-0 17-4-0-1-0 8-0-5-1-0 4-9-0-1-0 20: 16-9-2-0-0 16-2-5-0-0 17-8-2-0-0 17-2-4-0-0 2-9-4-0-0 2-8-5-0-0 20: 16-9-1-2-0 16-1-5-2-0 17-8-1-2-0 17-1-4-2-0 1-9-4-2-0 1-8-5-2-0 20: 16-9-1-1-0 16-1-5-1-0 17-8-1-1-0 17-1-4-1-0 1-9-4-1-0 1-8-5-1-0 20: 16-9-0-3-0 16-0-5-3-0 17-8-0-3-0 17-0-4-3-0 0-9-4-3-0 0-8-5-3-0 20: 16-8-4-3-0 16-4-0-3-0 8-0-4-3-0 4-8-0-3-0 20: 16-8-3-0-0 16-3-4-0-0 8-0-3-0-0 4-3-0-0-0 3-8-4-0-0 3-4-0-0-0 20: 16-8-2-2-0 16-2-4-2-0 8-0-2-2-0 4-2-0-2-0 2-8-4-2-0 2-4-0-2-0 20: 16-8-2-1-0 16-2-4-1-0 8-0-2-1-0 4-2-0-1-0 2-8-4-1-0 2-4-0-1-0 20: 16-8-1-3-0 16-1-4-3-0 8-0-1-3-0 4-1-0-3-0 1-8-4-3-0 1-4-0-3-0 20: 16-6-0-0-0 16-4-2-0-0 8-2-4-0-0 10-0-4-0-0 4-8-2-0-0 6-8-0-0-0 20: 16-5-0-2-0 16-4-1-2-0 8-1-4-2-0 9-0-4-2-0 4-8-1-2-0 5-8-0-2-0 20: 16-5-0-1-0 16-4-1-1-0 8-1-4-1-0 9-0-4-1-0 4-8-1-1-0 5-8-0-1-0 20: 24-9-0-0-0 25-8-0-0-0 20-0-5-0-0 21-0-4-0-0 0-13-4-0-0 0-12-5-0-0 20: 24-8-1-0-0 20-1-4-0-0 1-12-4-0-0 20: 24-8-0-2-0 20-0-4-2-0 0-12-4-2-0 20: 24-8-0-1-0 20-0-4-1-0 0-12-4-1-0 20: 24-4-0-0-0 20-4-0-0-0 8-4-4-0-0 12-8-0-0-0 12-0-4-0-0 4-12-0-0-0 20: 24-2-0-0-0 20-0-2-0-0 0-12-2-0-0 0-6-4-0-0 10-8-0-0-0 6-0-4-0-0 20: 24-1-1-0-0 20-1-1-0-0 9-8-1-0-0 5-1-4-0-0 1-12-1-0-0 1-5-4-0-0 20: 24-1-0-2-0 20-0-1-2-0 0-12-1-2-0 0-5-4-2-0 9-8-0-2-0 5-0-4-2-0 20: 24-1-0-1-0 20-0-1-1-0 0-12-1-1-0 0-5-4-1-0 9-8-0-1-0 5-0-4-1-0 20: 24-0-5-0-0 20-9-0-0-0 17-12-0-0-0 17-4-4-0-0 8-8-5-0-0 4-9-4-0-0 20: 24-0-2-0-0 20-2-0-0-0 8-8-2-0-0 4-2-4-0-0 2-12-0-0-0 2-4-4-0-0 20: 24-0-1-2-0 20-1-0-2-0 8-8-1-2-0 4-1-4-2-0 1-12-0-2-0 1-4-4-2-0 20: 24-0-1-1-0 20-1-0-1-0 8-8-1-1-0 4-1-4-1-0 1-12-0-1-0 1-4-4-1-0 20: 28-0-0-0-0 8-12-0-0-0 4-4-4-0-0 20: 24-0-0-3-0 20-0-0-3-0 0-12-0-3-0 0-4-4-3-0 8-8-0-3-0 4-0-4-3-0 20: 26-0-0-0-0 22-0-0-0-0 0-14-0-0-0 0-4-6-0-0 8-10-0-0-0 4-0-6-0-0 20: 25-1-0-0-0 21-0-1-0-0 0-13-1-0-0 0-5-5-0-0 9-9-0-0-0 5-0-5-0-0 20: 25-0-1-0-0 21-1-0-0-0 8-9-1-0-0 4-1-5-0-0 1-13-0-0-0 1-4-5-0-0 20: 25-0-0-2-0 21-0-0-2-0 0-13-0-2-0 0-4-5-2-0 8-9-0-2-0 4-0-5-2-0 20: 25-0-0-1-0 21-0-0-1-0 0-13-0-1-0 0-4-5-1-0 8-9-0-1-0 4-0-5-1-0 20: 16-3-1-0-0 16-1-3-0-0 3-8-1-0-0 3-1-4-0-0 1-8-3-0-0 1-3-4-0-0 20: 16-3-0-2-0 16-0-3-2-0 0-8-3-2-0 0-3-4-2-0 3-8-0-2-0 3-0-4-2-0 20: 16-3-0-1-0 16-0-3-1-0 0-8-3-1-0 0-3-4-1-0 3-8-0-1-0 3-0-4-1-0 20: 16-2-2-0-0 2-8-2-0-0 2-2-4-0-0 20: 16-2-1-2-0 16-1-2-2-0 2-8-1-2-0 2-1-4-2-0 1-8-2-2-0 1-2-4-2-0 20: 16-2-1-1-0 16-1-2-1-0 2-8-1-1-0 2-1-4-1-0 1-8-2-1-0 1-2-4-1-0 20: 16-2-0-3-0 16-0-2-3-0 0-8-2-3-0 0-2-4-3-0 2-8-0-3-0 2-0-4-3-0 20: 16-1-1-3-0 1-8-1-3-0 1-1-4-3-0 20: 18-9-0-0-0 18-0-5-0-0 17-10-0-0-0 17-0-6-0-0 0-10-5-0-0 0-9-6-0-0 20: 18-2-0-0-0 18-0-2-0-0 0-10-2-0-0 0-2-6-0-0 2-10-0-0-0 2-0-6-0-0 20: 18-1-1-0-0 1-10-1-0-0 1-1-6-0-0 20: 18-1-0-2-0 18-0-1-2-0 0-10-1-2-0 0-1-6-2-0 1-10-0-2-0 1-0-6-2-0 20: 18-1-0-1-0 18-0-1-1-0 0-10-1-1-0 0-1-6-1-0 1-10-0-1-0 1-0-6-1-0 20: 18-0-0-3-0 0-10-0-3-0 0-0-6-3-0 20: 19-1-0-0-0 19-0-1-0-0 0-11-1-0-0 0-1-7-0-0 1-11-0-0-0 1-0-7-0-0 20: 19-0-0-2-0 0-11-0-2-0 0-0-7-2-0 20: 19-0-0-1-0 0-11-0-1-0 0-0-7-1-0 20: 17-9-1-0-0 17-1-5-0-0 9-1-1-0-0 5-1-1-0-0 1-9-5-0-0 1-5-1-0-0 20: 17-9-0-2-0 17-0-5-2-0 0-9-5-2-0 0-5-1-2-0 9-1-0-2-0 5-0-1-2-0 20: 17-9-0-1-0 17-0-5-1-0 0-9-5-1-0 0-5-1-1-0 9-1-0-1-0 5-0-1-1-0 20: 17-5-0-0-0 17-4-1-0-0 8-1-5-0-0 9-0-5-0-0 4-9-1-0-0 5-9-0-0-0 20: 17-3-0-0-0 17-0-3-0-0 0-9-3-0-0 0-3-5-0-0 3-9-0-0-0 3-0-5-0-0 20: 17-2-1-0-0 17-1-2-0-0 2-9-1-0-0 2-1-5-0-0 1-9-2-0-0 1-2-5-0-0 20: 17-2-0-2-0 17-0-2-2-0 0-9-2-2-0 0-2-5-2-0 2-9-0-2-0 2-0-5-2-0 20: 17-2-0-1-0 17-0-2-1-0 0-9-2-1-0 0-2-5-1-0 2-9-0-1-0 2-0-5-1-0 20: 17-1-1-2-0 1-9-1-2-0 1-1-5-2-0 20: 17-1-1-1-0 1-9-1-1-0 1-1-5-1-0 20: 17-1-0-3-0 17-0-1-3-0 0-9-1-3-0 0-1-5-3-0 1-9-0-3-0 1-0-5-3-0 20: 0-7-0-0-0 0-4-3-0-0 8-3-0-0-0 11-0-0-0-0 4-0-3-0-0 7-0-0-0-0 20: 0-6-1-0-0 0-5-2-0-0 10-1-0-0-0 9-2-0-0-0 6-0-1-0-0 5-0-2-0-0 20: 0-6-0-2-0 0-4-2-2-0 8-2-0-2-0 10-0-0-2-0 4-0-2-2-0 6-0-0-2-0 20: 0-6-0-1-0 0-4-2-1-0 8-2-0-1-0 10-0-0-1-0 4-0-2-1-0 6-0-0-1-0 20: 0-5-0-3-0 0-4-1-3-0 8-1-0-3-0 9-0-0-3-0 4-0-1-3-0 5-0-0-3-0 20: 8-5-0-0-0 13-0-0-0-0 4-4-1-0-0 20: 8-4-1-0-0 12-1-0-0-0 12-0-1-0-0 9-4-0-0-0 4-5-0-0-0 5-4-0-0-0 20: 8-4-0-2-0 12-0-0-2-0 4-4-0-2-0 20: 8-4-0-1-0 12-0-0-1-0 4-4-0-1-0 20: 8-2-1-0-0 10-0-1-0-0 4-1-2-0-0 6-1-0-0-0 1-6-0-0-0 1-4-2-0-0 20: 8-1-2-0-0 9-0-2-0-0 4-2-1-0-0 5-2-0-0-0 2-5-0-0-0 2-4-1-0-0 20: 8-1-1-2-0 9-0-1-2-0 4-1-1-2-0 5-1-0-2-0 1-5-0-2-0 1-4-1-2-0 20: 8-1-1-1-0 9-0-1-1-0 4-1-1-1-0 5-1-0-1-0 1-5-0-1-0 1-4-1-1-0 20: 0-3-2-0-0 0-2-3-0-0 2-3-0-0-0 2-0-3-0-0 3-2-0-0-0 3-0-2-0-0 20: 0-3-1-2-0 0-1-3-2-0 3-1-0-2-0 3-0-1-2-0 1-3-0-2-0 1-0-3-2-0 20: 0-3-1-1-0 0-1-3-1-0 3-1-0-1-0 3-0-1-1-0 1-3-0-1-0 1-0-3-1-0 20: 0-3-0-3-0 0-0-3-3-0 3-0-0-3-0 20: 0-2-2-2-0 2-2-0-2-0 2-0-2-2-0 20: 0-2-2-1-0 2-2-0-1-0 2-0-2-1-0 20: 0-2-1-3-0 0-1-2-3-0 2-1-0-3-0 2-0-1-3-0 1-2-0-3-0 1-0-2-3-0 20: 2-2-1-0-0 2-1-2-0-0 1-2-2-0-0 20: 2-1-1-2-0 1-2-1-2-0 1-1-2-2-0 20: 2-1-1-1-0 1-2-1-1-0 1-1-2-1-0 20: 3-1-1-0-0 1-3-1-0-0 1-1-3-0-0 20: 1-1-1-3-0

Cheers

Gordon

by ab » Mon Apr 24, 2006 11:08 pm

here's another 20. not minimal though:

Code: Select all: ...|...|... .3.|9.8|.1. ..2|.7.|8.. ----------- .1.|...|.3. ..5|...|7.. .9.|...|.6. ----------- ..7|.5.|2.. .6.|1.7|.9. ...|...|... 0-9-6-0-0 0-10-5-0-0 17-0-6-0-0 17-10-0-0-0 18-0-5-0-0 18-9-0-0-0

and here's a minimal 20:

Code: Select all: ...|4.5|... ..9|...|8.. .7.|...|.4. ----------- 3..|9.8|..6 ...|...|... 8..|3.2|..5 ----------- .5.|...|.9. ..7|...|4.. ...|5.1|... 16-8-2-2-0 16-2-4-2-0 8-0-2-2-0 4-2-0-2-0 2-8-4-2-0 2-4-0-2-0

also I have annotated gfroyle's list with puzzles that are impossible and those that have been found to date:

Code: Select all: 20: 16-13-0-0-0 16-4-5-0-0 25-0-4-0-0 21-8-0-0-0 8-9-4-0-0 4-8-5-0-0 impossible 20: 16-12-4-0-0 24-8-4-0-0 20-8-4-0-0 impossible 20: 16-12-1-0-0 16-5-4-0-0 24-1-4-0-0 20-8-1-0-0 9-8-4-0-0 5-8-4-0-0 impossible 20: 16-12-0-2-0 16-4-4-2-0 24-0-4-2-0 20-8-0-2-0 8-8-4-2-0 4-8-4-2-0 20: 16-12-0-1-0 16-4-4-1-0 24-0-4-1-0 20-8-0-1-0 8-8-4-1-0 4-8-4-1-0 20: 16-11-0-0-0 16-0-7-0-0 19-8-0-0-0 19-0-4-0-0 0-11-4-0-0 0-8-7-0-0 impossible 20: 16-10-4-0-0 16-8-6-0-0 18-8-4-0-0 18-4-0-0-0 8-0-6-0-0 4-10-0-0-0 20: 16-10-1-0-0 16-1-6-0-0 18-8-1-0-0 18-1-4-0-0 1-10-4-0-0 1-8-6-0-0 20: 16-10-0-2-0 16-0-6-2-0 18-8-0-2-0 18-0-4-2-0 0-10-4-2-0 0-8-6-2-0 20: 16-10-0-1-0 16-0-6-1-0 18-8-0-1-0 18-0-4-1-0 0-10-4-1-0 0-8-6-1-0 done 20: 16-9-5-0-0 16-5-1-0-0 17-9-4-0-0 17-8-5-0-0 9-1-4-0-0 5-8-1-0-0 impossible 20: 16-9-4-2-0 16-8-5-2-0 17-8-4-2-0 17-4-0-2-0 8-0-5-2-0 4-9-0-2-0 done 20: 16-9-4-1-0 16-8-5-1-0 17-8-4-1-0 17-4-0-1-0 8-0-5-1-0 4-9-0-1-0 20: 16-9-2-0-0 16-2-5-0-0 17-8-2-0-0 17-2-4-0-0 2-9-4-0-0 2-8-5-0-0 done 20: 16-9-1-2-0 16-1-5-2-0 17-8-1-2-0 17-1-4-2-0 1-9-4-2-0 1-8-5-2-0 20: 16-9-1-1-0 16-1-5-1-0 17-8-1-1-0 17-1-4-1-0 1-9-4-1-0 1-8-5-1-0 20: 16-9-0-3-0 16-0-5-3-0 17-8-0-3-0 17-0-4-3-0 0-9-4-3-0 0-8-5-3-0 20: 16-8-4-3-0 16-4-0-3-0 8-0-4-3-0 4-8-0-3-0 20: 16-8-3-0-0 16-3-4-0-0 8-0-3-0-0 4-3-0-0-0 3-8-4-0-0 3-4-0-0-0 20: 16-8-2-2-0 16-2-4-2-0 8-0-2-2-0 4-2-0-2-0 2-8-4-2-0 2-4-0-2-0 done 20: 16-8-2-1-0 16-2-4-1-0 8-0-2-1-0 4-2-0-1-0 2-8-4-1-0 2-4-0-1-0 done 20: 16-8-1-3-0 16-1-4-3-0 8-0-1-3-0 4-1-0-3-0 1-8-4-3-0 1-4-0-3-0 20: 16-6-0-0-0 16-4-2-0-0 8-2-4-0-0 10-0-4-0-0 4-8-2-0-0 6-8-0-0-0 20: 16-5-0-2-0 16-4-1-2-0 8-1-4-2-0 9-0-4-2-0 4-8-1-2-0 5-8-0-2-0 done 20: 16-5-0-1-0 16-4-1-1-0 8-1-4-1-0 9-0-4-1-0 4-8-1-1-0 5-8-0-1-0 20: 24-9-0-0-0 25-8-0-0-0 20-0-5-0-0 21-0-4-0-0 0-13-4-0-0 0-12-5-0-0 impossible 20: 24-8-1-0-0 20-1-4-0-0 1-12-4-0-0 impossible 20: 24-8-0-2-0 20-0-4-2-0 0-12-4-2-0 20: 24-8-0-1-0 20-0-4-1-0 0-12-4-1-0 20: 24-4-0-0-0 20-4-0-0-0 8-4-4-0-0 12-8-0-0-0 12-0-4-0-0 4-12-0-0-0 impossible 20: 24-2-0-0-0 20-0-2-0-0 0-12-2-0-0 0-6-4-0-0 10-8-0-0-0 6-0-4-0-0 20: 24-1-1-0-0 20-1-1-0-0 9-8-1-0-0 5-1-4-0-0 1-12-1-0-0 1-5-4-0-0 impossible 20: 24-1-0-2-0 20-0-1-2-0 0-12-1-2-0 0-5-4-2-0 9-8-0-2-0 5-0-4-2-0 20: 24-1-0-1-0 20-0-1-1-0 0-12-1-1-0 0-5-4-1-0 9-8-0-1-0 5-0-4-1-0 20: 24-0-5-0-0 20-9-0-0-0 17-12-0-0-0 17-4-4-0-0 8-8-5-0-0 4-9-4-0-0 impossible 20: 24-0-2-0-0 20-2-0-0-0 8-8-2-0-0 4-2-4-0-0 2-12-0-0-0 2-4-4-0-0 20: 24-0-1-2-0 20-1-0-2-0 8-8-1-2-0 4-1-4-2-0 1-12-0-2-0 1-4-4-2-0 done 20: 24-0-1-1-0 20-1-0-1-0 8-8-1-1-0 4-1-4-1-0 1-12-0-1-0 1-4-4-1-0 20: 28-0-0-0-0 8-12-0-0-0 4-4-4-0-0 impossible 20: 24-0-0-3-0 20-0-0-3-0 0-12-0-3-0 0-4-4-3-0 8-8-0-3-0 4-0-4-3-0 20: 26-0-0-0-0 22-0-0-0-0 0-14-0-0-0 0-4-6-0-0 8-10-0-0-0 4-0-6-0-0 20: 25-1-0-0-0 21-0-1-0-0 0-13-1-0-0 0-5-5-0-0 9-9-0-0-0 5-0-5-0-0 impossible 20: 25-0-1-0-0 21-1-0-0-0 8-9-1-0-0 4-1-5-0-0 1-13-0-0-0 1-4-5-0-0 impossible 20: 25-0-0-2-0 21-0-0-2-0 0-13-0-2-0 0-4-5-2-0 8-9-0-2-0 4-0-5-2-0 20: 25-0-0-1-0 21-0-0-1-0 0-13-0-1-0 0-4-5-1-0 8-9-0-1-0 4-0-5-1-0 20: 16-3-1-0-0 16-1-3-0-0 3-8-1-0-0 3-1-4-0-0 1-8-3-0-0 1-3-4-0-0 done 20: 16-3-0-2-0 16-0-3-2-0 0-8-3-2-0 0-3-4-2-0 3-8-0-2-0 3-0-4-2-0 20: 16-3-0-1-0 16-0-3-1-0 0-8-3-1-0 0-3-4-1-0 3-8-0-1-0 3-0-4-1-0 20: 16-2-2-0-0 2-8-2-0-0 2-2-4-0-0 20: 16-2-1-2-0 16-1-2-2-0 2-8-1-2-0 2-1-4-2-0 1-8-2-2-0 1-2-4-2-0 20: 16-2-1-1-0 16-1-2-1-0 2-8-1-1-0 2-1-4-1-0 1-8-2-1-0 1-2-4-1-0 20: 16-2-0-3-0 16-0-2-3-0 0-8-2-3-0 0-2-4-3-0 2-8-0-3-0 2-0-4-3-0 20: 16-1-1-3-0 1-8-1-3-0 1-1-4-3-0 20: 18-9-0-0-0 18-0-5-0-0 17-10-0-0-0 17-0-6-0-0 0-10-5-0-0 0-9-6-0-0 done 20: 18-2-0-0-0 18-0-2-0-0 0-10-2-0-0 0-2-6-0-0 2-10-0-0-0 2-0-6-0-0 20: 18-1-1-0-0 1-10-1-0-0 1-1-6-0-0 20: 18-1-0-2-0 18-0-1-2-0 0-10-1-2-0 0-1-6-2-0 1-10-0-2-0 1-0-6-2-0 20: 18-1-0-1-0 18-0-1-1-0 0-10-1-1-0 0-1-6-1-0 1-10-0-1-0 1-0-6-1-0 20: 18-0-0-3-0 0-10-0-3-0 0-0-6-3-0 impossible 20: 19-1-0-0-0 19-0-1-0-0 0-11-1-0-0 0-1-7-0-0 1-11-0-0-0 1-0-7-0-0 20: 19-0-0-2-0 0-11-0-2-0 0-0-7-2-0 impossible 20: 19-0-0-1-0 0-11-0-1-0 0-0-7-1-0 impossible 20: 17-9-1-0-0 17-1-5-0-0 9-1-1-0-0 5-1-1-0-0 1-9-5-0-0 1-5-1-0-0 impossible 20: 17-9-0-2-0 17-0-5-2-0 0-9-5-2-0 0-5-1-2-0 9-1-0-2-0 5-0-1-2-0 20: 17-9-0-1-0 17-0-5-1-0 0-9-5-1-0 0-5-1-1-0 9-1-0-1-0 5-0-1-1-0 20: 17-5-0-0-0 17-4-1-0-0 8-1-5-0-0 9-0-5-0-0 4-9-1-0-0 5-9-0-0-0 impossible 20: 17-3-0-0-0 17-0-3-0-0 0-9-3-0-0 0-3-5-0-0 3-9-0-0-0 3-0-5-0-0 20: 17-2-1-0-0 17-1-2-0-0 2-9-1-0-0 2-1-5-0-0 1-9-2-0-0 1-2-5-0-0 20: 17-2-0-2-0 17-0-2-2-0 0-9-2-2-0 0-2-5-2-0 2-9-0-2-0 2-0-5-2-0 20: 17-2-0-1-0 17-0-2-1-0 0-9-2-1-0 0-2-5-1-0 2-9-0-1-0 2-0-5-1-0 20: 17-1-1-2-0 1-9-1-2-0 1-1-5-2-0 20: 17-1-1-1-0 1-9-1-1-0 1-1-5-1-0 20: 17-1-0-3-0 17-0-1-3-0 0-9-1-3-0 0-1-5-3-0 1-9-0-3-0 1-0-5-3-0 20: 0-7-0-0-0 0-4-3-0-0 8-3-0-0-0 11-0-0-0-0 4-0-3-0-0 7-0-0-0-0 20: 0-6-1-0-0 0-5-2-0-0 10-1-0-0-0 9-2-0-0-0 6-0-1-0-0 5-0-2-0-0 done 20: 0-6-0-2-0 0-4-2-2-0 8-2-0-2-0 10-0-0-2-0 4-0-2-2-0 6-0-0-2-0 20: 0-6-0-1-0 0-4-2-1-0 8-2-0-1-0 10-0-0-1-0 4-0-2-1-0 6-0-0-1-0 done 20: 0-5-0-3-0 0-4-1-3-0 8-1-0-3-0 9-0-0-3-0 4-0-1-3-0 5-0-0-3-0 20: 8-5-0-0-0 13-0-0-0-0 4-4-1-0-0 impossible 20: 8-4-1-0-0 12-1-0-0-0 12-0-1-0-0 9-4-0-0-0 4-5-0-0-0 5-4-0-0-0 impossible 20: 8-4-0-2-0 12-0-0-2-0 4-4-0-2-0 20: 8-4-0-1-0 12-0-0-1-0 4-4-0-1-0 20: 8-2-1-0-0 10-0-1-0-0 4-1-2-0-0 6-1-0-0-0 1-6-0-0-0 1-4-2-0-0 done 20: 8-1-2-0-0 9-0-2-0-0 4-2-1-0-0 5-2-0-0-0 2-5-0-0-0 2-4-1-0-0 done 20: 8-1-1-2-0 9-0-1-2-0 4-1-1-2-0 5-1-0-2-0 1-5-0-2-0 1-4-1-2-0 20: 8-1-1-1-0 9-0-1-1-0 4-1-1-1-0 5-1-0-1-0 1-5-0-1-0 1-4-1-1-0 20: 0-3-2-0-0 0-2-3-0-0 2-3-0-0-0 2-0-3-0-0 3-2-0-0-0 3-0-2-0-0 20: 0-3-1-2-0 0-1-3-2-0 3-1-0-2-0 3-0-1-2-0 1-3-0-2-0 1-0-3-2-0 20: 0-3-1-1-0 0-1-3-1-0 3-1-0-1-0 3-0-1-1-0 1-3-0-1-0 1-0-3-1-0 20: 0-3-0-3-0 0-0-3-3-0 3-0-0-3-0 impossible 20: 0-2-2-2-0 2-2-0-2-0 2-0-2-2-0 20: 0-2-2-1-0 2-2-0-1-0 2-0-2-1-0 20: 0-2-1-3-0 0-1-2-3-0 2-1-0-3-0 2-0-1-3-0 1-2-0-3-0 1-0-2-3-0 20: 2-2-1-0-0 2-1-2-0-0 1-2-2-0-0 20: 2-1-1-2-0 1-2-1-2-0 1-1-2-2-0 20: 2-1-1-1-0 1-2-1-1-0 1-1-2-1-0 20: 3-1-1-0-0 1-3-1-0-0 1-1-3-0-0 20: 1-1-1-3-0

Thanks for the list

I think searching for symmetric 20s is a reasonable task as any 20 gives rise to a 21, a 24 etc.

those 20s that are impossible or elusive will then provide a list of 21s or 24s to search for.

by **JPF** » Tue Apr 25, 2006 7:33 am

gfroyle wrote:Anyway, here is a list of all the 20-clue S-equivalence classes.. one per line.

Thanks for the list.
Actually, I was trying to supplement this list (at least for me) for every number of clues.
I don't undestand why it takes me years to do it.

gfroyle wrote:Of course, some of these can immediately be seen to be impossible patterns for a valid puzzle, so there are slightly fewer again to check.

ab wrote: also I have annotated gfroyle's list with puzzles that are impossible

I'm probably missing something.
How can you tell so quickly that 20 clues patterns don't have any solution ?
Like these ones :

Code: Select all: 16-13-0-0-0 x . . | . . . | . . x . x x | . x . | x x . . x . | . . . | . x . -------+-------+------- . . . | . . . | . . . . x . | . . . | . x . . . . | . . . | . . . -------+-------+------- . x . | . . . | . x . . x x | . x . | x x . x . . | . . . | . . x

Code: Select all: 0-13-4-0-0 . . . | . . . | . . . . x x | . x . | x x . . x x | . . . | x x . -------+-------+------- . . . | . . . | . . . . x . | . . . | . x . . . . | . . . | . . . -------+-------+------- . x x | . . . | x x . . x x | . x . | x x . . . . | . . . | . . .

JPF

by **vidarino** » Tue Apr 25, 2006 9:47 am

JPF: They have two empty columns in the center stack. That means that they can not have a unique solution, because the columns would be interchangable and still give a valid solution.

by **JPF** » Tue Apr 25, 2006 10:51 am

Thanks, Vidarino.

by ab » Tue Apr 25, 2006 1:13 pm

another minimal 20:

Code: Select all: ...|.6.|... ..6|1.3|5.. .4.|...|.2. ----------- .2.|...|.9. 9..|...|..4 .3.|...|.8. ----------- .9.|...|.1. ..5|6.7|3.. ...|.5.|... 10-0-1-0-0 8-2-1-0-0 6-1-0-0-0 4-1-2-0-0 1-6-0-0-0 1-4-2-0-0

by **gfroyle** » Tue Apr 25, 2006 1:28 pm

JPF wrote:
gfroyle wrote:Anyway, here is a list of all the 20-clue S-equivalence classes.. one per line.

Thanks for the list.
Actually, I was trying to supplement this list (at least for me) for every number of clues.
I don't undestand why it takes me years to do it.

My complete listing can be downloaded from

http://www.csse.uwa.edu.au/~gordon/sudokufsp-sequiv

if you would like to use it, or confirm it.

Plain text file, one line per S-class, all sizes except 0.

Gordon

by **tarek** » Tue Apr 25, 2006 1:37 pm

This may be silly........

But if you're using binary converted into decimal......
wouldn't be easier to use 32 as base as the maximum is 31 & therefore avoid the hyphens......
with 31=V

so the 81 clue Fully symmetric configuration would be VF731

tarek

by **JPF** » Tue Apr 25, 2006 3:38 pm

tarek wrote:...wouldn't be easier to use 32 as base as the maximum is 31 & therefore avoid the hyphens......
with 31=V

It could be a good idea.

But, I’d like to get the advices of gfroyle, ab and gsf who already used this nomenclature.

In any case, I would agree with ab to represent each class of S-equivalents by the lowest number (xyztu) ; (x<=y<=z<=t<=u), with or without hyphens.

JPF

by **gsf** » Tue Apr 25, 2006 4:21 pm

JPF wrote:
tarek wrote:...wouldn't be easier to use 32 as base as the maximum is 31 & therefore avoid the hyphens......
with 31=V

In any case, I would agree with ab to represent each class of S-equivalents by the lowest number (xyztu) ; (x<=y<=z<=t<=u), with or without hyphens.

at this point the hyphenated form jumps out as fully symmetric sudoku descriptor

also, I don't think (x<=y<=z<=t<=u) captures ab's suggestion
where you systematically compute the 6 equivalent representations and use one that sorts numerically least
so for the x's among the 6 the lowest x is selected, then the lowest y, etc.
so the comparison is between the representations, not within a representation
(the comparison can be done equivalently on the 31 bit rep instead of the hyphenated rep)

by **JPF** » Tue Apr 25, 2006 4:39 pm

of course !
You are right.

I wanted to say:
In any case, I would agree with ab to represent each class of S-equivalents by the lowest number (xyztu) <(x'y'z't'u') ; with hyphens like it is now, or without hyphens if these numbers are in base 32.

JPF

by ab » Tue Apr 25, 2006 5:17 pm

here's some more minimal 20s:

Code: Select all: ..7|.5.|3.. .6.|...|.5. 8..|...|..9 ----------- ...|8.5|... 9..|...|..2 ...|4.3|... ----------- 4..|...|..8 .2.|...|.4. ..5|.3.|7.. 16-5-0-2-0 16-4-1-2-0 9-0-4-2-0 8-1-4-2-0 5-8-0-2-0 4-8-1-2-0 ...|...|... .4.|...|.1. ..8|2.6|9.. ----------- ..6|.1.|7.. ...|4.5|... ..7|.3.|2.. ----------- ..2|7.9|6.. .3.|...|.5. ...|...|... 18-8-0-1-0 18-0-4-1-0 16-10-0-1-0 16-0-6-1-0 0-10-4-1-0 0-8-6-1-0 ...|.6.|... ...|714|... ..2|...|9.. ----------- .4.|...|.8. 37.|...|.41 .1.|...|.5. ----------- ..8|...|2.. ...|971|... ...|.4.|... 16-3-1-0-0 16-1-3-0-0 3-8-1-0-0 3-1-4-0-0 1-8-3-0-0 1-3-4-0-0

by **Ocean** » Tue Apr 25, 2006 7:18 pm

Good job with the minimal fullsymmetric 20s, ab. I know they are not the easiest to find.

Thanks to Gordon for the list of non-isometric symmetric patterns.

Since these configurations/patterns with empty boxes are impossible:

Code: Select all: 0X0 XXX 0X0 0X0 X0X 0X0

we therefore have:

Code: Select all: 20: 0-3-2-0-0 0-2-3-0-0 2-3-0-0-0 2-0-3-0-0 3-2-0-0-0 3-0-2-0-0 impossible 20: 0-3-1-2-0 0-1-3-2-0 3-1-0-2-0 3-0-1-2-0 1-3-0-2-0 1-0-3-2-0 impossible 20: 0-3-1-1-0 0-1-3-1-0 3-1-0-1-0 3-0-1-1-0 1-3-0-1-0 1-0-3-1-0 impossible 20: 0-2-2-2-0 2-2-0-2-0 2-0-2-2-0 impossible 20: 0-2-2-1-0 2-2-0-1-0 2-0-2-1-0 impossible 20: 0-2-1-3-0 0-1-2-3-0 2-1-0-3-0 2-0-1-3-0 1-2-0-3-0 1-0-2-3-0 impossible 20: 2-2-1-0-0 2-1-2-0-0 1-2-2-0-0 impossible 20: 2-1-1-2-0 1-2-1-2-0 1-1-2-2-0 impossible 20: 2-1-1-1-0 1-2-1-1-0 1-1-2-1-0 impossible 20: 3-1-1-0-0 1-3-1-0-0 1-1-3-0-0 impossible 20: 1-1-1-3-0 impossible

by **JPF** » Tue Apr 25, 2006 10:27 pm

gfroyle wrote:My complete listing can be downloaded from
http://www.csse.uwa.edu.au/~gordon/sudokufsp-sequiv
if you would like to use it, or confirm it.
Plain text file, one line per S-class, all sizes except 0.

Thanks Gordon again, you save me 1 week of bugs.

Now, we have the number N'(n) of S-different patterns with n clues :

Code: Select all: Number Number Number of clues of patterns of S-different (n) N(n) patterns N'(n) 0 1 1 1 1 1 4 8 4 5 8 4 8 34 10 9 34 10 12 104 24 13 104 24 16 253 52 17 253 52 20 512 98 21 512 98 24 888 165 25 888 165 28 1344 246 29 1344 246 32 1794 323 33 1794 323 36 2128 380 37 2128 380 40 2252 402 41 2252 402

N'(81-k) = N'(k) ; k=0,...,81

which gives a total of 6016 S-different patterns (32768 before)
and only 98 for the 20-clues instead of 512.

gfroyle wrote:Of course, some of these can immediately be seen to be impossible patterns for a valid puzzle...

For the 20 clues' :

ab and Ocean gave 21+11 = 32 impossible patterns.
I hope I'm not double-counting or missing some of them ?
Finally, it remains 98-32= 66 candidates.

For the minimal ones (before eliminating the obvious impossibles), it remains a maximum of : 2x(98+165+246+323+380)= 2424 S-different patterns, still assuming that 20 clues is the minimum and 37 is the maximum for a minimal FS puzzle.

JPF

by **JPF** » Wed Apr 26, 2006 12:00 am

Here is the list of FS patterns with 20 clues, so far :
14 S-different patterns.
all are abs. minimal except one.

If 66 is the right number of possible candidates, 52 are still missing.

Code: Select all: Ocean 0-6-1-0-0 0-5-2-0-0 10-1-0-0-0 9-2-0-0-0 6-0-1-0-0 5-0-2-0-0 . . . | . . . | . . . . . 1 | . 2 . | 3 . . . 4 . | 5 . 6 | . 7 . -------+-------+------- . . 4 | . . . | 1 . . . 7 . | . . . | . 8 . . . 2 | . . . | 6 . . -------+-------+------- . 8 . | 9 . 7 | . 5 . . . 3 | . 6 . | 2 . . . . . | . . . | . . . ab 24-0-1-2-0 20-1-0-2-0 8-8-1-2-0 4-1-4-2-0 1-12-0-2-0 1-4-4-2-0 3 8 . | . . . | . 7 1 9 . . | . . . | . . 4 . . . | . 2 . | . . . -------+-------+------- . . . | 8 . 9 | . . . . . 4 | . . . | 6 . . . . . | 1 . 2 | . . . -------+-------+------- . . . | . 5 . | . . . 8 . . | . . . | . . 7 7 3 . | . . . | . 9 8 ab 16-9-4-2-0 16-8-5-2-0 17-8-4-2-0 17-4-0-2-0 8-0-5-2-0 4-9-0-2-0 . 3 . | . . . | . 4 . 6 . . | . . . | . . 3 . . 7 | . 2 . | 9 . . -------+-------+------- . . . | 3 . 8 | . . . . . 9 | . . . | 7 . . . . . | 5 . 6 | . . . -------+-------+------- . . 2 | . 1 . | 4 . . 5 . . | . . . | . . 6 . 9 . | . . . | . 7 . ab 16-9-2-0-0 16-2-5-0-0 17-8-2-0-0 17-2-4-0-0 2-9-4-0-0 2-8-5-0-0 6 . . | . . . | . . 5 . . . | 4 . 3 | . . . . . 5 | . 7 . | 1 . . -------+-------+------- . 2 . | . . . | . 7 . . . 7 | . . . | 2 . . . 8 . | . . . | . 3 . -------+-------+------- . . 6 | . 2 . | 5 . . . . . | 7 . 8 | . . . 4 . . | . . . | . . 3 ab 8-1-2-0-0 9-0-2-0-0 4-2-1-0-0 5-2-0-0-0 2-5-0-0-0 2-4-1-0-0 . . . | 7 . 2 | . . . . . 2 | . 4 . | 6 . . . 6 . | . . . | . 5 . -------+-------+------- 4 . . | . . . | . . 9 . 1 . | . . . | . 3 . 3 . . | . . . | . . 7 -------+-------+------- . 8 . | . . . | . 9 . . . 4 | . 2 . | 1 . . . . . | 5 . 3 | . . . ab 0-6-0-1-0 0-4-2-1-0 8-2-0-1-0 10-0-0-1-0 4-0-2-1-0 6-0-0-1-0 . . . | . . . | . . . . . 2 | 5 . 8 | 1 . . . 7 . | . . . | . 9 . -------+-------+------- . 5 . | . 6 . | . 4 . . . . | 3 . 2 | . . . . 6 . | . 9 . | . 3 . -------+-------+------- . 9 . | . . . | . 7 . . . 8 | 2 . 1 | 3 . . . . . | . . . | . . . ab 16-8-2-1-0 16-2-4-1-0 8-0-2-1-0 4-2-0-1-0 2-8-4-1-0 2-4-0-1-0 . . . | 2 . 5 | . . . . . 7 | . . . | 4 . . . 9 . | . . . | . 3 . -------+-------+------- 2 . . | . 7 . | . . 1 . . . | 8 . 3 | . . . 1 . . | . 9 . | . . 5 -------+-------+------- . 4 . | . . . | . 8 . . . 8 | . . . | 5 . . . . . | 7 . 1 | . . . ab 18-9-0-0-0 18-0-5-0-0 17-10-0-0-0 17-0-6-0-0 0-10-5-0-0 0-9-6-0-0 Not M . . . | . . . | . . . . 3 . | 9 . 8 | . 1 . . . 2 | . 7 . | 8 . . -------+-------+------- . 1 . | . . . | . 3 . . . 5 | . . . | 7 . . . 9 . | . . . | . 6 . -------+-------+------- . . 7 | . 5 . | 2 . . . 6 . | 1 . 7 | . 9 . . . . | . . . | . . . ab 16-8-2-2-0 16-2-4-2-0 8-0-2-2-0 4-2-0-2-0 2-8-4-2-0 2-4-0-2-0 . . . | 4 . 5 | . . . . . 9 | . . . | 8 . . . 7 . | . . . | . 4 . -------+-------+------- 3 . . | 9 . 8 | . . 6 . . . | . . . | . . . 8 . . | 3 . 2 | . . 5 -------+-------+------- . 5 . | . . . | . 9 . . . 7 | . . . | 4 . . . . . | 5 . 1 | . . . ab 8-2-1-0-0 10-0-1-0-0 4-1-2-0-0 6-1-0-0-0 1-6-0-0-0 1-4-2-0-0 . . . | . 6 . | . . . . . 6 | 1 . 3 | 5 . . . 4 . | . . . | . 2 . -------+-------+------- . 2 . | . . . | . 9 . 9 . . | . . . | . . 4 . 3 . | . . . | . 8 . -------+-------+------- . 9 . | . . . | . 1 . . . 5 | 6 . 7 | 3 . . . . . | . 5 . | . . . ab 16-5-0-2-0 16-4-1-2-0 8-1-4-2-0 9-0-4-2-0 4-8-1-2-0 5-8-0-2-0 . . 7 | . 5 . | 3 . . . 6 . | . . . | . 5 . 8 . . | . . . | . . 9 -------+-------+------- . . . | 8 . 5 | . . . 9 . . | . . . | . . 2 . . . | 4 . 3 | . . . -------+-------+------- 4 . . | . . . | . . 8 . 2 . | . . . | . 4 . . . 5 | . 3 . | 7 . . ab 16-10-0-1-0 16-0-6-1-0 18-8-0-1-0 18-0-4-1-0 0-10-4-1-0 0-8-6-1-0 . . . | . . . | . . . . 4 . | . . . | . 1 . . . 8 | 2 . 6 | 9 . . -------+-------+------- . . 6 | . 1 . | 7 . . . . . | 4 . 5 | . . . . . 7 | . 3 . | 2 . . -------+-------+------- . . 2 | 7 . 9 | 6 . . . 3 . | . . . | . 5 . . . . | . . . | . . . ab 16-3-1-0-0 16-1-3-0-0 3-8-1-0-0 3-1-4-0-0 1-8-3-0-0 1-3-4-0-0 . . . | . 6 . | . . . . . . | 7 1 4 | . . . . . 2 | . . . | 9 . . -------+-------+------- . 4 . | . . . | . 8 . 3 7 . | . . . | . 4 1 . 1 . | . . . | . 5 . -------+-------+------- . . 8 | . . . | 2 . . . . . | 9 7 1 | . . . . . . | . 4 . | . . . ab 16-10-1-0-0 16-1-6-0-0 18-8-1-0-0 18-1-4-0-0 1-10-4-0-0 1-8-6-0-0 . . . | . 3 . | . . . . 9 . | . . . | . 5 . . . 1 | 7 . 2 | 3 . . -------+-------+------- . . 3 | . . . | 2 . . 6 . . | . . . | . . 9 . . 4 | . . . | 7 . . -------+-------+------- . . 7 | 8 . 4 | 1 . . . 2 . | . . . | . 3 . . . . | . 5 . | . . .

Impressive work from ab.

JPF

The New Sudoku Players' Forum

Fully symmetrical puzzles