I meant when you said “And even when I get to a place where I’m stuck, a square might have two different possibilities. I can take one of those possibilities, and either finish the puzzle by if-then logic assuming that possibility, or if-then my way to a contradiction.”. What is “if-thening my way to a contradiction”, if not “deep guess and check”?
The only guess is at “level 0”, so it’s not very deep. Although one might have to jump among a large number of cells to get to the ultimate contradiction, it’s all logical inference from that point on.
I suppose I would say that “deep guess and check” requires multiple copies of the (possible) board state at any given time. This is trivial for a computer. Board states get pushed and popped off a stack easily, and it might spend (relatively) considerable time evaluating a branch of the game tree past a point that a human would have rejected by other means. However, it is guaranteed to find the answer eventually.
I can’t keep any copies of the board state in my head; I have to use the one copy that’s written down and consists of the remaining valid possibilities for each cell. At most, I can test one possibility at a time (you can call this a “guess” if you want, but it’s not much of one), and either reject it or tentatively accept it.
Thank you. I was wondering: Why was the term “counting number” new to me, who is the target audience for the term, and why is the term useful? Per Merriam Webster, the term is “circa 1965”, and per Dictionary.com, 1960-1965. So, new to me because I had stopped studying basic mathematics by then. The target audience seems to be someone for example who can count 2 turtle doves and 1 partridge in a pear tree, but who counts 2 tomatoes and part of another as…3 tomatoes? Per my linked definition, the counting numbers are 1, 2, 3… and do not include 0, fractions, negative numbers, and decimals (and, I assume, irrationals). The “whole numbers” are the counting numbers and 0. Per Wolfram MathWorld™ the web’s most extensive matematics resource:
Aside: The “ketchup” reference was to the joke about the family of three tomatoes who were walking and the little baby tomato was falling behind.
But, I idly wonder: Why has the world, in only the last 50 years, needed the term “counting number”? A child can count “whole” objects (whatever the counter considers to be whole) and a child surely can also count fractions of objects – more likely 1/2 than 15/31, I assume. Hey, kid, just “count” them and tell me how many there are. If the child tells me that there are π pizzas, then I might consider them for “Kids Week Jeopardy!®”. (In any case, I don’t mean to make the thread more appropriate for GQ or IMHO.)
I can’t even begin to grasp the complaints and confusion over the term “counting number.” It’s a simple concept.
An experiment for those of you who are confused about “counting numbers”–ask the nextfive-year-old you see to count to 100. I guarantee you the child will start 123 and not one third, one half, three fourths … That’s why counting numbers.
People seem to get really worked up over the name. Names usually only have at most a passing resemblance to reality, though. What’s real about a real number, or imaginary about an imaginary number? Rational, irrational, natural, and so on… basically all meaningless, and just a label for a specific mathematical object. The set {x | x ∈ ℤ ∧ x ⋝ 1} is useful enough to warrant a name and “counting numbers” is as good as anything.
Ah, OK, when I said “deep” guess-and-check, I meant that you might have to follow the assumption a long way before you notice the contradiction, not that you’d be nesting assumptions. Nesting assumptions is also a perfectly valid logical technique, but it’s very difficult for a human to do, and I’ve never yet seen a puzzle (sudoku or kakaru) where it’s actually necessary.
It’s clearly valid, but as I mentioned previously it’s a rule of Sudoku construction that it should never be required. That’s not to say one couldn’t construct a Sudoku-like puzzle that requires it (and I’ve seen some on the net), but for a “proper” Sudoku it shouldn’t happen.
I don’t know if that’s actually a rule that constructors try to abide by, though. Once you have all the other techniques available, including single-layer guess-and-check, it’d be really hard to make a puzzle that difficult. Though of course, effective use of single-layer guess-and-check depends on a smart choice of the initial guess (you want something that implies a lot, so you can quickly resolve it, but you also want its negation to imply a fair bit, so it’s worth your time).
I am skeptical as anyone else about drawing a sharp formal line between what is “logical reasoning” and what is “guess-and-check”, in the context of solving a particular puzzle. (Of course, if one is considering solution algorithms for an infinite family of puzzles, one might ask for algorithms satisfying a certain complexity bound; regardless, I think of “Respond to puzzle A with solution B” as in itself a perfectly valid rule of logical inference, if solution B is indeed the sole fit to puzzle A.)
(You could, of course, say ahead of time “These 6 particular moves are the only moves you’re allowed to use”, or whatever. Then it’s clear what is meant by claiming that a puzzle could not be completed through use of those moves alone. But there’s no such explicit list of allowed moves for Sudoku, as far as I’m aware; people just have some informal idea in their head of what kinds of moves count as “logical” and what moves (though they comprise logically valid proofs) don’t.)
I’ve also solved a Killer Sudoku puzzle by also assuming the answer was unique. Now I don’t know if that assumption was necessary to solve the puzzle, but at the least it allowed me to solve it quicker than had I not made the assumption.
I found an online Sudoku solver once that used techniques I’d never even thought of, and it could work through a solution one step at a time and the solver would show which technique it was applying and how it excluded certain possibilities.
In fact, the site is here, and it includes links that explain how each technique works. I can do most of their basic strategies in my head, or certain reductions if I make notes of the possible answers for each cell. But there is no way I can do most of their tough (or harder) strategies, even with notes, and I’ve seen very few Sudokus that require them.
So, just because you think trial-and-error is necessary, that doesn’t mean it is. That solver has it as the 35th, and final, solving technique.