The New Sudoku Players' Forum

[re'born]

I am new to this forum...

Welcome to the forum wychwood.

If others do agree, then what are the alternatives to Forcing Chains that ARE vaild for solving puzzles?

You might find this thread interesting.

[wychwood]

I am new to this forum and certainly new to many of the advanced solving techniques discussed on this forum.

However, I am a keen Sudoku puzzler and feel the need to ask whether others feel that Forcing Chains is a technique that is not quite in the spirit of the puzzle?

Now, call me too much of a purist (or even a pedant) if you will, but any technique that requires one to start with "I wonder what happens if that cell is 'n'" is a trial and error technique and NOT logic, reasoning and deduction.

So, should it be there as a solving technique at all, for any Sudoku puzzle that is true to the basis of these puzzles - solvable by logic and reasoning only?
If others do agree, then what are the alternatives to Forcing Chains that ARE vaild for solving puzzles?

Cheers
Neil

[ravel]

Hi wychwood,

rep'nA already showed you a link to one of the most powerful alternatives, dont forget the big fishes also, subset counting, mutlidigit coloring and uniqueness based methods and others you can find in Mike Barker's link collection.

But be aware, that all of them were not able to solve the hardest sudokus. So in the moment we just have to accept, that there are a lot of puzzles, that neither can be solved with non assumptive techniques nor in any elegant (and human readable) way.

If contradiction chains (starting with "if cell A is x") are more elegant than other methods in some cases is a matter of taste.

On the other hand, for each technique you like, there will be a lot of puzzles, where it is fun to use it. Just ask for them, i am sure someone here will help you.

[re'born]

...but any technique that requires one to start with "I wonder what happens if that cell is 'n'" is a trial and error technique and NOT logic, reasoning and deduction.

What makes you say that T&E is not logic, reasoning and deduction. It is certainly not illogical nor unreasonable and it definitely deduces something.


BTW, does anyone know how my post aboves comes before the post to which I responded?

[ronk]

BTW, does anyone know how my post aboves comes before the post to which I responded?

You're clairvoyant Seriously, I think wychwood can confirm he deleted his original post ... and then reposted.

[re'born]

BTW, does anyone know how my post aboves comes before the post to which I responded?

You're clairvoyant

Funny. I knew you were going to say that.

[Binarius]

...but any technique that requires one to start with "I wonder what happens if that cell is 'n'" is a trial and error technique and NOT logic, reasoning and deduction.

What makes you say that T&E is not logic, reasoning and deduction. It is certainly not illogical nor unreasonable and it definitely deduces something.

Logic, reasoning, and deduction it may be, but wychwood is probably right in that the "purists" among us would dispute the spirit of any perfectly reasonable logical deduction made by, say, throwing a digit into a bivalue cell without justification and checking for contradictions. I agree: "If I were to put 'n' into this cell, then...um...what would happen?" is not a valid sudoku move, it's an experiment, and logic puzzles never require experimentation.

Let's not mince words: every step of the solution to every sudoku can be deduced without recourse to experimentation, assumption, or brute force, even if the logic required is inhuman -- say, a case of the Extended Subset Principle that has yet to be described in terms of any recognized rules, strategies, or patterns. This is quite simply because the rule of sudoku leaves no room for logical ambiguity: all you need is propositional calculus. The rest is just layers of complexity.

Of course, this is precisely the reason that it's easy for us humans to regard any sufficiently advanced deduction as indistinguishable from magic, as it were. Take any patzer with a pencil and confront them with a Hidden Pair; before they learn to recognize the pattern without having to make assumptions about it, they will simplify the situation in the same way that the purists are all tempted to once in a while: "Oh dear, there are two places this 4 can go. I wonder what will happen if I put it here?..." In the end, serious students of the grid are no different: think back to the first time you ran into what you now know as some familiar "theoretical" pattern -- a Sashimi Swordfish, say, or a Death Blossom. Forgive my skepticism, but I'm willing to bet that your first thought didn't exactly read like a sudopedia entry.

As for Forcing Chains, let's not be so quick to strike them from the record. They serve a very forward-thinking purpose in that we can derive contradictions from them that will help us solve the puzzle without having to delve into the realm of the hypothetical. Their essence is simple: since every forcing chain consists of two sets of candidates, one of which must be true and the other false, then any candidate in the grid that is weakly linked to one candidate from each set must be false. That one little trick, in various permutations, covers every single chain, cycle, and loop you're going to run into, be it nice, fishy, wingy, colorful, or even naked or hidden. And such a deduction can hardly be considered shooting first and asking questions later; indeed, what could be more "in the spirit of the game" than figuring out by yourself that if P then Q; if not P then Q; therefore Q before you put pencil to paper?

[ravel]

The rest is just layers of complexity.

This is the point for me. Often a solution with nice loops or contradiction chains is both found and explained faster and easier than solutions with non assumptive methods. If you like it or not, from my experience this is a fact.
Also note, that people, who use them, dont try candidates randomly like monkeys or systematically like programs, but they follow a concept they develop by spotting (almost) properties of a puzzle.

[RW]

So, should it be there as a solving technique at all, for any Sudoku puzzle that is true to the basis of these puzzles - solvable by logic and reasoning only?

Yes, it should be there. The forcing chain is the mother of all techniques. All pattern based techniques are just common forcing chains defined as patterns. If nobody ever did forcing chains, then nobody would have discovered any techniques more complex than subsets and uniqueness techniques. We see it quite often here, someone shows a deduction based on a short forcing chain and the next day it is described as a pattern. I don't see why the eliminations made based on the pattern would be more valid that the one made based on the forcing chain. If i find a nishio forcing chain, I could go to the "Ultimate Fish Guide" and most likely find a pattern based explanation for the elimination, would that make it more valid?

Another reason why I like forcing chains so much is that most other techniques rely very heavily on pencilmarks. Browsing through this forum you will find very few techniques that aren't described through patterns in the pencilmark grid. I never use pms when I solve on paper, so forcing chains is the way to go. Often when I find some short forcing chain I might have a closer look at it and notice that it was actually a swordfish or XY-wing. But in most cases even the short chains I find are not formally described as a pattern yet. I guess this is because I mostly see chains with hidden singles (if A => hidden single B) while most patterns use chains with naked singles (XY...-wings, APE, ALS...).

I'd say T&E starts when you input information in the grid that you aren't certain of. If you actually write down your assumption and continue solving from there, then you are guessing. If you are creating complex networks of implications inside your head, then you are analyzing the grid. Also, if you write down facts about the grid on a separate sheet (like strong/weak links) and then analyze them, I think it's perfectly ok, though I don't do that myself.

RW

[re'born]

Binarius,

Of this I am certain, there is a class of puzzles that currently I can solve without the aid of a computer and without using T&E, in an amount of time that allows me to work, eat and spend time with my wife and son (cheap plug!), and then there are the rest of the puzzles. It is never acceptable for me to use T&E to solve those in the complement. I get no pleasure in choosing a cell (even one chosen with a well conceived strategy) and checking the consequences. It just isn't fun for me. However, my wife has no problem with taking this route on a difficult puzzle (especially one I couldn't solve) and proudly producing a solution. Another thing of which I am certain is that I will not be the one to tell her

"If I were to put 'n' into this cell, then...um...what would happen?" is not a valid sudoku move...

If you were lucky, she would respond, "but I thought the only rules were that each row, column and block should have the numbers 1 through 9 and that the solution be unique."

I don't want to know what would happen if you were unlucky.

I don't believe that one should try to define or even talk about the "spirit of the game", other than to say that it is about having fun. There have been too many arguments on these boards (though mostly on the Eureka board from what I've seen) because people are unwilling to ignore posts using techniques they disapprove of, and insist on trying to convince others that (effectively) they know what makes Sudoku fun.

[wychwood]

Thanks to all who have responded to this - very interestig reading.
To be honest, I am not sure where I sit on my own question - partly because I just don't know what all these alternative fancy-named solving techniques are (or at least, I don't know how to use them).

But all I feel inside is that, when I started solving Sudoku puzzles/games, I belived that it was always possible to find a cell that HAD TO BE a single number between 1 and 9 because logically that was the only number that could go in it. I therefore feel slightly 'cheated' when I get to a point with, say, 15 cells to go when the only availbale way of getting further (as far as I can see) is to try one of two possible candidates in a cell and see if it works. I just feel that that is not a proper solving technique (or maybe it was never a proper puzzle in the first place??).
That is why I feel uncertain about Forcing Chains - BUT, they are a way of solvng some puzzles and thus they prevent the frustration of not solving it (and therefore also increase the enjoyment of these things).

Neil

[_m_k]

"But be aware, that all of them were not able to solve the hardest sudokus. So in the moment we just have to accept, that there are a lot of puzzles, that neither can be solved with non assumptive techniques nor in any elegant (and human readable) way."

It seems to me that if one can show such puzzle(s), then it will stop/settle this discussion once for all; namely so-called "purists" cannot solve such puzzle(s). I surely like to see such puzzle(s).

M.K.

[ravel]

It seems to me that if one can show such puzzle(s), then it will stop/settle this discussion once for all; namely so-called "purists" cannot solve such puzzle(s). I surely like to see such puzzle(s).

You can find them in the "hardest" thread, my current top list is in this post.
Maybe i should add, that non purists cant solve them either in reasonable time and not in a way, they could explain someone while watching rep'nA's son in the sandbox.

[Joe Wey]

Here is my opinion on this:

Even if you scan your Sudoku for patterns you perceive as acceptable, you “try” to find them. You try in the sense that there is no guarantee to find one … and you will “try” the next pattern after that, won’t you?
The discussion what is trying and what is not is pointless. The true point is what is worth trying and what is not!
Let me put some more thoughts into this.
We call a hypothesis what obviously is one, i.e. an unproved fact in a Sudoku (a placement of a digit is a trivial example, an exclusion of a digit at a certain place is another trivial one, any fact that adds knowledge relevant to the Sudoku is an acceptable hypothesis as such). Let’s call a “good hypothesis” one that gives you immediate inferences to other facts. A digit in a cell entails another one in another cell, which entails another one etc.. Is it worth following such a ”good” hypothesis? No! It eventually might solve your Sudoku, but this is is very unprobable and it just burns your time trying to go forward, or it may yield a contradiction, which may be a little more probable, but unfortunately you do not know your chance to find one, and, even if you happen to find the contradiction, it may be of little value. Normally it takes you into a time consuming exercise without any conclusion. So this is trying in the true sense.
Let’s call a bi-valued hypothesis a pair of hypothesis that is mutually exclusive. Again, a bi-valued cell is a trivial example. Let’s finally call a strong bi-valued hypothesis a pair of mutually exclusive, good hypothesis.
Following any one out of such a hypothesis pair will give you for sure good information if it “ends” (meaning lands into a solution, perfect (!), or a contradiction, less perfect but good information since it validates the conjugate, good hypothesis).
What if it does not end that easily, which you normally expect to happen? It then does establish a strong inference net, and that is what is the true interesting point about all this. There is a simple but powerful law associated with this: any fact that may be inferred by a pair of conditionally true facts a (true under hypothesis A) and b (true under hypothesis B) is true anyway and may be concluded as an unconditionally true fact for the Sudoku. Using this law, the net, if it happens to be a “good” one, generates clues without the need to take it to an “end”!

Let’s take an example to illustrate this. Take the Daily Nightmare of 19th Feb 2007. The Sudoku, after the basics, ends to be the following one:

16....8.....34 |9.......35.........16|25.........7......2345
2....56.....13 |8.........4..........7|156.....136......9
9....456.....7 |56......135........2|8.........136......3456
---------------+-------------------+----------------
13....34.....6 |14........29........8|29........5.........7
5......2......19|16.........7.........3|169......4.........8
8......7....149 |1456...1259..169|3........126.....26
---------------+-------------------+-------------------
7.....36......5 |2.........19.......19 |4........8........36
4......9.......8 |37.......6...........5|27.......23.......1
36....1........2|37.......8...........4|567......9......356

Now take the strong hypothesis pair (r4c2 = 3, r4c2 = 4) and look at the corresponding inference chains which come very easily (I label the conditional facts for ease of reasoning):

(r4c2 = 4) (1a) --> (r3c2 <> 4) (2a)--> (r1c1 = 1) (3a)--> (r1c6 = 6) (4a)--> (r3c4 = 5) (5a)

(r4c2 = 3) (1b--> (r4c1 = 1) (2b) --> (r1c1 = 6) (3b) --> (r2c2 = 5) (4b) --> (r3c2 = 4) (5b) --> (r1c3 = 3) (6b) --> (r1c5 = 5) (7b)

Take fact (5a) and (7b). Both infer (r3c5 <> 5), since r3c5 sees a 5 in each chain, so this is a true fact and you may eliminate from that cell the 5.
And now take (5a) and (5b). Both infer (r3c2 <> 5), so you may eliminate 5 from that cell, which by the way, gives you (r2c2 = 5) and yields a naked triple in box 3 and so on!

This is not the end of inferences you may get out of this inference net, just go on extending it as long as it is easy and look carefully at the combination of your conditional fact chains. Marking the chains visually will easily disclose the clues.

Let’s take another strong hypothesis, just for the sake of the exercise:
(r2c2 = 6, r2c2 = 5).

(r2c2 = 6) --> (r1c1 = 1) --> (r1c6 = 6)
(r2c2 = 6) --> (r3c2 = 5) --> (r3c4 = 6)

Oops, this is a contradiction! Too bad my chain just luckily generated that contradiction and it is not out of a known pattern that I got it … Well, if there is no known pattern for your clue, go and construct one! This has been so immediate that we can actually easily do so.

Looking at the contradiction carefully you construct the following nice, regular law:
Given 2 same digits in a box a, if you can find a box b with two facts in b inferring each one of these digits, if, in addition, one single fact in box b yields these two inferring facts, this later one must be wrong.

In our example the one 6 in box 2 is inferred from (r1c1 = 1) in box 1, the other 6 in box 2 is inferred from (r3c2 = 5) in box 1, both of these are inferred from (r2c2 = 6), so we can eliminate 6 from r2c2.

It is, from a pure logical point of view, of course unnecessary to require the 2 inferring conditions to be in one box. Looking at this law it is somehow like an inverse XY-wing. Now, what is the interesting point about the XY-wings? They are a special case of a much more generic law but they are easy to find because they are that specific! So, let’s keep the restriction to have the inferences in one box, and let’s see if we can use our pattern in our daily nightmare example. Look at box 5 with two 9 in 2 rows. One of them may be inferred by (r4c7 = 2) in box 6, the other one by (r6c7 and r6c8 do contain 1 and 6) in box 6. Both of these are trivially entailed by (r5c7 = 9), so we may eliminate the 9 in this cell! Lucky strike? Look at two 6 in box 9. One may be inferred by a 3 in box 3, the other one by a 5 in the same box (in the corresponding rows). Assume (r3c9 = 3), and look at that, it yields also (r2c7 = 5). So we can eliminate, by our pattern, both 3 in r1c9 and r3c9!

So, we have discovered a new pattern! I call it JoBIP (Joe’s backward inference pattern). Is it a special case of a pattern long known before? Maybe, I do not care. Is it a good pattern? I do not know. It is my personal one, I may do with it whatever I want, I may breed it, enhance it, change it, or throw it away if it does not really generate that many clues at the end! It has been great in this one Sudoku. But for sure it gave me a nice, very valid insight into the intrinsics of a Sudoku as such. And all this came from “trying” …

[ronk]

Joe Wey, be aware that double-posting and crossposting are usually frowned upon.