The New Sudoku Players' Forum

[randolphpaintball]

HI
Just starting with this game.

Do you have a sense if at some point you have to guess at abox solution. Trying out a number to see if it works?

Or should you be able to "calculate" every entry?

TTX
Marty

[PaulIQ164]

If you're getting your puzzles from a decent source, they should all be doable without guessing. You can certainly guess if you want - it's a solo activity after all; who's going to stop you? As to whether there's any way to know if it's time to guess - not really. That's the problem with puzzles that require guessing: when you get stuck, there's no way to know if it's because there's a logical move that you've missed, or if you've reached a point where you have to guess.

[tso]

Paul164 -- we've gone over this so many times. As long as a puzzle has a unique solution, it cannot *require* guessing. There is *always* a logical solution -- even if that solution beyond the capabilites of the individual solver (human or otherwise) working on it.

[9X9]

RPB - The better Su Doku puzzles, such as those generated by the Pappocom software, have only one solution and never require trial and error (guessing). For me, these are the only ones worth doing and I avoid the others like the plague.

When you are learning the solving techniques, probably as you graduate from easy to harder puzzles, you are likely to reach a point where it seems that the only way forward, on a particular puzzle, is to guess eg between value A or value B for a cell and see which of them then leads to an impasse. As I say, provided that the puzzle is a "proper" one and that you have made no preceding mistake, your perceived need to guess will probably stem from a mixture of inexperience and incomplete technical knowledge.

If you have not already done so, then the best way for you to rectify this, so that you can learn and move ahead, is to go to www.angusj.com and www.simes.clara.co.uk and absorb all the Su Doku techniques that are set out there.

[PaulIQ164]

Paul164 -- we've gone over this so many times. As long as a puzzle has a unique solution, it cannot *require* guessing. There is *always* a logical solution -- even if that solution beyond the capabilites of the individual solver (human or otherwise) working on it.

Yes. I've never seen this proved (I've never looked) but I entirely believe you. I meant "requires guessing" in the casual-solver-solving-in-the-paper sense (since he did say he was just starting out at sudoku). Should have been clearer, sorry.

[Moschopulus]

Paul164 -- we've gone over this so many times. As long as a puzzle has a unique solution, it cannot *require* guessing. There is *always* a logical solution

The old chestnut. Just to be clear, which of "guessing" and "logical solution" means "backtracking" for you? As 9x9 said, backtracking means at some point you make a choice between A and B for a cell, and see if your choice leads to an impasse.

I think many of these arguments happen because people don't define what they mean by "guessing" and "logic". People end up arguing when they actually agree.

[Lummox JR]

I think I can finally draw an appropriate line between guessing and trial and error.

In T&E, a trial candidate isn't considered "right" merely by placing it and finding no contradictions. T&E must either find a contradiction, or it must affirmatively place or fully eliminate a number by trial candidates in another set of cells. That is, if all the choices for (1,1) indicate that (5,1) is not a 6, then you can eliminate 6 there. If they all say it is a 6, you can place it there. The same applies for situations where you try placing a digit in every place it can go in a certain box/column/row. Or, if placing a digit in a particular place leads to a contradiction, you can eliminate that placement.

A guess, on the other hand, tries a candidate and if it works, accepts it. That will require backtracking if the guess is wrong, and if it's right, will mask the presence of other solutions and therefore a broken puzzle.

[Moschopulus]

I want to assume from the start that we have a valid sudoku puzzle, with only one solution.
Then do you distinguish between guessing and T&E?

I think your post is an example of my point, that different people mean different things when they say guessing and logic and T&E. You didn't assume a unique solution, but I did.

In order to make sense of the previous posts, I would like to know what tso means by "guessing" and "logical solution". I think that most people mean "backtracking" when they say "guessing", but I could be wrong.

[9X9]

If it's any help, my guess / impasse / reguess process envisaged only an option A or B. By extension though, the same kind of process would apply for eg an option A or B or C, with the requirement then that there would need to be two impasses out of the three, and so on.

In other words, there is the expectation that one, and only one, of the options will be a non-impasse.

[lunababy_moonchild]

Can we then define logical placing of a candidate as 'this goes here because .............(insert reason)' - and I don't mean after you've tried 2 or 3 other candidates - and guessing as 'I've got a choice of 2 or 3 candidates so I'll try this one and see what happens' ?

I tend to assume that backtracking is as a result of guessing (how do you do that anyway?). When I'm wrong - to use myself as an example - I'm wrong and I cannot backtrack, puzzle unsolved. Either I try the whole puzzle again (from the beginning) or it remains unsolved.

In answer to the original question : For a puzzle such as Pappocom's or Nikoli's, guessing is unnecessary to solve the puzzle, however, you are welcome to do that if you so choose. *Although some would state that Nishio, which is required for some of Nikoli's harder puzzles, is guessing - and that's where I think that the line gets blurred*

Anyway, I think that this will remain a contentious subject and that it's all down to personal preference. For example, I prefer to solve on paper. I'd probably get further and on harder puzzles if I chose software, but my preference is paper. Do we all have to follow suit? No. Do I miss some of the more advanced solving techniques this way? I don't know! Am I enjoying myself? - given these infuriatingly compulsive and addictive little puzzles - oh, yeah. My father prefers the Pappocom software and freely admits to guessing - with the wrong numbers feature switched on! - and will argue (should I be bothered to indulge him) that it's perfectly legitimate. He also solves (or attempts therein) the Daily Mail puzzles, but comes unstuck more often than not. I think it's laughable myself - and frequently do - but he's happy and the rule of the puzzle says "Fill in the grid so that every row, every column, and every 3x3 box contains the digits 1 through 9. "

The miraculous thing about these puzzles, I think, is that they are so very flexible. Guess or not guess, computer or paper, very easy to extremely hard, Pappacom, Nikoli or anybody else's. All ya have to do is "Fill in the grid so that every row, every column, and every 3x3 box contains the digits 1 through 9. " How hard can it be?

Luna

[9X9]

Readers can obviously be directed there but, to save them the time and energy and with apologies to those already familiar with it, here is what simes.clara.co.uk says about "Trial and Error".

"There are some who would argue trial and error is not a logical technique and is no better than guessing. Although it's not a technique I like to use, I do consider it logical. When further moves seem impossible, trial and error may be the only way forward. Indeed, some puzzles (the ones I eschew.......9X9) cannot be completed without it.

The technique involves selecting one candidate for a cell - without any particular reason for that selection - and then seeing whether the puzzle can then be completed. If it can, well done (although, there could also be other solutions- test the other candidates too.) If not, the trial and error move, and any subsequent moves, are undone and a different choice is made. For some puzzles, it may be necessary to use trial and error several times. For others, it may be required only once.

In order to better manage the complexity it's usual, if possible, to choose a cell with only two candidates but that doesn't have to be the case.

It's worth noting, that this technique alone will always generate a solution if the puzzle can be solved, no other technique can gaurantee that. But, whan used alone, it becomes the equivalent of a brute force attack."

[emm]

All decisions about placing candidates are based on the one rule 'Do Not Repeat any number 1-9 in any row, column or box'.

T&E is a logical technique based on that general rule but without refinements.

Logic refines by providing some useable sub-rules such as the Naked Pair Rule. Despite being defined/refined, however, these logical rules still fall under the overarching 'Do Not Repeat Rule.'

We may eschew T & E or not, but we are all still in the same ballpark - some of us just feel we are on higher gound!

[tso]

There is a difference from *knowing* that a puzzle CAN be solved without guessing/trial and error/backtracking etc and *demonstrating* this in a particular case. I'm saying that each and every one of the grazillion possible 9x9 sudoku's has a logical path from start to finish -- regardless of whether or not you, I or any human or that has ever lived -- can find it.

Let's set that point aside for the moment since so few seem to agree with me about it and there are really no other arguments I can make to convince anyone. Instead, lets stipulate that some puzzles DO require G/T&E/B, etc. These puzzles CANNOT be solved, by flesh or silicone short of a brute force search. Sudoku's can now be put into two groups -- those solveable without brute force search, and those NOT. Remember, those in the second group cannot be solved without brute force regardless of what other tactics and patterns are discovered. If they can, then they were mis-labled to begin with and belong to the first group.

Here's the problem -- given Sudoku "X" (not the diagonal kind -- the unknown kind), how do we decide which group to put it in? Well, we can try to solve it by non-brute force methods. If we are successful, it goes in the first group. If not -- well, we can't be sure *where* it goes, can we? In fact, deciding which group it goes in is more difficult and will take more time than the most protracted brute force search. That second group MUST stay empty and instead, we fill a third group -- the "unknown".

I cannot prove that there is or isn't at least one Sudoku that cannot be solved without a brute force search. Maybe that question is flawed. Maybe the question is whether or not a particular puzzle can be solved with more or less computation time (computer computation, not human) than a brute force search.

As puzzles get more complex, the number of tactics to apply and patterns to look for goes up and the number of times per puzzle any particular tactic or pattern comes up goes down. Taken to the ridiculous extreme would be to name each and every one of the 6 grazillion possible starting grids as a "pattern". All we have to do is identify the pattern and the solution is known -- but searching through this enormous database of "patterns" will take zillions of times longer than a simple brute force search of the puzzle itself. The location of this line, the line between puzzles that can be solved more quickly by looking through a limited database of patterns and applying them and the puzzles that will always be faster to solve by brute force may be a more interesting discussion.

In human terms, it gets more muddled, as we all have solved puzzles by protracted but logical means when we knew that at some point a brute force search would have been quicker.

There are puzzles that I have been unable to solve for years that I eventualy figured out (or tossed). For the longest time, I though solitaire-peg puzzle ...

Code: Select all

      x x x
      x x x
      x x x
x x x x x x x x x
x x x x x x x x x
x x x x x x x x x
      x x x
      x x x
      x x x

Remove one peg to start. Then jump pegs orthoganally, removing the peg jumped over. Goal: Given a specific peg to remove to start and specific hole, end with exactly one peg -- in the chosen hole.



... was beyond the ability of humans, that the only way to find any specific solution was trial and error. Turns out I was wrong. The Conway and Guy book "Winning Ways for your Mathematical Plays" shows in just a few pages a way to break down any peg jumping puzzle and make the impossible only mildly difficult.


I don't think there is a qualitative difference between working on a puzzle that cannot be solved without BFS and one which is merely beyond the solvers ability to solve without BFS. I think the question "Can this puzzle be solved without guessing?" has no meaning. Asking "Is there a puzzle that cannot be solved without guessing" is like asking "Is there a weight that cannot be lifted?" By who and what means? Which puzzles require guessing depends on which person is solving and what tactics are at her disposal -- again, the extreme case being that she has all 6 grazillion starting patterns memorized.

[Myth Jellies]

Put me firmly in Tso's camp; and let me add the following. Pappocom, and others who only serve up Sudoku Lite are actually doing themselves and the Sudoku community a disservice. Why would anyone bother coming up with advanced techniques such as colors, xy-wings, forcing chains, hyper-colors, and pattern overlay methods if it takes nothing more than a naked triple to solve whatever they choose to call an acceptable puzzle? You can look at American network television to see what happens when you cater only to the masses. You eventually end up with night after night of unwatchable trash and wonder what is happening when cable TV takes home all of the Emmys and starts eroding your viewership.

[angusj]

Pappocom, and others who only serve up Sudoku Lite are actually doing themselves and the Sudoku community a disservice.

Well I think a comment like that does Pappocom a disservice. If it wasn't for his passion for Sudoku, we wouldn't be discussing it here today. That Sudoku solving strategies have evolved is because of the interest generated by his programme, not in spite of it.