T&E vs logic

Advanced methods and approaches for solving Sudoku puzzles

T&E vs logic

Postby Guest » Mon Mar 21, 2005 11:19 pm

Following much recent debate on Trial & Error vs Logic,
I would like to point out that, there is NOT a qualitative
difference between them:

You see, in logic, you try to eliminate all possibilities until
you reach the conclusion that only 1 number can go into
a particular square. Now, what you are actually doing is
trying out all other possibilities and eliminating them, until
you have 1 valid solution left. T&E does exactly the same
except perhaps more randomly and with longer sequences
in the elimination process. However, foundamentally, T&E
is the same as Logic, as approaches to Sudoku. Logic is,
in essence, a directed T&E.

Example: Fri Mar 19, Times T2, I solved it by logic, as usual,
but there was a step in the middle I had to postulate a
number and follow its implications for about 7-8 steps
before I could eliminate that scenario. That is T&E.

I am very interested in hearing how computer algorithms
cope with the problem of Sudoku. As far as I know, there
is no effective reduction schemes for this. Anyone?
Guest
 

Postby Guest » Mon Mar 21, 2005 11:46 pm

Hi Yong,

There is a very important difference: T&E involves following the consequences of a postulation, whereas logic eliminates possibilities based on known facts and requires no postulation.

So your solution on Friday was T&E, not logic. Me too! We had a good discussion over the weekend about it in the "Times puzzles" section. We did eventually work out how to solve it logically - without having to chose a value and see what happened - but it took a while!

There are a few threads on solving by computer too - check it out, it's interesting stuff.
Guest
 

Postby Guest » Tue Mar 22, 2005 1:14 am

Hi IJ,
First of all, thanks for reading my post and replying.

IJ wrote:There is a very important difference: T&E involves following the consequences of a postulation, whereas logic eliminates possibilities based on known facts and requires no postulation.


This is actually my point, when logic eliminates possibilities, you are
actually postulating these possibilities in the first place! These possibilities
may be only 1 or 2 deductions long, but they are still postulates: e.g.
you say to yourself, 4 can't go there because if it did, it would violate
the rule due to this and that. You see my point? It probably comes down
to a question of definition of a postulate. Another example, you say 9
can't go anywhere else except here, well in fact you have quickly
postulated/tried the scenarios of 9 being elsewhere and eliminated
them.

IJ wrote:So your solution on Friday was T&E, not logic. Me too! We had a good discussion over the weekend about it in the "Times puzzles" section. We did eventually work out how to solve it logically - without having to chose a value and see what happened - but it took a while!


I think logic is a directed T&E here. When a human solves a sudoku,
he/she is actually performing short T&Es (normally of 1-4 deductions
long) on each cell - and brain can combine and speed up T&Es through
pattern recoginition. Ultimately he/she concludes that 9, say, has to be
there because all other numbers would result in rule violation.
BTW, who are 'we'? you have a club?:)
I pride myself on being able to solve all the Fiendish ones I lay my hands
on and would be interested in joining a forum. I have only discovered this
forum yesterday.

IJ wrote:There are a few threads on solving by computer too - check it out, it's interesting stuff.


I have, but if you have any specific pointers, I would be happy to see
them.
Guest
 
Posts: 312
Joined: 25 November 2005

Postby Guest » Tue Mar 22, 2005 10:59 am

Yes, it's a tricky definition. But there is definitely a distinct difference between making a guess and finding it to be wrong and using the available data to eliminate possibilities. I'm not a good teacher, but I'll have another go...

The example you gave of Friday's puzzle is a good one - your solution of chosing a 7 or an 8 and seeing what happened, is postulation. You'll see if you look at that thread, that I suggested this too at one point, but I was happy with it!

The logic only solution was to note that only two cells in column 8 could contain the digits 6 & 7. This meant those two cells could only contain either 6 or 7, so the other digits could be eliminated as possibilities for those two, which left only one cell possible for another digit in that row (I think it was a 1). There is no postulation in this process at all. Each step is a direct, uncontestable conclusion from the known facts.

See what I mean?


BTW, who are 'we'? you have a club?


I just meant the contributors to that thread - I was one of them. This is the thread... http://forum.enjoysudoku.com/viewtopic.php?t=53
Guest
 

Hi again

Postby Guest » Tue Mar 22, 2005 2:57 pm

Hi IJ,
Yes, I do see your point - you are drawing a subtle line saying that 1-step
trial and errors are obvious and therefore does not count as trial and
errors, instead, they count as logic. I don't have a problem with that -
it is all in the definition of T&E. For example, you see a 4 in column 8
and your logic tells you "4 can't be in any other cell of column 8" - what
your logic is actually doing is postulating a 4 in any other cell and then
immediately encountering rule violation (this is certainly how you'd
rigorously prove the assertion between "..."), this is what I call a 1-step
T&E because the scenario gets eliminated 1 step after postulating the 4.

At this point, you probably agree that it is all in the definition. From my
point of view, logic here is a tight and directed set of T&Es.

The example you gave of Friday's puzzle is a good one - your solution of chosing a 7 or an 8 and seeing what happened, is postulation. You'll see if you look at that thread, that I suggested this too at one point, but I was happy with it!

The logic only solution was to note that only two cells in column 8 could contain the digits 6 & 7.


Well, you have shown that you can progress using quite a few 1 step
T&Es (what you call logic) in combination, or equivalently, a largish
7-8 step T&E (what you call T&E). This is interesting, though obvious
with hindsight.

Therefore, I believe that, at any point in solving the puzzle, there might
be many possibilities of progression, involving different step length T&Es.
Then you can define the logic solution as the one which minimises the
step length at each point of progression!
Guest
 

Postby Guest » Tue Mar 22, 2005 3:59 pm

Fair enough - I think we are saying the same thing.

What you call 1 step T & E and I would call logic, involves deriving information from the current state of the grid.

What I call T & E involves thinking ahead to possible future states of the grid based on a postulation.

For the purposes of the discussion though, I think it's an important distinction because these puzzles can all be solved without resorting to T & E - that is to say that it is always possible to eliminate at least one possibility from at least one cell purely based on the current state of the grid as a whole. At least this is my understanding - there are still puzzles that I cannot solve like this, but I do believe it is possible.

I don't think anyone would say that in the broader sense trial and error isn't a form of logical deduction, but when it comes to discussing Sudoku, it does become important to have terms that describe both methods - thus Logic and Trial and Error.
Guest
 

T&E -v- Logic

Postby Guest » Fri Apr 08, 2005 1:39 pm

I agree with the cross-over between the two methods - for me the T&E method is essentially the starting point for logic.

I find that I am able to use logic entirely for "easy" and "mild" puzzles and the first half a dozen or so of the "difficult" and "fiendish" puzzles.

Thereafter with the latter two I find that (obvious) logic will take me only so far and that I need some T&E to move forward. But when I then proceed using a T&E number based on, say, 75% logic I then find myself coming back to logic to assess the possibilities immediately thereafter.

Sometimes I refuse to consciously make the T&E jump and end up finding I am doing it mentally anyway as I postulate. I don't think I have ever postulated past 3 numbers (i.e. "if that's 2, I'm 99% sure that will be a 6 and that can't be a 3 then x must be 9") because my head begins to hurt (I only do Sudoku on the train in the morning and have very limited time)

Sometimes this works and sometimes not (moreoften not).

I also agree that in theory each grid can be solved without resorting to T&E by successively removing rend returning 1 number at a time and then evaluating the remaining numbers. However, in practice I think that it would be a nightmare.

I did think about writing some code to solve the puzzles but it's essentially combination and permutation modelling which is very interesting but quite hard (for my brain anyway). It would also take away the fun, frustration, righteousness, anger, achievement, sadness, joy, futility and life-affirming emotions I feel during my train journey.....
Guest
 

Postby Spok » Mon Jul 16, 2007 8:00 pm

A very interesting discussion.

I agree that all logical solving is T & E. The simpler the puzzle the fewer steps required. So long as, when you place a number in a square you can say for certain, and prove conclusively, that your number is correct, then it has been found through logic and you can move on.

Guessing, on the other hand is just putting a number in a square and not being able to prove it is absolutely correct before placing other numbers, by which time it is too late.

Spok.
Spok
 
Posts: 6
Joined: 03 January 2006

Postby Steve48 » Tue Jul 17, 2007 12:46 pm

This looks like a pretty old thread, but I agree that it's an interesting one. I also agree that all logic is T&E. The distinction in many people's minds seems to be in whether the process is strictly cerebral or involves writing the steps down. If it's in your head it's logic; if it's on paper it's T&E.

I really like Sudoku, but one of its weaknesses, to me, is that the distinction between "proper" puzzles, which can be solved by logic, and "improper" ones, which involves T&E, is partially a function of who is solving the puzzle.
Steve48
 
Posts: 6
Joined: 06 July 2007


Return to Advanced solving techniques

cron