Making a puzzle harder by adding a number

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

Postby Carcul » Sun Apr 23, 2006 10:26 am

RW wrote:Make the very obvious BUG-lite reductions...


Maybe I am missing something, but why can we exclude "2" from the indicated cells?

Regards, Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby ravel » Sun Apr 23, 2006 12:23 pm

vidarino wrote:Hmm, another side-effect of this phenomenon is that you could theorhetically find a hard puzzle, remove a clue, and make it easier.:)

However, you'd have to somehow verify that it still has a unique solution after the removal. Otherwise the use of uniqueness techniques would be invalid.


This is exactly the point, why it can become harder. You know that a puzzle has to be unique, but normally no pre-information is given, which clues are redundant. But to verify that a clue is redundant is as hard as solving the (n-1)-clues puzzle without uniqueness methods.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby ravel » Sun Apr 23, 2006 12:54 pm

Carcul wrote:.. why can we exclude "2" from the indicated cells?

I have not studied BUG-lite to be able to point to a link with this deadly pattern there, but let me say it in my words:
if r56c9 <> 2, the cells r56c59 (read clockwise) will have the possibilities 48,38,38,48 (or 38,48,48,38, if r4c5=4) and always 2 solutions 4,8,3,8 and 8,3,8,4 (or 3,8,4,8 and 8,4,8,3 resp.). Note that all 6 cells are in 2 boxes.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby Smythe Dakota » Sun Apr 23, 2006 1:00 pm

vidarino wrote:Hmm, another side-effect of this phenomenon is that you could theoretically find a hard puzzle, remove a clue, and make it easier. ....

Wouldn't that make the original puzzle invalid, in that the clue set was redundant?

To those who defend uniqueness methods as a valid solving technique, don't you now have another, similar, technique in your arsenal? For example, you could say something like "r4c3 cannot be a 7, because then" (through some complicated logic or other) "the 2 given in r8c5 would be redundant".

Bill Smythe
Smythe Dakota
 
Posts: 536
Joined: 11 February 2006

re: deducing from Uniqueness-Of-Answer

Postby Pat » Sun Apr 23, 2006 1:31 pm

Smythe Dakota wrote:To those who defend uniqueness methods as a valid solving technique, don't you now have another, similar, technique in your arsenal? For example, you could say something like "r4c3 cannot be a 7, because then" (through some complicated logic or other) "the 2 given in r8c5 would be redundant".


no, not quite -
redundant clues are definitely allowed.

~ Pat
User avatar
Pat
 
Posts: 3462
Joined: 18 July 2005

re: deducing from Uniqueness-Of-Answer

Postby Pat » Sun Apr 23, 2006 1:41 pm

Ruud wrote:
Smythe Dakota wrote:A math purist would probably say that uniqueness techniques should not be considered valid, and that part of the task in solving any puzzle is to establish uniqueness.

Many websites and newspapers that publish Sudokus explicitly state that "every puzzle has a unique solution that can be found by logic".

A math purist would IMO stick to the problem definition and not try to prove something given as an axiom.


i and Smythe Dakota seem to be in the minority,
refusing to assume Uniqueness-Of-Answer
even when the puzzle is published with such a promise.


just imagine they had a misprint
and the puzzle as published does have 2 answers.

if you assume Uniqueness-Of-Answer,
you may reach what you think is the only answer,
where in fact the puzzle was invalid
(had 2 answers).


see PaulIQ164 (2005.Sep.6)

~ Pat
User avatar
Pat
 
Posts: 3462
Joined: 18 July 2005

Postby Ruud » Sun Apr 23, 2006 2:11 pm

Pat wrote:i and Smythe Dakota seem to be in the minority,
refusing to assume Uniqueness-Of-Answer
even when the puzzle is published with such a promise.

I'm not sure that is true. You're in the same corner as Angus Johnson, the writer of Simple Sudoku.

just imagine they had a misprint
and the puzzle as published does have 2 answers.

The chances of a published puzzle that you see in the newspaper today having a misprint that leads to 2 solutions is probably less than the chance that you will have a car accident today when you take a ride. Yet you have no fear of stepping into your car today. But you fear the sudoku.

It is your choice not to accept the assurance of a unique solution. However, you cannot deny me making a different choice.

The real question is: Do you think a contestant at the Sudoku World Championships should be disqualified for using a technique that assumes a unique solution?

Ruud.
Ruud
 
Posts: 664
Joined: 28 October 2005

re(2): Deducing from Uniqueness-Of-Answer

Postby Pat » Sun Apr 23, 2006 2:18 pm

Ruud wrote:The real question is: Do you think a contestant at the Sudoku World Championships should be disqualified for using a technique that assumes a unique solution?

well, at the Championships they seem to want the answer - no questions asked as to how you got there.


if they did ask about the deductions used,
they would have to state their rules in advance
- i wouldn't quarrel with them either way.

and i certainly wasn't trying to dictate to you or to anyone.

~ Pat
User avatar
Pat
 
Posts: 3462
Joined: 18 July 2005

Postby RW » Sun Apr 23, 2006 3:24 pm

carcul wrote:
RW wrote:Make the very obvious BUG-lite reductions...


Maybe I am missing something, but why can we exclude "2" from the indicated cells?


Aah, maybe nobody has mentioned this deadly pattern yet in the BUG-lite thread:

Code: Select all
.   abc   .  | .  abc  .
.   abc   .  | .  abc  .
.   abc   .  | .  abc  .


Would end up in one of 6 different BUG-lite patterns when you solved the rest of the puzzle:

Code: Select all
.  ab . | . ab .
.  bc . | . bc .
.  ac . | . ac .

.  ab . | . ab .
.  ac . | . ac .
.  bc . | . bc .

.  bc . | . bc .
.  ab . | . ab .
.  ac . | . ac .

.  ac . | . ac .
.  ab . | . ab .
.  bc . | . bc .

.  bc . | . bc .
.  ac . | . ac .
.  ab . | . ab .

.  ac . | . ac .
.  bc . | . bc .
.  ab . | . ab .


The puzzle I posted would end up in either of these two:

Code: Select all
.  34 . | . 34 .
.  48 . | . 48 .
.  38 . | . 38 .

.  34 . | . 34 .
.  38 . | . 38 .
.  48 . | . 48 .


I thought this was common knowledge. I think it's the second easiest deadly pattern to recognise after the normal uniqueness rectangle. Perhaps I should I post this one to the BUG-lite thread as well.

RW
Last edited by RW on Wed May 17, 2006 4:54 am, edited 1 time in total.
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Re: re: deducing from Uniqueness-Of-Answer

Postby vidarino » Sun Apr 23, 2006 5:39 pm

Pat,

If you chose to not use the information available to you (i.e. that the puzzle has a unique solution), that's fine with me.:) Sudoku is a game, meant to be fun, so if one prefers to verify uniqueness oneself (i.e. not using uniqueness methods), or relying on trial and error when the going gets tough, go right ahead. I do, however, regard uniqueness methods as perfectly legal.

Pat wrote:just imagine they had a misprint
and the puzzle as published does have 2 answers.


Hmm, well, if a puzzle is misprinted, all bets are off anyway. It could have zero, two or a hundred solutions. If you rely on uniqueness techniques, then maybe, just maybe it would appear to have a unique solution. But so what? Puzzle solved! ;-) Alternatively you'd get stuck at a point where you would have to guess to proceed, since there would be no logical next step. I, for one, would probably tap it into a solver to verify it at that point anyway, and if it was invalid, I'd either just make the required guess or scrap it.

Just my two Norwegian øre.:)

And RW; I'm fairly sure the 3x2 BUG-Lite was discussed in the BUG-Lite thread, if I recall correctly. I am 100% sure about having read about it *somewhere* before, at least, because I have added them to my solver. ;-)

Vidar
vidarino
 
Posts: 295
Joined: 02 January 2006

Postby RW » Sun Apr 23, 2006 6:16 pm

Pat wrote:just imagine they had a misprint
and the puzzle as published does have 2 answers.


Very interesting... So I cannot assume that the given numbers are correct as a basis for my reductions. Thus the only right way of doing it would be to remove all clues, they might be misprints, and start solving the empty grid. Thank you for clearing that up for me, I always wondered what those potentially wrong numbers were doing there anyway.:)

vidarino wrote:And RW; I'm fairly sure the 3x2 BUG-Lite was discussed in the BUG-Lite thread, if I recall correctly. I am 100% sure about having read about it *somewhere* before, at least, because I have added them to my solver.


Yes, it was so I didn't post it. I've added them to my "solver" ages ago even if I hadn't read anything about any techniques yet at that time.:D

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

Postby Smythe Dakota » Sun Apr 23, 2006 9:17 pm

Pat wrote:.... if you assume Uniqueness-Of-Answer, you may reach what you think is the only answer, where in fact the puzzle was invalid (had 2 answers). ....

Or, worse yet, you may conclude that it has NO answer, when in fact it has 2.

Of course, a player in a tournament would want to use every method he can think of, to come up with the answer in the shortest possible time. And a player working at home can do whatever floats his boat.

Certainly, though, a solver PROGRAM should never assume uniqueness, since arbitrary grids can be plugged into such programs. The program should not only come up with a solution, but make sure that solution is unique (and say so if it isn't). Otherwise, the program just isn't doing the whole job.

Similarly, a program which GENERATES puzzles should make sure the clue set is not redundant.

Bill Smythe
Smythe Dakota
 
Posts: 536
Joined: 11 February 2006

Postby re'born » Mon Apr 24, 2006 2:40 am

Smythe Dakota wrote:Certainly, though, a solver PROGRAM should never assume uniqueness, since arbitrary grids can be plugged into such programs. The program should not only come up with a solution, but make sure that solution is unique (and say so if it isn't). Otherwise, the program just isn't doing the whole job.

Bill Smythe


Bill,

On the back end, of course you are dead right. But after verifying that the puzzle has a unique solution, the best solver programs also help human solvers find a non-brute force solution. From this point on, why not have the program use the uniqueness assumption, especially when certain puzzles whose only known solutions (without uniqueness arguments) use rather difficult forcing chains?

The onus should be on the designer to provide a "valid" sudoku, whatever we decide that to mean. It is our job to solve them. As a mathematician, I appreciate elegant solutions and I find no technique in Sudoku more elegant than uniqueness reductions.
re'born
 
Posts: 551
Joined: 31 May 2007

Postby JPF » Mon Apr 24, 2006 7:36 pm

and what about this puzzle…

Code: Select all
 6 . . | 3 1 9 | . . x
 . 1 . | 2 . 4 | . 5 .
 . . . | . . . | . . .
-------+-------+-------
 1 8 . | . . . | . 6 9
 7 . . | . 2 . | . . 1
 2 4 . | . . . | . 7 5
-------+-------+-------
 . . . | . . . | . . .
 . 6 . | 1 . 8 | . 3 .
 9 . . | 7 5 3 | . . 6


...with only one solution...


JPF

PS : if you remove the x, you will get 42 solutions !

Thanks, Tarek.
JPF
2017 Supporter
 
Posts: 3753
Joined: 06 December 2005
Location: Paris, France

Postby ravel » Mon Apr 24, 2006 8:05 pm

Hm, is this a sudoku variant ?
I get one unique solution, 2 multiple and the rest 0 solutions for different numbers for x.
ravel
 
Posts: 998
Joined: 21 February 2006

PreviousNext

Return to General