The New Sudoku Players' Forum

[richardm]

Code: Select all


Damn it you're right. I pasted the partially worked puzzle twice.
Here's the staring position:

... 382 ...
... 17. ...
8.. ... 412

5.. .3. 9..
.26 ... 35.
..4 .2. ..7

462 ... ..1
... .67 ...
... 941 ...

I've been thinging about the UR method. The logic that says in:

.   59  59
.   .   .
.   .   .

.   .   .
.   .   .
.   .   .

.  59  593
.  .   .
.  .   .


59 can be eliminated from r7c3. This logic is only correct if you can prove that in having 59 instead of 3 you don't get a solution. If you don't prove this then you are arbitrarily selecting one of 3 possible solutions. 

Another way of putting it: you have to have faith in the compiler and assume that when the puzzle was constructed the uniqueness of the solution was tested. Merely selecting the technique doesn't guarantee uniqueness.


Your xy-wing move seems to be what I used without understading that it was a generalized move. However even that troubles me since the proof of the move requires proof by contradiction, which istelf requires a hypothesis (or assumption) to be tested.

To me it seems to be a very fine line as to whether one type of assumption-based move is allowed and another is not.

Is there any guidance on this from Pappocom?

Richard


[/code]

[re'born]

Your xy-wing move seems to be what I used without understading that it was a generalized move. However even that troubles me since the proof of the move requires proof by contradiction, which istelf requires a hypothesis (or assumption) to be tested.

To me it seems to be a very fine line as to whether one type of assumption-based move is allowed and another is not.

Richard,

I don't think that the proof of the move requires 'proof by contradiction'. For instance, you have 3 cells with candidates [xy], [yz], and [xz], respectively, where the first cell 'sees' the second and third cells. If the first cell is x, then the third cell is z. If the first cell is y, then the second cell is z. Since the first cell is either x or y, the second or third cell must be z and hence any cell seeing both of these cells cannot be z. This is a direct proof.

As far as I know, every technique used by Sudoku players can be reformulated as proof by contradiction, including naked and hidden singles. So the type of proof used to demonstrate a move's validity is probably not the best judge of its 'allowability', whatever that means. Without taking sides on the T&E debate, I think it is reasonable to say that there is a big difference between recognizing a pattern (such as an XY-wing) and making an arbitrary placement or removal and determining whether it leads to a contradiction or a solution.

Another way of putting it: you have to have faith in the compiler and assume that when the puzzle was constructed the uniqueness of the solution was tested. Merely selecting the technique doesn't guarantee uniqueness.

This is normally true (there are some interesting exceptions discovered by RW though) and thankfully the designers of published puzzles (a few sources notwithstanding) have an excellent track record of providing Sudoku puzzles that follow the rule that they should have a unique solution. Moreover, the more difficult puzzles (most of which are found on this forum) are solved by many of us on the computer and this allows us to determine beforehand if the puzzle is valid. In the end, I don't feel bad using a technique that is fun to look for, easy to use and often devastating when applied, where the only risk is that I don't determine whether the puzzle is valid, something that should have been determined by the designer.

[richardm]

I think we are in agreement here. What you've demonstrated for me is that one does need to resort to testing an hypothesis for certain advanced problems. In doing that, one may show an impossible situation results or equivalently that a certain value cannot be selected. The two arguments are equivalent. It all depends on where you start your test. I must conclude that guessing, in its broadest interpretation, cannot be avoided in some of the more difficult problems. My personal challenge is to delay the use of such a technique to the last possible moment.

There are indications when such a technique may be needed (which I think is what the xy-wing is an instance of): for example the presence of many 2-values cells in a 3x3 block where at lest one number has two possible positions not in the same row and not in the same column.

For the record, I solved the AA problem by noting that:

Code: Select all

*-----------------------------------------------------------*
 | 6     4     1     | 3     8     2     | 5     7     9     |
 | 2     59    59    | 1     7     4     | 6     38    38    |
 | 8     37    37    | 56    9     56    | 4     1     2     |
 |-------------------+-------------------+-------------------|
 | 5     1     78    | 47    3     68    | 9     2     468   |
 |79     2     6     | 47    1     89    | 3     5     48    |
 | 39    *38    4    | 56    2    *5689  | 1     -68   7     |
 |-------------------+-------------------+-------------------|
 | 4     6     2     | 8     5     3     | 7     9     1     |
 | 1     359   359   | 2     6     7     | 8     4     35    |
 | 37    3578  3578  | 9     4     1     | 2     36    356   |
 *-----------------------------------------------------------*

r4c8 cannot be 8 becuase 8 is in either r4c2 or r4c6 since 3 in r4c2=>r6c3=8=>r5c1=7=>r56c6 cannot be 8


Interesting discussion. My thanks to those who responded to my original posting.

Richard

[udosuk]

For the record, I solved the AA problem by noting that:
...
r4c8 cannot be 8 becuase 8 is in either r4c2 or r4c6 since 3 in r4c2=>r6c3=8=>r5c1=7=>r56c6 cannot be 8

Firstly I notice that you use a different indexing system on rows...
Most people index them 1..9 from top to bottom, but you do it from bottom to top!
IMHO the politically correct way is to do what everybody does, namely r1=top row, r9=bottom row...
(No matter how much you love the game of chess you cannot apply its notation on every other game! )

Your move, with some alteration, could be expressed as a forcing chain using the nice loop notation:

Code: Select all

 *-----------------------------------------------------------*
 | 6     4     1     | 3     8     2     | 5     7     9     |
 | 2     59    59    | 1     7     4     | 6     38    38    |
 | 8     37    37    | 56    9     56    | 4     1     2     |
 |-------------------+-------------------+-------------------|
 | 5     1    *78    | 47    3     68    | 9     2     468   |
 |*79    2     6     | 47    1    *89    | 3     5    *48    |
 | 39   *38    4     | 56    2     5689  | 1    -68    7     |
 |-------------------+-------------------+-------------------|
 | 4     6     2     | 8     5     3     | 7     9     1     |
 | 1     359   359   | 2     6     7     | 8     4     35    |
 | 37    3578  3578  | 9     4     1     | 2     36    356   |
 *-----------------------------------------------------------*

[r6c8]-8-[r6c2]=8=[r4c3]=7=[r5c1]=9=[r5c6]=8=[r5c9]-8-[r6c8]
i.e.
r6c8=8 => r6c2<>8(=3) => r4c3=8(<>7) => r5c1=7(<>9) => r5c6=9(<>8) => r5c9=8
=> Contradiction: two 8s in b6 (r6c8 & r5c9)!

And although rep'nA has more or less answered your question... Here is what I prepared to reply to you 2 days ago but didn't get to do so:

Your xy-wing move seems to be what I used without understading that it was a generalized move. However even that troubles me since the proof of the move requires proof by contradiction, which istelf requires a hypothesis (or assumption) to be tested.

Perhaps I presented it in a way that lead you to think it's proof by contradiction... How about this way?

Code: Select all

 *-----------------------------------------------------------*
 | 6     4     1     | 3     8     2     | 5     7     9     |
 | 2     59    59    | 1     7     4     | 6     38    38    |
 | 8     37    37    | 56    9     56    | 4     1     2     |
 |-------------------+-------------------+-------------------|
 | 5     1    *78    | 47    3    -68    | 9     2     468   |
 |*79    2     6     | 47    1    *89    | 3     5     48    |
 | 39    38    4     | 56    2     5689  | 1     68    7     |
 |-------------------+-------------------+-------------------|
 | 4     6     2     | 8     5     3     | 7     9     1     |
 | 1     359   359   | 2     6     7     | 8     4     35    |
 | 37    3578  3578  | 9     4     1     | 2     36    356   |
 *-----------------------------------------------------------*

r5c1={79} "sees" both r4c3={78} and r5c6={89}
Whatever value r5c1 turns out to be, one of r4c3 and r5c6 must become an 8
Therefore all other cells which "see" both r4c3 and r5c6 must not be 8
r4c6 "sees" both r4c3 and r5c6, therefore it must not be 8, and must be 6

Sounds better?

And the way to "spot" these XY-wings is:

1. Scan the grid for bivalue cells
2. For each bivalue cell {XY}, look for 2 other bivalue cells {XZ} and {YZ} which both "sees" the {XY} cell
3. Now look at all other cells which "see" both the {XZ} and {YZ} cells
4. Eliminate Z from those cells (possibly a maximum of 5)

Because of the systematic way to spot this move, not many people would call it "assumption-based"...

Let's look at another example... Consider this very simple turbot fish:

Code: Select all

 .  .  . | .  #  . | .  .  .
 3  4  5 |*12 6  7 | 8 *12 9
 .  .  . | .  #  . | .  .  .
---------+---------+---------
 .  .  . | #  .  . | .  .  .
 .  .  . | #  .  . | .  .  .
 9  8  7 | 6 *13 5 | 4 *13 2
---------+---------+---------
 .  .  . | .  .  . | .  .  .
 .  .  . | .  .  . | .  .  .
 .  .  . | .  .  . | .  .  .

Candidate 1 may be eliminated from the # cells... Why?
Suppose one of the # cells contain a 1, then r2c4 will be forced to 2 and r6c5 will be forced to 3, and we will be forced to have two 1s on c8 (r26c8)!
Therefore all the # cells cannot be 1...

The above reasoning sounds awfully like trial-and-error/assumptions/proof-by-contradiction, right?

How about another angle:

r2c8 and r6c8 cannot both be 1 (obviously).
Therefore either r2c8=2 or r6c8=3 (or both).
No matter which case turns out to be true, at least one of r2c4 and r6c5 must be 1.
Therefore all the # cells, "seeing" both r2c4 and r6c5, cannot be 1.

The above 4 lines are just logical reasoning based on observations... And now would you still think this move is "assumption-based"?

To me it seems to be a very fine line as to whether one type of assumption-based move is allowed and another is not.

Is there any guidance on this from Pappocom?

The fine line is different according to each solver and each program... Pappocom seems to cut it after X-wings/Swordfish etc while Simple Sudoku seems to extend to Colors/Multi-colors/XY-wings...

My own view is: those moves that involve more than 1 digits on more than 1 units (row/column/box) are "advanced"...

So: Naked/hidden singles are not because they involve 1 digit on 1 unit

Subsets (naked/hidden pairs/triples/quads) are not because they involve multiple digits on 1 unit

Locked candidates, fishes (X-wings/Swordfish/Jellyfish), turbot/finned fishes, colors/multi-colors are not because they involve 1 digit on multiple units

But, XY-wings/XYZ-wings/... or forcing chains or almost locked sets or the newly introduced "advanced locked candidates" etc are advanced because they involve multiple digits on multiple units...
(My definition includes even the "remote pairs" which many players regard as quite easy to spot...)

Note that uniqueness-based moves such as Unique Rectangles/Unique Loops/BUGs (Bivalue Universal Graves) belong to another class which might be used subjected to personal preference...

This post is a very good starting point if you want to get to know about the various techniques developed by the experts here...

[richardm]

Thanks for the link udosuk.
I ought to point out that I have no difficulty understanding the logic of your explanations. I don't regard the proofs as incorrect and I don't advocate that branch of metamathematics that denies the prroof by contradiction i.e. Bishop's Constructive Mathematics though it does lead to some suprisingly elegant proofs.

The thing that got me going on this was the statement, apparently originating from pappocom, that guessing was not required. It seemes to me that it is required in a limited form as demonstrated by the previous appends. That was what I wanted to verify.

I was reading an article on Latin Squares in the Mathematical Gazett the other day. There was a discussion on critical sets - the minimum number of cells that need to be known to produce a unique solution. The author made a reference to previous paper that discusses two types of latin square - one where the solution can be derived step by step from the critical set. The other where it cannot, yet a unique solution exists. I haven't followed that up yet, but potentially it points to a whole group of much harder puzzles where none of the techniques we have been discussing can apply.

Come across anyting like this in sudoku?

[RW]

The thing that got me going on this was the statement, apparently originating from pappocom, that guessing was not required.

I believe pappocom has said that in his puzzles guessing is not required. This just means that he chooses the puzzles in such a way that a limited amount of pattern based techniques will lead to the solution. If you pick puzzles randomly this is not the case.

It seemes to me that it is required in a limited form as demonstrated by the previous appends. That was what I wanted to verify.

I do not regard a XY-wing as a guess, sure you must test your hypothesis at first, but once you've done that, you can use it over and over again whenever you see the pattern. Through practise you can learn to spot even bigger patterns at sight, seeing the implications without needing to place a number.

There is puzzles that do require guessing, and there is puzzles that cannot be solved by just applying single guesses and basic techniques. These can be found in the "hardest" thread in general/puzzle. I do not recommend you to take on any of those, many computer programs have tried and failed...

RW

[tarek]

You keep forgetting that guessing is also SUBJECTIVE.....Some people can spot a mate in 7 or more in chess while most people can't, some people FEEL that they are doing the right thing & most of the time they ARE RIGHT.

all of us are trying to put an OBJECTIVE rule for it (whether it is complexity, depth, exponentiality,....).

As people will always remain different in terms of IQ,memory,vision & honesty, this argument will not end.

tarek

[richardm]

You're absolutely right it is subjective and I am not fogetting that at all. What I wanted to do was to explore boundaries of "guess", which to a degree I have done - at least to satisfy my own approach to these puzzles and my own very very broad interpretation of "guess".

I think one could apply a ranking to the methods of deduction per step based on the number of logical arguments in each deduction. Clearly the cleaver solutions use fewer logical steps. Those which employ brute force testing of values at the first sign of difficulty will in general use a significantly larger number of steps.

One could tot up the ranking of all steps from beginning to solution and arrive at a ranking for the solver's attempt. There will be a minimum ranking and the best solver will achive that value.

I wonder whether this provides a method for calculating the difficulty of a puzzle - probably if the advanced techniques score more than the simpler ones,

I might have a look at this and report back if there is any value ranking.

Richard