How adding another clue can make a puzzle harder?

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

How adding another clue can make a puzzle harder?

Postby JeJ » Fri Mar 11, 2011 7:54 pm

In the mathematics article in Sudopedia, it is mentioned that adding clues can make a puzzle more difficult and as an example the following puzzle is shown:
Code: Select all
8 . . | 2 . 5 | . . 1
. . . | 1 . 3 | . . .
. . 3 | . 7 . | 8 . .
------+-------+------
6 3 . | . . . | . 7 5
. . 8 | . . . | 2 . .
9 1 . | . . . | . 4 8
------+-------+------
. . 5 | . 9 . | 1 . .
. . . | 7 . 6 | . . .
3 . . | 5 . 2 | . . 9


The extra clue is "9" on r3c6, which according to the article and to Hodoku, makes the puzzle "harder". So is the game really harder? If so how a puzzle with more clues can be harder than one with less?
JeJ
 
Posts: 76
Joined: 06 January 2011

Re: How adding another clue can make a puzzle harder?

Postby PIsaacson » Fri Mar 11, 2011 9:24 pm

JeJ,

Without the given 9r3c6, the puzzle quickly forms the following PM grid using SSTS, which reveals a type 3 UR r3c46/r5c46 <49> with the locked set <36> in column 4. This results in r7c4 <> 3 and the hidden single 4r7c4 is a backdoor which "cracks" the puzzle, allowing a singles only solution from there on.

Code: Select all
 *-----------------------------------------------------------------------------*
 | 8       4679    679     | 2       46      5       | 347     369     1       |
 | 2457    245679  679     | 1       8       3       | 4567    2569    2467    |
 | 1       2456    3       | 49+6    7       49      | 8       256     246     |
 |-------------------------+-------------------------+-------------------------|
 | 6       3       4       | 8       2       1       | 9       7       5       |
 | 57      57      8       | 49+36   346     49      | 2       1       36      |
 | 9       1       2       | 36      5       7       | 36      4       8       |
 |-------------------------+-------------------------+-------------------------|
 | 247     2467    5       | 34      9       8       | 1       236     23467   |
 | 24      2489    19      | 7       134     6       | 45      258     234     |
 | 3       4678    167     | 5       14      2       | 467     68      9       |
 *-----------------------------------------------------------------------------*

Adding the 9r3c6 prevents the discovery of the UR and the subsequent backdoor, which forces a much more difficult solution path. Using Sudoku Explainer (lksudoku's serate f11), the former puzzle scores 4.5 while the latter (with the additional clue) scores 7.2, which is significantly harder. Perhaps there is some way of reconstructing the 4/9 DP and making the same deduction? I seem to recall some posting on just such a technique, but my formerly good memory has since gone to fallow ground, so I need to do some searching to ascertain whether or not I'm misrecollecting.

Cheers,
Paul
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Re: How adding another clue can make a puzzle harder?

Postby ronk » Fri Mar 11, 2011 9:48 pm

PIsaacson wrote:Perhaps there is some way of reconstructing the 4/9 DP and making the same deduction? I seem to recall some posting on just such a technique, but ...

A uniqueness pattern may only be "reconstructed" when none of the cells of the pattern contains a given.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: How adding another clue can make a puzzle harder?

Postby PIsaacson » Fri Mar 11, 2011 10:44 pm

Ron,

I was thinking more along the lines of a Reverse BUG or a similar deadly pattern type of thing rather than a true UR. I have some notes on a Reverse BUG that contained something similar to a type 3 UR in which the additional candidates in some of the postulated R-BUG cells formed a locked set which eliminated a candidate from an external cell that was a peer of all the contributing LS R-BUG cells. However, I couldn't make this particular grid conform, so I'm still looking for some kind of DP solution?

Cheers,
Paul
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Re: How adding another clue can make a puzzle harder?

Postby JeJ » Sat Mar 12, 2011 12:05 am

Thank you PIsaacson

So does this mean that instead of starting to make placements as I find them, I should use another approach and analize the puzzle "as a whole" first?
JeJ
 
Posts: 76
Joined: 06 January 2011

Re: How adding another clue can make a puzzle harder?

Postby PIsaacson » Sat Mar 12, 2011 4:42 am

JeJ,

If you're discussing a computer solver, then I would highly recommend initial analysis of numerous kinds: validity/uniqueness, minimalness, backdoors... The more a priori information you have, the easier it is to make an intelligent directed attack on the sudoku puzzle.

In computer solvers, you often see algorithms that follow a brute-force approach - trying all possible candidates in row/col/digit order without any thought of going for bi-value/local, then tri-value/local... A potentially optimal approach would be to attack candidates that expose backdoors sorted by their cardinality. But that resurrects the can-of-worms "optimal solution path" discussions/debates. Nevertheless, there's lots of room here for research and experimentation.

If you're asking this from a human solver's POV, then it's a whole different issue and one better left to those expert in manually solving sudoku puzzles.

Cheers,
Paul
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Re: How adding another clue can make a puzzle harder?

Postby JeJ » Sat Mar 12, 2011 4:26 pm

Thanks Paul

I usually use a computer helper to solve my puzzles.

Darn! they never tell you that, about analizing first before you start eliminating like crazy.
JeJ
 
Posts: 76
Joined: 06 January 2011

Re: How adding another clue can make a puzzle harder?

Postby kifotv » Sun May 22, 2011 11:04 am

I've read some stuff about "avoidable rectangles", but I'm not sure how applicable that is to this puzzle. Avoidables can be used when anywhere from 1-3 cells of the UR pattern are already solved (I think).
kifotv
 
Posts: 6
Joined: 27 April 2011

Re: How adding another clue can make a puzzle harder?

Postby RW » Sun May 22, 2011 2:26 pm

kifotv wrote:I've read some stuff about "avoidable rectangles", but I'm not sure how applicable that is to this puzzle. Avoidables can be used when anywhere from 1-3 cells of the UR pattern are already solved (I think).

Avoidables can be used if some cells are solved, but not if they are given clues. This is why adding a clue can make a puzzle harder. Solving a cell cannot make it harder.

RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006


Return to General