The New Sudoku Players' Forum

[Havard]

The problem with keith's "question for everyone" is that the number 5472730538 was computed mathematically, not by listing all the possibilities. It would be interesting to have a nice list of all of them, and it may just about be feasible to construct it.

Sorry if my maths are completly out here, but would not such a list take over 400 GB? (I got to almost 413) The question then becomes where you would have such a list?

Havard

[keith]

I'll have to go and look at the original work. I have this further issue on uniqueness.

Is this a count of only unique solution grids? In that we cannot scramble part of one grid to get another? Then, what do we do with the situation of: Yes, the solution grid itself is not unique, but the initial values are such that a particular puzzle has only one solution.

I think I agree that if we have a mathematical proof that counts the soultions, it should be possible to find a way to generate the grids.

Keith

[ronk]

no duplicate (up to isomorphism) solution grids in the 50K
(which implies no duplicate puzzles)

Even if I knew what isomorphism meant, I wouldn't be sure if "up to" meant "including" or "excluding", so I have a simple question ...

If a minimal-clue puzzle and that same puzzle with one or more redundant clues were in Ruud's set of 50K ... would your canonicalization , etc. process consider the two identical?

[ravel]

If a minimal-clue puzzle and that same puzzle with one or more redundant clues were in Ruud's set of 50K ... would your canonicalization , etc. process consider the two identical?

Puzzles with different numbers of clues are never isomorphic (or equivalent).

But Ruud (oot: nice uniqueness nightmare today ) said, that the puzzles are either minimal or symmetrically minimal and no 2 puzzles have the same clues in the first band. I suppose that not both a minimal and the same plus 1 clue are added to the list.

btw, gsf, are there any multiple (isomorphic) solution grids at all ?

[RW]

[edit: removed a stupid question]

To summarize my dilemma that started this thread, I got a list from Havard on the puzzles with 12-cell BUG-lites: 44, 47, 55, 73, 75, 83, 86, 97, 101, 150, 163, 206, 226, 1243, 1343. Only the two last ones were totally different puzzles, 22 clues and didn't seem to be very closely related to each other either. They might share the same canonical grid, but if they do they have several clues placed differently. If someone who isn't doing this manually want to test them, go ahead.

The first 13 are almost identical, 12 of them are the same 17 minimal with one reduntant clue and #101 is the most interesting. Here's a scrambled version to compare with #163:

Code: Select all

#101           #163
 
 *-----------*   *-----------*
 |4..|...|26.|   |4..|...|26.|
 |.3.|.7.|...|   |.3.|.7.|...|
 |...|...|...|   |...|...|...|
 |---+---+---|   |---+---+---|
 |...|.8.|.53|   |...|.8.|.53|
 |6.1|...|...|   |6.1|...|8..|
 |...|...|.7.|   |...|...|..7|
 |---+---+---|   |---+---+---|
 |...|654|1..|   |...|6.4|1..|
 |.5.|...|.8.|   |.5.|...|.8.|
 |...|2..|...|   |...|2..|...|
 *-----------*   *-----------*


Not only has the reduntant clue moved (163: r5c7, 101: r7c5) but the 7 in box 6 has moved 1 step to the left, which makes 101 a minimal 18. The puzzles thus have different solution grids, but the 12-cell BUG-lite appears in the same cells with the same digits, allowing the same reduction. I would still consider this a different puzzle, as it is otherwise solved differently than the other 12.

So the top1465 has 4 different (or 3 if 1243 and 1343 are the same) puzzles with 12 cell BUG-lites+1, just in case anybody is interested.

RW

[gsf]

this is long -- I bundled top50000 and top1465 replies into one post

Even if I knew what isomorphism meant, I wouldn't be sure if "up to" meant "including" or "excluding", so I have a simple question ...

play meets math again
wikipedia "up to isomorphism"
its a precise phrase used to quantify "same" and "different"

isomorphism is a mathematical concept that is immune to reordering and relabeling
for sudoku this means that the cells labels, symmetries, and row/col/box
permutations are taken into account

one may have a measure that makes two puzzles seem identical
(same # UR's, xwings, etc.), but they still may be different puzzles

conversely, a measure sensitive to cell labelling and/or row/col/box
permutations may make two identical puzzles seem different

no duplicate (up to isomorphism) solution grids in the 50K

means that I canonicalized the solution grids (in ruud's list) and there were no dups
which means that all of the puzzles have different solutions
which means there is no need to check the original puzzles for equivalence
i.e., canonical solutions different => canonical puzzles (with givens) different

there are other ways to compute/detect equivalence/difference
but canonicalization allows efficient comparisons on large numbers of elements

If a minimal-clue puzzle and that same puzzle with one or more redundant clues were in Ruud's set of 50K ... would your canonicalization , etc. process consider the two identical?

assuming valid sudoku (one solution), the two solution grids would be identical,
but the puzzles would be different (different # clues => different puzzles)

the top1465 was constructed to foil backtracking solvers using singles
that it illustrates various techniques is more by accident than design
although the premise has weathered pretty well in the face of techniques
formed since the list was compiled

here is the top1465 grouped by identical solution grid (up to isomorphism)
"==" within a group denotes identical puzzles (up to isomorphism)
puzzles with no isomorphic match not listed
(note that ruud's 50K list has no groupings since all solution grids are different)

000000940000090005300005070080400100463000000000007080800700000700000028050260000 #204
000070940070090005300005070087400100463080000000007080800700000700000028050268000 #224

080070000000004600010000000000020071605300000400000000300006000000700080000000500 #1348
034200050000087000010000000002400030050000200600000000000300001200000700800000000 #193

000100500000026000403000000000070643065000000000000080300800000000400200010000000 #607
000020403000100700085000000300700000000400010060000000000018000403000000000600050 #471

000010780500009000000000040020000000000600003074080000000003002080040010600500000 #300
020000000000600003074080000000003002080040010600500000000010780500009000000000040 #307==300

003400000000700030700001506200008007000940000000000900600000250805002001000600008 #646
003400000000700030700001506200008007000940000000000900600000250805302001000600008 #597

520006000000000701300000000000400800600000050000000000041800000000030020008700000 #243
108300000000007200300600000642050000000000061070000000050000400000800030000000000 #208
000100500400000060000000000602040000500000803700000000031500000000007020050800000 #222
017500600000400003060000500804000020000051000300000000000060700200800000000000000 #253
020050608000700400000103000060040000300000050000000010700305000000000200000080000 #234

012000600000807000000300000730000400000020009000000500400530000800000030000000010 #761
000032700010000000000050000100000029407800000060000000500000430200900000000100000 #1059
240000600000090008000000700419000500000302000000400000300000040600700000000000010 #267

071008000500000020000000000000006801400030000000000700000450030016000000000200000 #151
080051000000600020000000000030000805507400000000000100406000070000035000200000000 #170
064000900100200000000000000000049300700000050000056000000500017043000000000000002 #166
500000300000100020000406000000000508060200000000000900010000049900030000800090000 #221
560000400007200000000000000000300078610000000000000002000046100100050000008000030 #124
008017000000500030000000000540000020630000000000076000006000807200400000000000100 #144
460000029000030500000000000105040000000000072300000000070602000004000100000900000 #127

000450009000000003009000001060008700008002060904600000000830000600001000001000540 #874
000450009000000003009000001060008700008002060904605000000830000600001000001000540 #839

020400009400180000000062050000006300300940500000008010000000000802004000964000007 #258
020400009400180000000360050000006300300940500000008010000000040802000000960000007 #271
020400009400189000000062050000006300300940500000008010000000000802004000964000007 #228

003600000040000080900000700860400000000000105020000000500017000100090000000000020 #57
001000080000200500000600000000041030620000700000000009270800000000030004500000000 #116

000603700051000000000002000000010084600700000000000050140580000300000200000000000 #74
700000480000601000000000020000300605200080000000000000053000001060100000000040700 #45

019000050400200000000000000000091000000050060700000300000300407061000000000000200 #192
019060000200000700000000000300401000000000091000050060000203400051000000000700000 #184
000070043800000500000000000200501000000000064000800000034000600000200100070060000 #102

480300000000000071020000000705000060000200800000000000001076000300000400000050000 #55
170320000000000051000080000506001000000700300400000000000504060080000200000000000 #155
000030070020000800010000000300060200200100500704000000600000040000205000000800000 #206
507000030000061000108000000620040000000700080000000000010000604300500000000000200 #44
400000260030070000000000000000080053601000800000000007000604100050000080000200000 #163
000028070401000000000005000000100406020070000000000300600340000080200050000000000 #214
060070000000800020010000000000000605400300000000000700200060040803100000000050100 #75
001407000500000600000800000408600070000020300000000000630050000000000041020000000 #226
420000036000030800000000000708010000000000054003000000050406000100000700000200000 #73
000603700051000000000002000000010054600700000000000080140580000300000200000000000 #86
850000070000041000300000000001000406070500000000000200742060000000800030000000000 #64
700630000000000081000020000685001000000700600040000000000804050200000300000000000 #119
608100000000007200000000000003050061500004000000000080470000500000630000020000000 #150
000903050200000700000000000059001000000400600043000000400670000000000091000020000 #47
700000480000601000000000020000300605200080000000000000063000001050100000000040700 #83
300100060001047000000050000680300000000000401020000000405000700000200080000000000 #97

360100050000040290000007000610000000000009400800000000002050000000800006000000003 #195
001000080000200500000600000000014030620000700000000009270800000000030004500000000 #176

400000805030000000000700000020000060000080400000010000000603070500200000104000000 #230
100530070048000000000200000000068100300000002000001000010000400500700000000000600 #290
020000160000070500000010000000608040300200000105000000500000703000400000080000000 #326

here is the same list, but the canonical puzzles are listed to illuminate the differences within each group
this also gives a clue to how this post was compiled (sort by canonical solution and canonical puzzle, then uniq)

..3....89.5.78......9.3....271.......9..1.4.......3.9.......61...2..5.3....6....5 #204
..3....89.5.789.....9.3....2719.....39..1.4.......3.9....3..61...2..5.3..3.6....5 #224

1...5............2.8......4..7...95........1..6.2.8.....8..4...5......7.....9.... #1348
1...5..8.........2........4..7...95.8......1..6.2.8.....8..4...5......7.....9.... #193

..34.......6.....2.......5.......89.....6.....7.932.....58...........2.394....... #607
..34.......6.....2.......5.......89...4.6.....7..32.....58...........2.394....... #471

.....678.......1....9.3....2....86....19.........4...367...2...8...........5....4 #300
.....678.......1....9.3....2....86....19.........4...367...2...8...........5....4 #307==300

..34........7...3.7....15.62....8..7...94..........9..6.....25.8.5..2..1...6....8 #646
..34........7...3.7....15.62....8..7...94..........9..6.....25.8.53.2..1...6....8 #597

.........4....9....8......6.....34...1..7.........429.3.2..............7...6...18 #243
.........4....9....8......6.....34...1..7.........429.3.2..............7...6..318 #208
.........4....9....8......6.....34...1..7.........429.3.2.....4........7...6...18 #222
.........4....9....8......6.....34...1..7.....3...429.3.2..............7...6...18 #253
.........4....9....8......6.....34...1..7...3.....429.3.2..............7...6...18 #234

..345............7..9.....1....91...8.4.....2.6..........8..59..7.9...........3.. #761
..345............7..9.....1..7.91...8.4.....2.6..........8..59..7.............3.. #1059
..345...9........7..9.....1....91...8.4.....2.6..........8..59..7.............3.. #267

..3....8.45...9...............73..1....8.....56.............4.......69.5..7.1.... #151
..3....8.45...9...............73..1....8.....56.............4.......69.5..751.... #170
..3....8.45...9...............73..1....8.....56.............4.1.....69.5..7.1.... #166
..3....8.45...9...............73..1....8.....56.........5...4.......69.5..7.1.... #221
..3....8.45...9...............73..1....8.....56.......6.....4.......69.5..7.1.... #124
..3....8.45...9...............73..1....86....56.............4.......69.5..7.1.... #144
..3....8.45.1.9...............73..1....8.....56.............4.......69.5..7.1.... #127

...45...9........3..9.....1.6...87....8..2.6.9.46........83....6....1.....1...54. #874
...45...9........3..9.....1.6...87....8..2.6.9.46.5......83....6....1.....1...54. #839

.2.4....94..18........62.5......63..3..94.5.......8.1..........8.2..4...964.....7 #258
.2.4....94..18.......36..5......63..3..94.5.......8.1........4.8.2......96......7 #271
.2.4....94..189.......62.5......63..3..94.5.......8.1..........8.2..4...964.....7 #228

1...5......6.....7.8....4...3.9.4...........2.9.8.......2............93..75.6.... #57
1...5......6.....7.8....4...3.9.4...........2.9.8.......2.........7..93...5.6.... #116

1...5.........932.......4.....81...5...6......94...............8.......69.2.43... #74
1...5.........932...9...4.....81...5...6......94...............8.......6..2.43... #45

.....76..4...8.........65..2......38........4..5..1....6...........3...2.71...... #192
.....76..4...8.........65..2......386.......4..5..1....6...........3...2.71...... #184
.....76..45..8.........65..2......38........4..5..1....6...........3...2.71...... #102

.2.4...........7....9...15..17..5...............8....6....91...6........84......2 #55
.2.4...........7....9...15..17..5...............8....6....91...6........84....9.2 #155
.2.4...........7....9...15..17..5...............8....6....91...6........841.....2 #206
.2.4...........7....9...15..17..5...............8....6....91...69.......84......2 #44
.2.4...........7....9...15..17..5...............8....6..2.91...6........84......2 #163
.2.4...........7....9...15..17..5..............48....6....91...6........84......2 #214
.2.4...........7....9...15..17..5............9..8....6....91...6........84......2 #75
.2.4...........7....9...15..17..54..............8....6....91...6........84......2 #226
.2.4...........7....9...15..17.65...............8....6....91...6........84......2 #73
.2.4...........7....9...15..179.5...............8....6....91...6........84......2 #86
.2.4...........7....9...15.217..5...............8....6....91...6........84......2 #64
.2.4...........7....9...154.17..5...............8....6....91...6........84......2 #119
.2.4...........7....9.2.15..17..5...............8....6....91...6........84......2 #150
.2.4...........72...9...15..17..5...............8....6....91...6........84......2 #47
.2.4..........97....9...15..17..5...............8....6....91...6........84......2 #83
.2.4....9......7....9...15..17..5...............8....6....91...6........84......2 #97

......6.9.5.1.....78..............5.6...49...9....3...3.......4..28......1.....7. #195
.....76.9.5.1......8..............5.6...49...9....3...3.......4..28......1.....7. #176

...4.7........82....9...51..4......6..5.2............7......9..86...4.......1.... #230
...4.7........82....9...51..4......6..5.2.4..........7......9..86...4.......1.... #290
...4.7........82....9...51..4......6.75.2............7......9..86...4.......1.... #326

[gsf]

is there any way to change the font size in a [ code ] block?
[ size=9 ] [ code ] etc. has no effect

[ravel]

is there any way to change the font size in a [ code ] block?

AFAIK unfortunately no, you also cant use any other colors

Thx for explaining "up to isomorphism", a new phrase for me, which also answered my question, if there are isomorphic solution grids.

[kjellfp]

The problem with keith's "question for everyone" is that the number 5472730538 was computed mathematically, not by listing all the possibilities. It would be interesting to have a nice list of all of them, and it may just about be feasible to construct it.

The code for doing this exists. When I confirmed the number 5472730538, my program simply visited every equivalence class exactly once.

[Viggo]

I also have a collection of 3418 non-minimized puzzles with this pattern:

Code: Select all

X . .|X . .|X . .
. X .|. X .|. X .
. . X|. . X|. . X
-----+-----+-----
X . .|X . .|X . .
. X .|. X .|. X .
. . X|. . X|. . X
-----+-----+-----
X . .|X . .|X . .
. X .|. X .|. X .
. . X|. . X|. . X

I think that it is what ravel calls a "diagonal pattern". This may be converted by row, column, 3-block manipulations, and some of the boxes may show up like these five other examples:

Code: Select all

X . .|. X .|. X .|. . X|. . X|
. . X|X . .|. . X|X . .|. X .|
. X .|. . X|X . .|. X .|X . .|

It is then essentially the same puzzle, but it appears differently. Due to the fact, that so many of the puzzles has the "diagonal pattern" indicate, that some sorting of the clue-pattern already has been applied.

-----
And then to the matter of finding hard puzzle and 17-clue puzzles...

We have had a focus on the structure of the clues, but perhaps the structure of the solution is another part of the problem.

Starting from a solution and removing clues is extremely fast. Somehow it is the best method to find minimal puzzles with a higher number of clues. I've already found puzzles that are symmetrical minimal with 44 clues.

A third method starts with an empty grid and a solution. It plugs a random set of clues in the grid and checks for a unique solution. When not unique, a new random set is taken. In case of a fixed pattern, a new solution is used.

If you apply Ruuds way of creating puzzles to some randomly selected solutions (of all possible solutions), then I suppose, that some procentage will be 17-clue puzzles, and some other procentage will be hard sudokus above some level.

I have two questions:

1) Can some structure of the solution influence the possibility of finding 17-clue puzzles?
2) Can some structure of the solution influence the possibility of finding hard puzzles?

You could also ask: Does the solution matter at all in order to find 17-clue og hard puzzles? Maybe these questions already have been answered before. I tend to believe, that a solution has no special structure, but I'am not quite sure.

It can checked. You use solutions from 17-clue pussles, and start with these solutions when finding hard sudokus - or the other way around. If you get another procentage than in the random case, then some structure in the solution do make a difference.

You have to be sure, that the process of selecting the clues is random and not depending of the position in the puzzle at all in order to get a valid result.

/Viggo

[Viggo]

Sorry about this - I have placed the above post on the wrong topic.

/Viggo

[ronk]

Sorry about this - I have placed the above post on the wrong topic.

When it was the last post on this thread ... you could have deleted it.

[Viggo]

Ronk, thank you for the information. I have just now read the FAQ on how and when you can delete a message.

/Viggo

[algernon]

It is possible that a lot of them can be solved with XYZ-wing, APE, ALS, subset counting or Nice Loops.

My very simple solver, which supports only X/XY/XYZ-wings and simple
coloring (no other fishes) solved 162 of the top50000; all of these solutions used XYZ-wing.
Not so much, suspect I must implement APE now, to score some more...