The words you are looking for: 'deduction' and 'induction'

Advanced methods and approaches for solving Sudoku puzzles

The words you are looking for: 'deduction' and 'induction'

Postby Zotmeister » Fri Jul 08, 2005 1:02 am


I'm seeing an awful lot of arguments on this forum regarding rather flawed terminology. Maybe this will help get everyone speaking the same language and actually know what they're arguing over.

But first, a riddle. Two men are standing along (and on the same side of) a street that runs north-south. One is facing north; the other is facing south... but they can see each other. How?

No mirrors need be involved: the person facing north is simply southward of the person facing south. They can look in opposite directions and see each other because they are facing each other.


There are two forms logic can take: deductive and inductive. Think of them as the direction one seeks logic in. Deduction is the process of taking the general and reducing it to the specific by eliminating impossibilities; induction is the combination of specifics to create a generalization. Both, if used properly, are logic.

The solving of a logic puzzle (such as the one these forums are named after) is a deductive act: the solver takes a generalized version of a solution grid - one that has missing data and at first glance could have multiple ways for that data to be filled in - and eliminates impossible alternatives step by step until it is discovered that only one valid solution yet remains. To quote Sherlock Holmes: "When you have eliminated the impossible, whatever remains, however improbable, must be the truth."

Nonetheless, one can still apply an inductive approach: parts of alternatives can be researched to determine their individual validity, and the valid parts can be kept and added together until the entire puzzle is reconstructed. If there is only one valid solution to begin with, there will be only one valid end result of this process.

So we have deduction and induction, both of which can solve a puzzle. But they work in opposite ways! How can both be useful when they're opposites? Easy - because they're not opposites. They are both logic; they just take different approaches. Place them both along that street, and they're facing each other.


So now that I've defined the terms 'deduction' and 'induction', let's look at the two terms people are arguing about here: 'logic' and 'trial and error'. Okay, as I've already stated, deduction and induction are both logic. So what's trial and error? Isn't that induction? Isn't that what the "pro-logic proselytizers" are saying - that trial and error is logic? But surely trial and error can't be logic - that's what we use when logic fails us, right?

I have yet to see the proper definition of 'trial and error' used here on this forum. The term 'trial and error' belongs to applied sciences, and stems from experimentation; it shouldn't be used in a discussion about logic since it has nothing to do with it. But since it's here already, I'll define it: it is a process through which possibilites for a given situation are researched to find which are superior. When using trial and error, one uses the word 'if' a lot: they note what results if "this" is true, they note what results if "that" is true, and the better of "this" or "that" wins. Trial and error is the asking of all the "if"s; each "if" is a trial, and the results are examined for unfavorable outcomes - errors, if you will - and new trials are run lacking those errors in the hopes of finding something better.

NO ONE uses trial and error to solve a puzzle. If someone talks about "trial and error" in the context of a puzzle, they're wrong - the scientifically-rigorous technical term for what they're talking about is 'guessing'.

Logic is not an applied science. Logicians don't run trials hoping to find something to build a formula on; they don't test hypotheses. They know that there's a definitive answer to whatever problem taxes them. Inductive reasoning may look like trial and error because of all the "if"s, but those "if"s aren't asking about any of a multitude of possible things that may exist - they're asking about a discrete set of choices. They're not trying to improve the quality of future "if"s - they're all on the same level. Inductive reasoning is when all possibilities have been accounted for; guessing is when someone stops as soon as they find what they're looking for.

So the next time you're banging away at a puzzle and you find you need to guess at a cell's value to get an answer, then that's just what you've done - found the solution by guessing - UNLESS you then go back to where you were before the guess and tried all the other possible values you could put there, all those you hadn't deductively eliminated, and show how they all render the puzzle unsolvable. Then you can say you inductively proved the answer. That is complete logic. But...


Only now, with the proper terms in hand, can we attack the real underlying question: Is induction really an acceptable means of solving a puzzle? Yeah, sure, it's all logic, and it proves the solution and its uniqueness, but is it really the best way? Has a puzzle truly been mastered by the solver if brute force was the best they could do for some portion of it?

Here's a classic cliché: how does one find a needle in a haystack? Now by definition, a deductive approach would entail removing all the hay until only the needle remains, and an inductive approach would entail thoroughly searching the space of the haystack by volume until the needle is encountered. Assuming no mistakes, both routes will find the needle. However, the deductive path is the more efficient due to the ease with which the hay may be effectively removed: activate a powerful electromagnet over the haystack and the hay will remove itself by not flying up to the magnet like the needle will.

The real point, though, is that, after having found a needle, how do you know it's the only one? To prove this, induction must keeping searching the rest of the stack; deduction just looks at the magnet.

How does this relate to puzzles? When you find the solution to a puzzle using only deduction, you know the solution is unique. You know there isn't another out there to be found because you've eliminated all others already. You have completely mastered the puzzle - you know everything else out there is a dead end. Those taking an inductive approach, however, upon finding a solution, probably aren't done applying their logic. They have, for all intents and purposes, guessed at the answer unless they finish their thorough search for solutions - they have not mastered the puzzle until they're done, as uncertainty remains if they stop early. Perhaps even worse, though, is that continuing the search after finding an answer could feel tedious, leading them to wonder if it could have been avoided... and if it could have been avoided, that means they could have done better, and if they could have done better, then they haven't mastered the puzzle!

Now for some people, guessing is perfectly fine: they're happy to see a solution, any solution at all, and they're content with that. Others cannot stand such unknowns and will insist upon proving the answer they've found is unique; others still will feel as though they cannot move on unless they've unequivocally defeated the puzzle, and that means using an entirely deductive approach. That is all a matter of opinion for the solvers... but it is the essential guideline of the constructor. Those who compose puzzles that do not leave a purely deductive trail to follow can alienate solvers. That is why all logic puzzles are expected to have unique solutions and not require pure induction for any portion - they cannot be efficiently mastered otherwise, and that's where the deepest pleasure of puzzles is derived from.


But herein lies the heart of the issue: what of deductions supported by inductions?

I admit my guilt: the Polyominous puzzle I provided as a sample to the Wikipedia (look up Filomino) uses this mechanism. There's another topic right on this forum - indeed, the final trigger to my writing this article - that brings it up.

It is possible to solve a puzzle completely through deductive steps while still using induction as a tool for one or more of those steps. Let's say you have a cell you've narrowed down to two possibilities. But for either possibility, some other cell is then forced to take on some particular value, a matching value for both possibilities. You don't need to carry on both possibilities through the entire grid, trying to solve the whole puzzle from both - you've deduced the value of a cell by inductively proving it can't be anything else!

Some will accept this as still deductive: it isn't tedious, it isn't searching the entire grid for every consequence of a possible value for a cell, and it gets the solver right back on track for raw deduction. They'll still know the answer they get when they're done is unique - the puzzle will be mastered. Others may scoff at the fact induction is involved at all: they feel they shouldn't have to look ahead, they feel they shouldn't ever have to follow an assumption any distance, and they feel there's probably some non-inductive-at-all means of proceeding anyway. They may even be right about that.

Ultimately, however, regardless of a solver's approach, a puzzle composer needs to be able to make enjoyable puzzles. Should this be allowed in puzzle construction? Is an all-deductive-steps route to a solution good enough even though some induction is involved in determining them, or is any induction at all too much to ask? Is it anathema to ever expect the solver to place an assumed value in a cell, no matter how transiently, or can it be construed as clever design, making the puzzle more rewarding to solve?

NOW you know what to argue about!:D - ZM
Posts: 3
Joined: 27 May 2005

Postby Karyobin » Fri Jul 08, 2005 2:30 pm

Thank God you turned up Zotmeister!

It's alright everyone, someone's come to educate us all! I jest, poorly.

Had you understood the subtext of any of the postings on the site Zotty-baby, you would probably have realised that the last thing we need is another way to say the same thing. You would also have realised that (amongst those in the know) no-one is arguing about vocabulary, the discussion is really about the spirit of how it feels to arrive at a solution. And we've also agreed by now (thanks to lunababy, primarily) that everyone has their own preferred techniques.

Sorry to come across as argumentative, but there have been some excellent postings on these threads already (none made by myself, I hasten to add) and as much as I don't approve of the verbosity of all of them, I certainly will defend the quality.

And let's face it, it's not that hostile - we all know what happened to the last person who taught in parables.
Posts: 396
Joined: 18 June 2005

Return to Advanced solving techniques