The New Sudoku Players' Forum

[daj95376]

Is anyone finding that the hardest puzzles have anything in common that would either help in constructing them directly or generating them more efficiently or identifying them by inspection? Some templates seem to yeild harder puzzles -- but is that as far as it goes? Any hint there may be some rules of thumb, like "puzzles with 2 or 3 clues in each group are more likely to yeild an ultra hard" ... or something like that?

Besides hating diagonal puzzles, I also cringe when I encounter a puzzle where one value, e.g. 9, is missing from any of the clues for the puzzle. It often results in more complex analysis of the puzzle. Does anyone have examples for difficult missing-value puzzles?

[tso]

Since the difficulty of the puzzle remains unchanged after swaping a pair of rows or columns in the same chute, the rule of thumb becomes:

"Puzzles generated with no more than 3 givens per box in which no two givens are in the same row or column have a greater chance of being more difficult than others."

In puzzles like this, no two clues are in the same two groups. Maybe *that's* the rule of thumb:

"Puzzles in which no two clues are in two groups are more likely to be very difficult others."

Is it possible that this result might be dependent on how the puzzles are generated or selected? Starting from a full grid and subtracting clues, starting from an empty one and adding, some other method ... Which way do you do it, Ruud?

[Ruud]

Is it possible that this result might be dependent on how the puzzles are generated or selected? Starting from a full grid and subtracting clues, starting from an empty one and adding, some other method ... Which way do you do it, Ruud?

There are more than those 2 methods. I employ them all.

Starting from an empty grid and adding clues seems to produce puzzles with fewer clues and a narrower solving path. It is also a very slow method, so I hardly use it any more for batch generation.

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.

The last method was used to create the diagonals. For the last set, I modified the generator to minimize after a puzzle was found with the standard diagonal pattern.

I modified my DLX solver to count the total size of constraints covered upto the solution. I often see that puzzles that resist DLX also turn out to be difficult puzzles. I need to collect a little more data to find the exact correlation, but it looks very promising.

Ruud.

[RW]

Is anyone finding that the hardest puzzles have anything in common that would either help in constructing them directly or generating them more efficiently or identifying them by inspection?

I quickly looked through the puzzles with 5+ steps and gfroyles seems to be the only one with <22 clues. Most of the hardest seem to have 24 or 25 clues. Also was a few 27s around. I still find it hard to believe that a 27 can be harder than any possible 17, but that just adds to the mystery of sudoku. If someone has a scientific explanation to this, I'd be happy to hear it.

RW

[ravel]

Ruud,

your second list again has some puzzles for me
Lines 2,3 and 11 with 4 steps, 5 and 9 with 5 steps and 4 with 6 steps.

RW,

no explanation, but there is another mystery found by coloin: A minimal 33-clue, that is harder than an 18-clue, which has 10 common numbers [edit: and the same solution].

[Viggo]

Is anyone finding that the hardest puzzles have anything in common that would either help in constructing them directly or generating them more efficiently or identifying them by inspection? Some templates seem to yeild harder puzzles -- but is that as far as it goes? Any hint there may be some rules of thumb, like "puzzles with 2 or 3 clues in each group are more likely to yeild an ultra hard" ... or something like that?

From solving some sudokus I find, that the hard puzzles seems to have very few easy steps from the start. One way to get easy steps from the start is if a unit is almost filled, because then the remaining candidates are easier found. Another way is if almost all of one candidate value is pressent, because then the space for the remaining candidate places are limited, and therefore you have a good chance of placing the rest of them. Consequently it likely, that hard sudokus have a limited number of candidates in each unit. Furthermore the amount of a specific number should not be high. Of cause other factors make an influence, but this could be a way of thumb.

I have looked on the top 10 from Ravels list and counted manually:

The number of values in each unit (10x27 in all) is like this:

5 values or more: 0
4 values: 12
3 values: 171
2 values: 81
1 values: 5
0 values: 1

The number of each value is distributed like this:

444333211
443332222
443322222
433333222
433333222
433333221
433332222
433332222
433332221
433332221

So you don't find one value more than 4 times or less than 1 time.

Two of the puzzles have 25 values from start, six has 24, and two has 23.

This is a very small statistics. Possibly somebody can make a better one using a computer program. I think that the limits from such a statistic could also be a quick way to sort candidate puzzles.

If you look for 17-puzzles, then I guess that the difficulty is to get a unique puzzle. So possibly more candidates should be more "fixed" from the start in order to avoid multiple solutions. I have no better or scientific explanation on why they are not among the hardest.

/Viggo

[Ocean]

I quickly looked through the puzzles with 5+ steps and gfroyles seems to be the only one with <22 clues. Most of the hardest seem to have 24 or 25 clues. Also was a few 27s around. I still find it hard to believe that a 27 can be harder than any possible 17, but that just adds to the mystery of sudoku. If someone has a scientific explanation to this, I'd be happy to hear it.

Maybe part of the explanation could be that there are less 17s (and 18s) around ?

"Puzzles generated with no more than 3 givens per box in which no two givens are in the same row or column have a greater chance of being more difficult than others."

In puzzles like this, no two clues are in the same two groups. Maybe *that's* the rule of thumb:

"Puzzles in which no two clues are in two groups are more likely to be very difficult others."

I tried to find puzzles using your rules of thumb, and made it even stronger:
"Puzzles with no more than 2 givens per box, per row, per column, and no two clues are in the same two groups."

Here are some 18s. Wonder how they compare to the hard ones?

Code: Select all

 +-------+-------+-------+
 | . . . | . . 1 | . . 2 |
 | . 3 . | . . . | . 1 . |
 | . . 4 | . 5 . | . . . |
 +-------+-------+-------+
 | . . . | 2 . . | . 6 . |
 | . . 7 | . . . | 4 . . |
 | 5 . . | . . 8 | . . . |
 +-------+-------+-------+
 | . . . | . 4 . | 7 . . |
 | . 8 . | 6 . . | . . . |
 | 1 . . | . . . | . . 5 | 
 +-------+-------+-------+

Code: Select all

000001002030000010004050000000200060007000400500008000000040700080600000100000005
000001002030000010004050000000600030007000400500002000000040700060800000200000005
000001002030000010004050000000600070008000400500002000000040800060700000100000005
000001002030000040001050000000400060005000700200008000000090100060200000400000005
000001002030000040001050000000400060007000300500008000000070500060900000400000001
000001002030000040001050000000600030007000800200004000000020100060300000400000009
000001002030000040001050000000600030007000800200004000000070100060300000400000005
000001002030000040001050000000600070002000300800004000000020500070300000400000001
000001002030000040004050000000600030001000500700002000000030100080700000200000009
000001002030000040005020000000600070002000300100004000000070500080300000400000009
000001002030000040005030000000400030006000700100002000000080600070500000400000001
000001002030000040005030000000400060001000700200008000000050300080700000400000001
000001002030000040005040000000200060007000300100008000000070500060300000200000008
000001002030000040005060000000200030001000600700008000000030500090400000200000007
000001002030000040005060000000200030006000100100005000000030500070400000200000008
000001002030000040005060000000200030006000700100008000000030500070400000200000008
000001002030000040005060000000200030006000700100008000000030500090400000200000008
000001002030000040005060000000200030007000500600008000000050700020400000800000006
000001002030000040005060000000200050006000700100008000000050900020400000800000001
000001002030000040005060000000200070004000300600008000000010500020400000800000006


Edit: The pattern has even more symmetry than I thought. Here is the first one again (reworked). Double diagonal symmetry:

Code: Select all

 +-------+-------+-------+
 | 1 . . | . . . | . 2 . |
 | . . . | . . 2 | . . 3 |
 | . . 4 | . 5 . | . . . |
 +-------+-------+-------+
 | . . . | 3 . . | . 6 . |
 | . . 7 | . . . | 4 . . |
 | . 5 . | . . 8 | . . . |
 +-------+-------+-------+
 | . . . | . 4 . | 7 . . |
 | 8 . . | 6 . . | . . . |
 | . 2 . | . . . | . . 5 | 
 +-------+-------+-------+


[daj95376]

Ocean,

In your 20 puzzles, my solver found 45 Swordfish. I don't know about difficulty, but you could enter any contest for generating Swordfish!

[Mike Barker]

My solver was able to solve all 20 puzzles generally with nice loops, but some ALS and grouped nice loops were required. On the other hand, my solver could only solve 6 of Ravel's 4-steppers and nothing above that. I'd have to say these puzzles lack that magic ingredient that makes puzzles really tough.

[Ocean]

My solver was able to solve all 20 puzzles generally with nice loops, but some ALS and grouped nice loops were required. On the other hand, my solver could only solve 6 of Ravel's 4-steppers and nothing above that. I'd have to say these puzzles lack that magic ingredient that makes puzzles really tough.

OK, thanks! Blind shot that missed the target. Back to analysis.

[ravel]

Ocean,

though none of your nice puzzles needed 4 steps, i appriciate, that someone is trying others than the diagonal patterns. Only 2 of the 11 7+steps and 7 of the 21 6+steps puzzles here dont have this pattern. Maybe because it is best explored.

[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

[ravel]

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?

From the minimum clue thread we know, that with high probability less than 50000 solution grids have a 17-clue, that is 1 out of [edit:] 100000 (there are 5472730538 non equivalent grids). But as far i know, no special structure could be identified.
So i dont think, we really could find a structure for hard sudoku grids. We dont even have a definition, what a hard puzzle is.

[Viggo]

From the minimum clue thread we know, that with high probability less than 50000 solution grids have a 17-clue, that is 1 out of [edit:] 100000 (there are 5472730538 non equivalent grids). But as far i know, no special structure could be identified.
So i dont think, we really could find a structure for hard sudoku grids. We dont even have a definition, what a hard puzzle is.

Interesting! Then there IS some structure, which can be identified by a computerprogram finding minimal sudokus. However this structure currently is complex and and takes a lot of computer time. But if it was possible in an easier way to find these grids, then it would be very revarding - and more people could use them as a start. When so few grids can produce minimal sudokus, then it is likely to assume, that another small subset of grids can produce hard sudokus. If only a few sudokus are equal (common) in these two subsets, then it explanlain why so few minimal sudokus are hard sudokus.

We may not have complete agreement on what a hard puzzle is, but I think the variation is small. Ravels solvers stepcounter is one way. Other solvers identification of hard steps are another way. These computer programs can repeat there findings on more sudokus and they can be compared.

/Viggo

[claudiarabia]

Using simple sudoku for the first time, I produced these two

Code: Select all

. . . | 6 . 8 | . . .
. . 7 | . 4 . | 8 . .
. . 2 | . . . | 6 . .
---------------------
6 . . | 8 . 4 | . . 9
. 9 . | . 2 . | . 5 .
1 . . | 7 . 9 | . . 6
---------------------
. . 6 | . . . | 2 . .
. . 3 | . 9 . | 4 . .
. . . | 4 . 5 | . . .


loving hearts


which require a guess and are still one-solutional

Claudia