The New Sudoku Players' Forum

[Silver Surfer]

Folks,

This 5-star puzzle appeared in the USA Today September 30th edition. Its solution apparently requires more than my beginner's skills can provide. Need a little push in the right direction.

Code: Select all

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

Candidates
  .   .  . | .  .  . | .  .  .
  57  .  57| .  .  . | .  .  .
  .   .  . | .  .  . | .  .  .
 ----------+---------+----------
  29  . 126| 56 . 49 | 45 . 12
 389  .  18| 35 . 79 | 58 . 17
 238  . 268| 36 . 47 | 48 . 27
 ----------+---------+----------
  27  .  . | . 57  . | . 25  .
  .   .  27| . 57  . | . 25  .
  58  .  58| .  .  . | .  .  .

 

[angusj]

Need a little push in the right direction.

It requires a forcing chain:
r4c6 could be either 4 or 9.
if r4c6 = 4, then r6c6 = 7, r6c9 = 2, r4c9 = 1
if r4c6 = 9, then r4c1 = 2, r4c9 = 1
either way r4c9 = 1
Solves easily after that.

[tso]

I'm surprised (and happy) that USA Today is publishing puzzles requiring advanced methods.

I don't think there's anything simpler than a forcing chain.

There is a forcing chain in these five cells:

Code: Select all

  .   .  . | .  .  . | .  .  .
  .   .  . | .  .  . | .  .  .
  .   .  . | .  .  . | .  .  .
 ----------+---------+----------
  29  .  . | .  . 49 | .  . 12
  .   .  . | .  . 79 | .  . 17
  .   .  . | .  .  . | .  .  .
 ----------+---------+----------
  .   .  . | .  .  . | .  .  .
  .   .  . | .  .  . | .  .  .
  .   .  . | .  .  . | .  .  .


Both values for r5c6 force r4c6=4

[EDIT: Argusj beat me to it. Either of this and several other similar chains will work. I don't think there is anything shorter.]

[Silver Surfer]

Forcing chain? Now that is something completely foreign to me. How do you go about identifying these things?

[r.e.s.]

Brendan's Sherlocking method can also be applied here ...

Using row 4 & row 5:
The allowable permutations of candidates for row 4:
2 6 5 9 4 1 <-- call this A
9 1 6 4 5 2 <-- call this B
9 2 6 4 5 1 <-- call this C
The allowable permutations of candidates for row 5:
3 1 5 9 8 7 <-- call this D
8 1 3 9 5 7 <-- call this E
9 8 3 7 5 1 <-- call this F
(C,D) is the only compatible pair, etc.

Alternatively, using row 4 & row 6:
The allowable permutations of candidates for row 6:
2 6 3 4 8 7 <-- call this H
8 6 3 7 4 2 <-- call this I
3 2 6 4 8 7 <-- call this J
3 8 6 7 4 2 <-- call this K
(A,J) and (C, I) are the only compatible pairs, and both have r4c9=1;
therefore, r4c9=1. Etc.

[PaulIQ164]

I'm surprised (and happy) that USA Today is publishing puzzles requiring advanced methods.

One suspects, though, that it's not because they've got a spiffy generating program that understands forcing chains, but rather because they have a quite poor generating program whose only criterion for hard puzzles is that they have a unique solution.

I'd be less happy for the regular readers of USA today who are being presented with puzzles that require them to essentially invent brand new techniques (or else resort to T&E) if they want to solve them, presumably without warning or explanation.

[tso]

I'm surprised (and happy) that USA Today is publishing puzzles requiring advanced methods.

One suspects, though, that it's not because they've got a spiffy generating program that understands forcing chains, but rather because they have a quite poor generating program whose only criterion for hard puzzles is that they have a unique solution.

You are correct -- I spoke too soon. I checked some of their other 5 star puzzles and none required anything besides singles. This one may have been an anomoly.

I'd be less happy for the regular readers of USA today who are being presented with puzzles that require them to essentially invent brand new techniques (or else resort to T&E) if they want to solve them, presumably without warning or explanation.

However, this is NOT a difficult problem as forcing chain type puzzles go! It's one thing to require a forcing chain when there are many cells with 3, 4 and more candidates, but in this case, simple logic ends with 24 2-candidate cells and just 4 3-candidate cells. At least two solutions are only 5 cells long. The problem can also be solved using binary groups, drawing labeled edges and looking for repetitive loops, several other methods that are beyond me, and yes, even simple trial and error -- not to mention gestaldt. Why puzzle solvers need to be warned that they may be required to think is beyond me. Before the introduction of Sudoku to the non-Japanese world, there was no precedent that I can find for warning the puzzle solver that they might have to figure out how to solve the puzzle. Solvers are given the rules, and rudimentary tips, most of which are useless. Even the Times does not give full tactics for the Killer, not even mentioning the various combinations possible for different totals and how this information can be used. Figuring out *how* to solve the puzzle is what its all about.

[Guest]

double row elimination for 5
r7c1=27
r8c3=27
x-wing for 8
r5c1=39
x-wing for 2
r4c1=9
the rest is trivial

[tso]

double row elimination for 5
r7c1=27
r8c3=27
x-wing for 8
r5c1=39
x-wing for 2
r4c1=9
the rest is trivial

Could you explain this?

What is "double row elimination"?

There is no x-wing in 8's.
There is no logical reason to remove the candidate 8 from r5c1.
There is no x-wing in 2's.

[Guest]

step one
box 8 has to have a five in either row, say row 7
now box 9 will have a 5 in row 8

another possible is
box 8 has a five in row 8, now box 9 has to have a five in row 7
in either case, row 7 and 8 are taken, therefore the five in box 7 can not be in row 7 or 8

this type of technique is also known as the x-wing

here is a picture to ilustrate




the second step
a variant of the x-wing technique is called swordfish
it combines two x-wing techniques to come up with a solution, one wing corner touching the other
the requirement is that three rows or three columns must have no more then 3 unknown cells sharing the same columns or rows respectavily
this means, r5c1 can not contain an 8 as a possible




third step
same technique as before but one thing
note: just because the 4(r8c1) is there does not mean it would not have contained the 2 as a possible when we do the consideration
this leaves us with the conclusion that the cell in r5c1 is a 9




i must clarify, this technique is not derived by me
here is a link that explains it
http://www.angusj.com/sudoku/hints.php
i hope this helps


side note, my program helped in comming up with the solution
current posted version only solves for
single_naked
single_hidden

version in progresss solves
single_naked
single_hidden
two_naked
two_hidden
three_naked
three_hidden
row_column_elimination

if you want to check it out, go here
html://www.evropej.notaggaming.com/sudoku.html

[angusj]

i must clarify, this technique is not derived by me
here is a link that explains it
http://www.angusj.com/sudoku/hints.php
i hope this helps

Evidently my description wasn't clear enough since you don't yet seem to understand swordfish .

Edit: corrected typo.

[cho]

Brendan's Sherlocking method can also be applied here ...

Using row 4 & row 5:
The allowable permutations of candidates for row 4:
2 6 5 9 4 1 <-- call this A
9 1 6 4 5 2 <-- call this B
9 2 6 4 5 1 <-- call this C
The allowable permutations of candidates for row 5:
3 1 5 9 8 7 <-- call this D
8 1 3 9 5 7 <-- call this E
9 8 3 7 5 1 <-- call this F
(C,D) is the only compatible pair, etc.

You gotta love it when a single technique solves a dozen cells in one fell swoop. But it's simply branching. I still see no need to write out all possible permutations when you're just saying "if r4c1 = 2 it leads to a contradiction (two sevens) in row five, so r4c1 = 9". You're left with a (12) pair in row 4, but they quickly sort out when you apply the rest of your deductions to row 5 (which is why your C is compatible).

These two rows being so nicely aligned and interdependent is certainly ideal, but damn... That's almost cheating.

cho

[Guest]

let me tell you how to force an answer
start with asuming
r6r4 is a 6
then r4c4 is a 5
then r5c4 is a 3
then r4c7 is a 4
then r4c6 is a 9
then r5c6 is a 7
then r6c6 is a 4
then r6c7 is a 8
then r5c7 is a 5
then r5c9 is a 1
then r4c9 is a 2
but from r4c6 we have r4c1 being a 2 also
contradiction
which mean assumption is wrong and therefore
r6c4 is a 3
then r5c4 is a 5
then r4c4 is a 6
then r5c7 is a 8
then r6c7 is a 4
then r6c6 is a 7
then r5c6 is a 9
then r4c6 is a 4
then r4c7 is a 5
then r5c3 is a 1
then r6c3 is a 6
then r4c3 is a 1
then r4c3 is a 2
then r4c1 is a 9
then r5c1 is a 3
then r6c1 is a 8
then r6c3is a 6
you can get the rest
as far as the swordfish explanation, im still comming up with it
i need to program that next in my game so im going to need a good understanding of it before i start using it in my code
hope this solves the problem for you

[dgmp]

Don't know about these new techniques but you can try this very simple method with binary cells if you are using pencil and paper. Very good if you are a beginner.

You mark the cells belonging to a strongly linked binary chain. Each cell in the chain has two candidates only and is strongly linked to another cell in the chain. That means that one candidate in the cell appears only once more in the same row ( or column or block ).

When you find cells in this chain, mark the cell by circling the cell. If necessary reverse the numbers in each cell so that the first candidate in a cell matches the first candidate in the other cells in the chain. You do this without having to make inspired guesses; it should be done automatically and will frequently solve the puzzle.

In your example you can start with column 7 where the cells are all strongly linked and the numbers do not have to be reversed. Then looking at row 4 columns 6 and 7, these are linked by the candidate 4 but the r4c6 has to be reversed to be 94. Keep finding cells in the chain and eventually you find two cells: r4c1 and r4c9 which are 21 and 29 which eliminates the first option in all the cells in the chain and the problem is solved.

One word of warning: just having two cells with two candidates that match does not guarantee a forcing link. In your puzzle, the cells r5c3 and r5c7 have a 8 in common but are not ( yet ) strongly linked because there is another 8 in the row. In this case you find they are strongly linked. This can be used to eliminate the other 8 in the row. In other cases as r4c1 and r4c9 they provide a contradiction.

The nice thing about this method is that you just look for the cells that match and extend the chain as far as possible. It does not matter where you start the chain or which direction you are going. I started in column 7 but you could have started anywhere in the chain. You can do this without too much thinking or complexity. There are some interesting and more complicated variations with more than one chain. I suppose this can all be done with colouring but I only have an HB pencil and an eraser.