Elementary form of logic consistantly ignored

Advanced methods and approaches for solving Sudoku puzzles

Elementary form of logic consistantly ignored

Postby tso » Thu Jun 30, 2005 10:22 pm

Earlier today I solved Sudoku from my morning paper. Took maybe half an hour. The puzzle was only rated Tough, the second hardest rating they use. Afterwards, I entered it into Pappocom to check what rating it would get. It claimed that it “is not solvable using logic alone” and was “invalid”. It went on to tell me that “To be valid, a puzzle must be solvable using logic alone. If you must use guess-work or trial-and-error to get the answer the puzzle is not valid.”

Setting aside the argument about whether a puzzle that requires T&E is invalid for the moment, I challenge anyone to point out where I guessed OR used trial-and-error? I’ve been solving these puzzles for years and though I shouldn’t, I take it personally when I’m told that I doesn’t really solves them like them smart peoples does, duh, I’m-a just guessing.

I entered the puzzle into a variety of Sudoku apps -- and they all got stuck at the same point, showing that certain logical steps have not (yet) been implemented. This does not change the fact that this IS simple logic, NOT guess work, NOT trial and error. I don’t believe this topic would EVER have occurred to anyone if no one had ever tried to program a computer to create and solve Sudoku. I’ve NEVER come across this idea in the decades I’ve been doing Sudokus and the hundreds of different logic puzzles in the same genre. Some things that humans do easily might be more difficult to program at first. Not that it can’t be implemented -- or that it will even be difficult to do so -- only that apparently no one has yet. When someone does -- won’t everyone have to change their mind about what is and what isn’t logic and what is guessing? (I don’t really know how my TV’s remote control works -- to me, it is indistinguishable from magic. Maybe it is. But if a high-tech expert tells me it’s done with technology, who am I to insist that it’s magic?)

Ok, here’s the puzzle as printed:

Code: Select all

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


Here’s what it looked like after doing all the currently accepted logical tactics:
Code: Select all

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


At this point, I made pencil marks in the cells that had exactly two possibilities:
Code: Select all

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



I didn’t have to look for too long -- the solution was so simple:
Code: Select all

1) r1c1 must be 1 or 8
2) if r1c1 is 1, then r7c1 is 2, then r7c3 is 4
3) if r1c1 is 8, then rcc3 is 2, then r7c3 is 4


Either way, r7c3 is 4, so r7c3 MUST BE 4!

With this cell filled, the puzzle is finished quickly by more common means.

Below, I’ve removed all extraneous information to make it as clear as possible:
Code: Select all

 1-8   .    .  |  .    .    .  |  .    .    .
  .    .    .  |  .    .    .  |  .    .    .
  .    .   2-8 |  .    .    .  |  .    .    .
  -------------+---------------+-------------
  .    .    .  |  .    .    .  |  .    .    .
  .    .    .  |  .    .    .  |  .    .    .
  .    .    .  |  .    .    .  |  .    .    .
  -------------+---------------+-------------
 1-2   .   2-4 |  .    .    .  |  .    .    .
  .    .    .  |  .    .    .  |  .    .    .
  .    .    .  |  .    .    .  |  .    .    .




*Though I don’t know, haven’t guess, don’t even *care* what the value of r1c1 is yet, haven’t touched pencil to paper, haven’t looked in the back of the book or into a crystal ball, haven’t flipped a coin, certainly didn’t TRY and ERROR -- I have proved r7c3=4 definitively, with very simple, rudimentary, iron clad logic -- the kind of critical, logical thinking they taught us in grade school.

Pappocom says I just guessed.

If only we could get the opinion of someone who worked in a field where one heard ‘logical arguments’ from opposing parties and then had to make ‘decisions’ based on the validity of these arguments -- I suppose one might call them ‘judgments’ -- someone trained to identify logical fallacy. If such a person existed, what would she or he say? I wonder if she or he would disallow logical conclusions such as this as ‘guess work’ in their place of work. If only there were such a magical person and such an honorable career.

One more thing -- generally, when I get to this point in a problem, I solve it the way I did above. Of course I could have seen it this way:
Code: Select all

1) r7c3 must be 2 or 4
2) if r7c3 is 2,
then r7c1 is 1,
then r1c1 is 8,
then r3c3 is 2, which is a contradiction as I now have two 2’s in column 3.
3) therefore, r7c3 must be 4.


I don’t usually do it this way -- not because I have a problem with this type of iron clad logic -- but because usually the chain of reasoning is much longer this way, longer than I can follow in my head. In this particular case however, it’s probably just as obvious to most solvers.

As a non-programmer, it isn’t clear to me why this cannot be implemented and more and more I’m coming to believe it’s because people are allowing themselves to be convinced that it isn’t logic and shouldn’t be implemented. Everybody seems to be jumping on the bandwagon and adding disclaimers like -- “warning, these puzzles may require guessing to solve”, maybe without putting much thought to it.

The idea that using this type of logic makes solving too easy is terribly misleading. When Wayne says that doing this makes a Very Hard as easy as a Hard -- what I hear is that Very Hards are actually are NOT more difficult than Hards! We’re pretending they’re harder by pretending certain types of logic are voodoo. Restrict yourself to ANY subset of logical tactics and solving will be more difficult.

Subjectively, the part of solving a puzzle that is the most fun for me by far is the point at which I have to do what I’ve described above. Wayne says in multiple places that this isn’t fun. I’ve never seen him qualify that by saying “Personally, I don’t find that fun.”, but instead, he speaks for all. I hope people are deciding for themselves.

When asked how long it takes to solve a really difficult puzzle, Wayne said in the Times: “The very hardest? Put it this way. If you were on death row and were due to be executed in the morning, and your guard told you that if you could solve this puzzle you’d be free, then you’d die.”

Really? Assuming he was referring to a 9x9 Sudoku, and that by “morning”, he means no earlier than 6am, and scratch paper, pen and pencil is provided -- Bring it on.

(The puzzle is in the June 30th Los Angeles Times, but as this post is about solving technique rather than the TIMES I placed it here.)
tso
 
Posts: 798
Joined: 22 June 2005

Postby Animator » Thu Jun 30, 2005 10:38 pm

This obviously is a technique to which you have been refering many times lately... (Foreched chains).

The term Trial and Error in this case is obviously incorrect. The term 'Trial' would be correct I guess...

I can see one thing you guess about and that is the cell you chose.

You normally (or atleast I) look at a specific number, row, column or box, but never on one particular cell.

What if you started with r7c3? Then I'm sure you could agree that this is Trial and Error... Yet now you tried another cell, and studiedthe outcome (which is basiclly the same as Trial and Error). What made you choose r1c1 over r7c3? (The only reason I can guess would be that r1c1 is the first empty cell :) )

I'm not sure on this yet, but I'm begining to believe that for each 'Trial and Error'-case there is a 'Foreched chain'-case.


To me this is really close on the edge of Trial and Error, but who am I to set the line?
Animator
 
Posts: 469
Joined: 08 April 2005

Postby Hammerite » Thu Jun 30, 2005 11:00 pm

tso - Hear, hear!

It does make me irate when people around here appear to shut their eyes, put their fingers in their ears and mutter, "That isn't logic! That isn't logic!" to themselves. It's almost a kind of group mentality - why are people allowing the crowd to tell them what's valid logic and what isn't? We're all intelligent people, aren't we?
Hammerite
 
Posts: 44
Joined: 20 June 2005

Re: Elementary form of logic consistantly ignored

Postby Nick70 » Thu Jun 30, 2005 11:34 pm

tso wrote:I entered the puzzle into a variety of Sudoku apps -- and they all got stuck at the same point, showing that certain logical steps have not (yet) been implemented.


My program solves it, using advanced coloring.

It actually puts in 20 numbers all at the same time after the coloring step, because it has proved that they are all chained:)
The only number that it doesn't put down is 2 in (2,3). It leaves that as the last move.

Of course, advanced coloring is a very powerful technique which is like shooting at a fly with a cannon in most cases. One thing that I will try to do when I have time is to make it isolate the simplest chain that moves the puzzle forward.
Nick70
 
Posts: 156
Joined: 16 June 2005

Postby Nick70 » Thu Jun 30, 2005 11:45 pm

Animator wrote:I can see one thing you guess about and that is the cell you chose.

You normally (or atleast I) look at a specific number, row, column or box, but never on one particular cell.


I can't believe I'm reading something like this. This really looks like a denial phase.

Animator wrote:I'm not sure on this yet, but I'm begining to believe that for each 'Trial and Error'-case there is a 'Foreched chain'-case.


This isn't so. Up to now, I've compiled about 18,000 problems. About 12,000 can be solved using common techniques. About 2,000 can be solved using advanced coloring (which includes swordfish and foreched chains). About 4,000 my program still cannot solve without guessing (9 times in one case).

Note: I haven't yet implemented naked/hidden triples in my program so this changes a bit the figures above.

Should anyone be interested in the 9-guesses problem, here it is; I don't expect it to be solvable by logic.

Code: Select all
..1.9.8.5
.326.....
4........
.....5...
..3.1.6..
...4.....
........4
.....712.
8.9.6.3..
Nick70
 
Posts: 156
Joined: 16 June 2005

Postby simes » Fri Jul 01, 2005 7:48 am

Hi tso,

Yep, you're right. I only recently discovered this technique after reading one of your posts, and I hope to add it to my solver soon.
Last edited by simes on Sun Dec 11, 2011 2:31 pm, edited 1 time in total.
simes
 
Posts: 324
Joined: 11 March 2005
Location: UK

Postby Animator » Fri Jul 01, 2005 9:22 am

Nick70 wrote:Note: I haven't yet implemented naked/hidden triples in my program so this changes a bit the figures above.

Should anyone be interested in the 9-guesses problem, here it is; I don't expect it to be solvable by logic.


You can solve it with a single guess...

If r2c1 = 5 then the number 4 will appear in r2c7. (which results in an invalid grid if you continue)
If r2c1 = 9 then the number 4 will appear in r2c7.

So r2c7 must be 4. (ofcourse this is not as elegant as tso's example/grid)
Animator
 
Posts: 469
Joined: 08 April 2005

Postby Nick70 » Fri Jul 01, 2005 10:59 am

Animator wrote:You can solve it with a single guess...


That's a problem with guessing, not only does one need to guess what value is in a cell, but he also has to guess which cell to guess on. If you don't pick the right path, you may have to guess again, and again... I haven't found a good way to pick the cell to guess on, and exploring all possible paths would increase computation time exponentially. I have an idea, though, I will try to implement it.

Animator wrote:If r2c1 = 9 then the number 4 will appear in r2c7.


Eventually it will, but how soon? I don't see a quick path to that.
Nick70
 
Posts: 156
Joined: 16 June 2005

Postby Animator » Fri Jul 01, 2005 11:16 am

Nick70 wrote:
Animator wrote:If r2c1 = 9 then the number 4 will appear in r2c7.


Eventually it will, but how soon? I don't see a quick path to that.


The quickest path (I found):

r2c1 = 9
r2c9 = 1
pair of 4/7 in row 2 ==> r1c6 = 4
r8c5 = 4
r9c2 = 4
r4c3 = 4

At which point there is only one place for the number 4 in column 7. And that happens to be r2c7.
Animator
 
Posts: 469
Joined: 08 April 2005

Re: Elementary form of logic consistantly ignored

Postby rrabbit » Fri Jul 01, 2005 6:45 pm

Let me reword this a bit:
Code: Select all

 1-8   .    .  |  .    .    .  |  .    .    .
  .    .    .  |  .    .    .  |  .    .    .
  .    .   2-8 |  .    .    .  |  .    .    .
  -------------+---------------+-------------
  .    .    .  |  .    .    .  |  .    .    .
  .    .    .  |  .    .    .  |  .    .    .
  .    .    .  |  .    .    .  |  .    .    .
  -------------+---------------+-------------
 1-2  1-4  2-4 |  .    .    .  |  .    .    .
  .    .    .  |  .    .    .  |  .    .    .
  .    .    .  |  .    .    .  |  .    .    .


From the position in box 1, there is a 1 in r1c1, or (non-exclusive or)
there is a 2 in r3c3.

Thus, because there can be only one 1 in c1, and only one 2 in c2,
there is not a 1 in r7c1, or (non-exclusive or) there is not a 2 in r7c3.
Which is equivalent to "not both r7c1=1 and r7c3=2", btw.


The position in row 7 leaves two possible combinations:
1-4-2, and 2-1-4.

Among these two combinations, 1-4-2 does not fulfil "no 1 in r7c1 or no 2 in r7c3".
Thus 1-4-2 is impossible, leaving 2-4-1 as the only possible candidates for r7c1-r7c3.


Thomas
rrabbit
 
Posts: 9
Joined: 22 June 2005

Postby RFB » Sat Jul 02, 2005 5:52 pm

I thought I would try to use this technique on the following puzzle (July 1st LA times).
Code: Select all
.86|54.|9.7
547|.6.|8.3
...|7.8|456
-----------
829|357|641
76.|82.|539
.5.|..6|782
-----------
.78|1.5|264
6..|.8.|175
.15|67.|398

I tried the 1, 3 possibles for cell r1c1 but the 3 option quickly led to an invalid state. So my attempt to solve the puzzle using tso's technique became a basic bifurcation!
  • Is this puzzle solvable using the technique?
  • Where?
  • Are there any clues that would lead me to choosing the pair of cells to use?
RFB
 
Posts: 43
Joined: 03 April 2005

Postby scrose » Sat Jul 02, 2005 7:24 pm

I managed to solve it by using colouring on the candidate 3's.
scrose
 
Posts: 322
Joined: 31 May 2005

Postby Nick70 » Sat Jul 02, 2005 7:44 pm

Coloring the 3s is indeed probably the easiest way.

Another way is to look at this:

Code: Select all
  .    8    6  |  5    4    .  |  9    .    7
  5    4    7  |  .    6    .  |  8    .    3
  .    .    .  |  7    .    8  |  4    5    6
---------------+---------------+---------------
  8    2    9  |  3    5    7  |  6    4    1
  7    6   1-4 |  8    2   1-4 |  5    3    9
  .    5    .  |  .    .    6  |  7    8    2
---------------+---------------+---------------
  .    7    8  |  1    .    5  |  2    6    4
  6    .   2-4 |  .    8    .  |  1    7    5
 2-4   1    5  |  6    7   2-4 |  3    9    8
Nick70
 
Posts: 156
Joined: 16 June 2005

Postby rrabbit » Sun Jul 03, 2005 12:21 pm

Nick70 wrote:Another way is to look at this:

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


Good catch. r8c3 and r9c6 must be identical.
But they cannot both be 4, thus they must be 2.


Thomas
rrabbit
 
Posts: 9
Joined: 22 June 2005

Postby tso » Sun Jul 03, 2005 8:33 pm

RFB wrote:I thought I would try to use this technique on the following puzzle (July 1st LA times).
Code: Select all
.86|54.|9.7
547|.6.|8.3
...|7.8|456
-----------
829|357|641
76.|82.|539
.5.|..6|782
-----------
.78|1.5|264
6..|.8.|175
.15|67.|398

I tried the 1, 3 possibles for cell r1c1 but the 3 option quickly led to an invalid state. So my attempt to solve the puzzle using tso's technique became a basic bifurcation!


1) Start by examining only those cells that have just TWO possibilities first, moving on to those with 3 or more only if you can make no progress. As far as I can tell, at this point there are 3 possibilites for r1c1: 1, 2 and 3 so I wouldn't even look there yet.

2) I couldn't easily follow in my head the chain that leads to a contradiction starting with r1c1=3. But if you did, and you saw that it lead to a contradiction -- hey, a proof is a proof. Go ahead and use that information and go fom there. The goal is to prove each piece of information as efficiently as possible, right?

RFB wrote:
  • Is this puzzle solvable using the technique?


    Yes. Scrose, Nick70 and rrabbit point out the place in slightly different language.
    RFB wrote:
  • Where?


Code: Select all
  .    .    .  |  .    .    .  |  .    .    .
  .    .    .  |  .    .    .  |  .    .    .
  .    .    .  |  .    .    .  |  .    .    .
  -------------+---------------+-------------
  .    .    .  |  .    .    .  |  .    .    .
  .    .   1-4 |  .    .   1-4 |  .    .    . 
  .    .    .  |  .    .    .  |  .    .    .
  -------------+---------------+-------------
  .    .    .  |  .    .    .  |  .    .    .
  .    .   2-4 |  .    .    .  |  .    .    .
 2-4   .    .  |  .    .   2-4 |  .    .    .

1) r5c6 = 1 or 4
2) if r5c6=1, then r5c3=4, then r8c3=2, then r9c1=4
3) if r5c6=4, then r9c6=2, then r9c1=4

This proves that r9c1 must be 4. Everything else follows easily.
RFB wrote:
  • Are there any clues that would lead me to choosing the pair of cells to use?


  • Sure. Focus on:

      Cells that have only two possibilites.

      Cells that share at least one possibility with at least two other cells. (Each cell in the solution must connect to at least two others.) For example:

      Code: Select all
        .   1-2   .
        .    .    3-4
       2-3   .    4-5


      The "2-3" and the "3-4" are each have two connections. The other two must connect again elsewhere or there they are dead ends.

      Three or more cells in the same group that share possibilites may give multiple routes for the chain.

      Cells that are connected to more than two others.

      Cells that are *strongly* connected, that is, each have the same two possibilities and no others.

      Code: Select all
        .   1-2   .
        .    .    .
       1-2   .    .


      Three cells can be MUTUALLY strongly connected if they are all in the same group, each has exactly 2 possibilities and each shares exactly one possibily with each of the others:
      Code: Select all
        .   1-2   .
        .    .   1-3
       2-3   .    .


      Find the shortest closed loop of connected cells first.



      Regardless of the different language used to describe this, it is often very easy to find once you've done it a few times. I find it much easier than some of the tactics required to simplify the puzzle to the point where it is possible to use, so there's no reason that puzzles that require this technique should automatically considered outlandishly difficult. The range of difficulty is huge.

      It's interesting to think of it this way: If this were a Pappocom puzzle, you would have finished solving one step sooner, without having applied this technique. But because it wasn't, you got to do everything you would have done with a Pappocom puzzle, plus one more step. You don't give up anything by using this technique, or bifurcation or coloring, etc. These techniques are generally too difficult to apply before you've done everything else. Even though I don't think this last step is as hard as some others, it does increase the overall difficulty of the puzzle somewhat.
    tso
     
    Posts: 798
    Joined: 22 June 2005

    Next

    Return to Advanced solving techniques