The New Sudoku Players' Forum

[kingo gondo]

I have partially solved the puzzle below. I know the partial answers are correct because I have seen the solution. I can't figure out the next step. I see a X-wing at r5c1, r5c9, r9c1, r9c9 which removes some potential 7's but that doesn't seem to help. Any info will be appreciated.

824 769 513
9*6 12* 874
*** 84* *2*
*89 35* *4*
*45 291 3**
*1* 48* *95
*** 614 ***
49* 578 **2
*68 932 45*

[scrose]

Where did you get this puzzle from? You will need to use trial-and-error to solve this one. I suggest making a guess at r7c9.

[kingo gondo]

I got this puzzle from Friday's (June 24) Los Angeles Times. It's the 5th puzzle since they started publishing Sudoku.

[scrose]

The L.A. Times puzzles are not from Pappocom, as mentioned by Wayne himself. The benefit of Pappocom puzzles is that each puzzle is guaranteed to have one solution only, and that the solution can be reached without having to make any guesses.

[kevinjsands]

If you look at the bottom right grid of 9, the number 9 can only go in one of two places - the top left or the top right. I inserted the 9 in the top right as my first choice and that caused many numbers to flow on from that but eventually it proved to be the wrong choice. So I inserted the 9 in the top left (c7r7) and I think you'll find that is the key to solving the puzzle.

[kingo gondo]

I knew a trial-and-error approach in one of several cells would solve the puzzle but I was looking for a logical-derived solution, if there is one.

[scrose]

I was looking for a logical-derived solution, if there is one.

Well, many here would tend to argue that trial-and-error is a form of logic. But lets not wade into that discussion again...

As I have already mentioned above, this puzzle cannot be solved without guessing. You must resort to trial-and-error to solve it.

If you are looking for puzzles that are guaranteed to have unique solutions which do not require trial-and-error, try Pappocom puzzles. There is a list of U.S. newspapers that carry Pappocom puzzles, or you can download the Pappocom software.

[tso]

A) Though I don't have Friday's LA Times puzzle in front of me -- it's been tossed -- but I solved the puzzle without guessing.

B) The partially completed puzzle as posted here is rated by Pappocom's software as V.Hard, arguably unfair -- NOT invalid.

C) [ ...Edited by Pappocom: Comment C arose from a misunderstanding about the forum in which this topic was originally posted. The topic was moved to this forum ("Non-Pappocom") only when it was realized that the puzzle under discussion was a Non-Pappocom puzzle ...]

All the Los Angeles Times puzzles DO have a unique solution. So far, though I'm not averse to using it, I haven't required trial and error to solve any of them.


D) The partially completed puzzle as shown can be easily solved by a more than one method, for example:

Code: Select all


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



Consider the cell at row 8, column 3 (r8c3) and it's relationship with r5c8.
1) r8c3 can only be 1 or 3
2) If r8c3 is 1, then r9c1 is 7, then r5c1 is 6, then r5c8 is 8.
3) If r8c3 is 3, then r8c8 is 6, then r5c8 is 8.

Since the only two possible results in r8c3 force an 8 in r5c8, we have proved that r5c8=8 and the rest falls easily.

I believe this method has been refered to as "forcing chains" or something like that. There is no guessing, no trial and error, no contradiction. I've found than many puzzles that Pappocom claims as "invalid" that supposedly require trial and error can be solved this way.

The chains can sometimes be very long, but as long as you're dealing with cells that have been narrowed down to two possibilities a piece, it's fairly simple to follow the connections by eye. If it gets too confusing, you can put a circle around pencil marks in a forcing sequence. I mean, if you are already placing marks in the cells other than the final answer numbers, there's no reason to limit the what other information keep track of in there.

Forcing chains can be similarly used to spot a contradiction. Using the same example above, if you start in r5c8, you can follow the forcing chain thusly:

If r5c8=6, then r5c1=7, then r9c1=1, then r8c3=3, then r8c8=6, then r5c8=8, a contradiction. This proves that r5c8 does NOT equal 6, so it must equal 8. This is just another way of looking at the same logic set. (In this case there is a contradiction, but to call this guessing is absurd.)

The argument over whether this is a fair way to solve the puzzle seems odd to me, since as far as I know, EVERYONE makes little pencil marks in the cells of the harder puzzles. If it's fair to write something other than the answer in the grid, any specific limitation is arbitrary. To me, this is the best part of solving the puzzle -- like the endgame in chess where you're looking for a forcing sequence so you can declare "mate in 5", humiliating your older brother, err. (Note to self: edit that bit out before posting.)

This method might be extended to include cells that still have 3 or more possibilities, but with current methods of using pencil marks, it usually beyond the capabilities of most humans. But that doesn't preclude the possibility of discovering a more efficient to handle the information and store it within the cells that might make possible what now appears not. For those that pooh-pooh this eventuallity -- or even the validity of using forcing chains -- why allow ANY pencil marks? If you can't solve it simply by using logic in your head and filling in the cells in big, fat, inked numbers, aren't you using a crutch anyway?

This is the loose, highly subjective rating scale I use for puzzles

Easy puzzles -- solved without pencil marks
Moderate puzzles -- require a few cells to have pencil marks, usually just two marks per cell.
Hard puzzles -- require many cells to have 2 or 3 pencil marks.
Very hard puzzles -- at some point, all empty cells will be filled with pencil marks.
Hardest -- as above, but pencil marks do not seem to help as most cells have 4 or more possibilites. Multiple trial and error required.

[scrose]

Since the only two possible results in r8c3 force an 8 in r5c8, we have proved that r5c8=8 and the rest falls easily.

That was a excellent piece of reasoning. You might be interested in a similar puzzle that was discussed recently.

Personally, I place forcing chains somewhere in the realm between not guessing and guessing. Similar to nishio, this technique will usually offer a solution fairly quickly without having to resort to the really brute-force retrace-your-steps-a-half-dozen-times type of trial-and-error.

The reason I don't quite consider forcing chains to be purely "not guessing" is because it elevates at least one pencilmark to a pseudo big-number status. By somehow identifying a particular pencilmark (you mention circling it), a scenario is now being examined; a "trial" is being conducted. In this example, the two trials (r8c3 is 1 or r8c3 is 3) terminate once a conclusion is reached (r5c8 is 8) before reaching a point of error.

This is where I find the line between guessing and not guessing gets blurred. I would say that a "pure guess" would be of the following variety: "For no apparent reason, I'm going to try placing this number into this cell and see if it will let me solve the puzzle without reaching some form of error." With forcing chains, I feel a type of guess is still being made, but one that seems "nobler": "I'm going to try placing this number into this cell and see if I can conclude something about another cell."

So, I shall withdraw my claim that this puzzle requires trial-and-error: instead, it requires trials-without-error, or perhaps trials-to-conclusion. tso, you're well-stated argument has broadened my perspective on what constitutes trial-and-error, or what is considered guessing. In the future I will try not to be so hasty to slap the "requires trial-and-error" label onto a puzzle.

[little Zivvy]

I think this is another forced-chain example (again a non-standard puzzle).

*4* **6 ***
6** 32* 59*
7*2 *** *8*

*69 *1* ***
*** 8*9 ***
*** *7* 96*

*9* *** 1*5
*13 *52 **9
*** 4** *2*

As with Tso's puzzle above, this one arrives at a position where you can actually see there is a relationship between a group of cells. [In fact reading this thread made be go back to this puzzle]

I arrive at:
9 4 5 .=. 1 8 6 .=. * 3 *
6 8 1 .=. 3 2 7 .=. 5 9 4
7 3 2 .=. 9 4 5 .=. 6 8 1

3/8 6 9 .=. 2 1 3/4 .=. * 5 *
* * * ..=. 8 6 9 .=. * 1 *
1 2 4/8 .=. 5 7 3/4 .=. 9 6 *

2 9 6 .=. 7 3 8 .=. 1 4 5
4 1 3 .=. 6 5 2 .=. 8 7 9
* * * .=. 4 9 1 .=. 3 2 6

The four cells r4c1 (candidates 3&8), r6c3 (4&8), r4c6 (3&4) and r6c6 (also 3&4) seemed linked to me. The problem was I couldn't solve this link with a 'normal' technique. So I was forced to finish this puzzle with T&E .
However, it is easy enough to see in your head (with no more pencil marks) that r4c6 must be a 4 (whatever position the 8 is, then cell r4c6 is a 4). In fact even if a guess is made in Box 4, whatever you choose (3,4 or 8) then the same 4 persists.

Have a failed to see a more 'traditional' logic here?

So, going back to Tso and Scrose's excellent analysis ... it would appear that Sudoku can, on occasion, be solved by the Human Eye spotting a legitimate pattern to force a cell. I'm not sure we should torture ourselves over whether this move is LOGIC or not.
From my experience, anything that involves moving the puzzle forward without 'touching the paper' is hugely satisfying.

[tso]

Since the only two possible results in r8c3 force an 8 in r5c8, we have proved that r5c8=8 and the rest falls easily.

That was a excellent piece of reasoning. You might be interested in a similar puzzle that was discussed recently.

Exactly! That one's even easier to see, but again, the Pappocom software rates that partially completed puzzle as "arguably unfair". Possibly, as this technique becomes codified somehow, he will incorporate it in an update. I seems funny that something that jumps off the page at you, that TELLS you what the value of a cell must be, leads to a discussion of whether it is a guess or not. Is the solver supposed to ignore the information, as if she had peeked the answer in the back of the book? Maybe this highlights the differences in human solving and computer solving. If a programmer cannot put into code the difference between chasing down a forcing chain and brute-force trial and error, then puzzles of wildly different difficulty levels will end up in the same pile. A program MIGHT guess in this situation. I wouldn't.

Personally, I place forcing chains somewhere in the realm between not guessing and guessing. Similar to nishio, this technique will usually offer a solution fairly quickly without having to resort to the really brute-force retrace-your-steps-a-half-dozen-times type of trial-and-error.

The reason I don't quite consider forcing chains to be purely "not guessing" is because it elevates at least one pencilmark to a pseudo big-number status. By somehow identifying a particular pencilmark (you mention circling it), a scenario is now being examined; a "trial" is being conducted. In this example, the two trials (r8c3 is 1 or r8c3 is 3) terminate once a conclusion is reached (r5c8 is 8) before reaching a point of error.

This is where I find the line between guessing and not guessing gets blurred. I would say that a "pure guess" would be of the following variety: "For no apparent reason, I'm going to try placing this number into this cell and see if it will let me solve the puzzle without reaching some form of error." With forcing chains, I feel a type of guess is still being made, but one that seems "nobler": "I'm going to try placing this number into this cell and see if I can conclude something about another cell."

So, I shall withdraw my claim that this puzzle requires trial-and-error: instead, it requires trials-without-error, or perhaps trials-to-conclusion. tso, you're well-put argument has broadened my perspective on what constitutes trial-and-error, or what is considered guessing. In the future I will try not to be so hasty to slap the "requires trial-and-error" label onto a puzzle.

Still, when this method -- call it the "forcing chains proof" or FCP -- is applied, one considers the consequences of BOTH possible values in the first cell at once -- neither choice given any raised status -- in fact, the method does not result in telling you the value of the first cell, only the value at the intersection of the chains shooting out in opposite directions. The first cell remains in a quantum state for the time being. In my experience, this is the method I generally use. The other way of using forcing chains -- call it the "forcing chain contradiction" or FCC -- typically I follow the chain in one direction until it loops back to the starting cell and since I usually do this in my head, the chain will be longer and harder to keep track of this way. It also feels easier to spot the place where to apply FCP versus FCC.

For me, just a humble solver, not a programmer or puzzle maker, any method that I can do in my head is best. The more I have to write, the less I like it -- as I'm terribly messy and hate using pencils, though inexplicably, I refuse to solve puzzles on the computer, only on paper. Solving by reducing choices until a guess would be productive is fine, when required. (Solving even a Very Easy puzzle using *only* trial and error is outrageously difficult.)

For you, FCP is good, FCC maybe not. I wonder though, when you are solving a puzzle, and you notice a connection, some previously undiscovered pattern or sequence that leads you to KNOW, not guess , the value of an empty cell -- what do you do? How do you feel? Do you feel cheated because now you won't be able to find the 'elegant' or 'intended' solution or do you feel smart because you figured out something that you hadn't done before? You were lucky to spot it -- does that make it a guess? Maybe I'm the weirdo -- but that's what I'm looking for -- the flashes of insight that come along with decreased frequency the more you solve a particular type of puzzle.

[scrose]

Have a failed to see a more 'traditional' logic here?

No, I don't think you have. In this puzzle, it looks like you reached the limit of how far "traditional techniques" will take you.

whatever position the 8 is, then cell r4c6 is a 4

Excellent reasoning. Did you find this puzzle posted somewhere else on the forum?

I'm not sure we should torture ourselves over whether this move is LOGIC or not.

In my opinion, this move was definitely logic. For now, I still consider forcing chains to be in that grey realm (the same one I think nishio resides in) between the "traditional techniques" and "pure guessing". However, you and tso have convinced me that forcing chains is a very powerful technique to pull out of the arsenal when a puzzle seemingly reaches a dead end.

[tso]

I think this is another forced-chain example (again a non-standard puzzle).
...

As with Tso's puzzle above, this one arrives at a position where you can actually see there is a relationship between a group of cells. [In fact reading this thread made be go back to this puzzle]

I arrive at:
9 4 5 .=. 1 8 6 .=. * 3 *
6 8 1 .=. 3 2 7 .=. 5 9 4
7 3 2 .=. 9 4 5 .=. 6 8 1

3/8 6 9 .=. 2 1 3/4 .=. * 5 *
* * * ..=. 8 6 9 .=. * 1 *
1 2 4/8 .=. 5 7 3/4 .=. 9 6 *

2 9 6 .=. 7 3 8 .=. 1 4 5
4 1 3 .=. 6 5 2 .=. 8 7 9
* * * .=. 4 9 1 .=. 3 2 6

The four cells r4c1 (candidates 3&8), r6c3 (4&8), r4c6 (3&4) and r6c6 (also 3&4) seemed linked to me. The problem was I couldn't solve this link with a 'normal' technique. So I was forced to finish this puzzle with T&E .
However, it is easy enough to see in your head (with no more pencil marks) that r4c6 must be a 4 (whatever position the 8 is, then cell r4c6 is a 4). In fact even if a guess is made in Box 4, whatever you choose (3,4 or 8) then the same 4 persists.

Have a failed to see a more 'traditional' logic here?

So, going back to Tso and Scrose's excellent analysis ... it would appear that Sudoku can, on occasion, be solved by the Human Eye spotting a legitimate pattern to force a cell. I'm not sure we should torture ourselves over whether this move is LOGIC or not.

Amazingly, this nearly completed example is still rated "arguably unfair" by Pappocom. This may be the only reason that it is an issue for me. I'd like to see Pappocom's software allow creation of "arguably unfair" and even those he currently classifies as "invalid". Maybe we *won't* be able to solve some of them without T&E -- but we will also be more likely to discover new techniques and see some puzzles that might turn out to be the most fun to crack.

From my experience, anything that involves moving the puzzle forward without 'touching the paper' is hugely satisfying.

Amen!

[little Zivvy]

In response to Scrose's question.

The puzzle I quoted was actually one of a bunch I was given to look at on a plane journey. It turns out to be Nr48 from Sudoku org archive.

Luckily I could remember there was an interesting position, when I read this thread yesterday.

On the whole I don't recommend those puzzles.