5 ms·

Not the GP, but I think in general the “guess and check” strategy frowned-upon by the Sudoku community. Ideally you should be able to make progress by making so

Not the GP, but I think in general the “guess and check” strategy frowned-upon by the Sudoku community. Ideally you should be able to make progress by making some logical observation (a trivial example: the numbers 1-8 are present in this column, therefore the remaining cell in this column is a 9). Humans can carry this out to complex patterns (the “swordfish” involves looking at 6 cells in 3 different rows/columns and inferring that cells visible to those cannot take on particular values), but it is seems reasonable to say that patterns will reach complexity that humans can’t hold in their heads. Obviously, any such classification would be subjective, but there’s probably a “reasonable” limit to solvability. (Without guess and check)

chongli 4y ago
Obviously, any such classification would be subjective, but there’s probably a “reasonable” limit to solvability. (Without guess and check) It’s totally subjective. Since sudoku is a closed (fixed size grid, fixed number of symbols), guess-and-check is just a catch-all label for logical inference strategies which haven’t been named yet. New strategies are discovered (and named) all the time and one of the ways to do this is to guess and then, if the guess was correct, go back and try to understand why. This bias against guess and check seems to be some deep-seated issue from our culture. I know a lot of mathematics teachers frown on guess-and-check as well and that can rub off on their students, possibly implanting the bias for life. Unfortunately, having this bias can really damage a person’s ability to learn and succeed at mathematics in university. It turns out that guess-and-check makes a triumphant return as a strategy for quickly completing proofs when one is unfamiliar with established theory. Sound familiar? That’s just like sudoku! Working mathematicians, in contrast to poor math teachers at lower levels, have a healthy relationship to the guess-and-check strategy. And that’s good news for them, since they are often working in areas where there is insufficient established theory to make any progress.
- rhdunn 4y ago
  It's all down to whether or not there is any logic to the guess and check strategy. Most of the computer algorithms work by picking a number in the possible values, following the eliminations, and repeating. If they hit an error, they backtrack to the last decision, choose a new number from the set and repeat. If you look at some of the Cracking the Cryptic puzzles on YouTube with "computer" in the title, that covers cases where the computer resorts to a guess and check strategy but where better underlying logic is available in the solve path.
  - chongli 4y ago
    The finite nature of sudoku puzzles guarantees that there is an underlying logic to a given move, whether the solver is aware of it or not. Ultimately, all sudoku strategies are backed by an overriding master logic: "Does this branch of the game tree contain the completed solution or not?" Whether or not humans have come up with a name for a given strategy depends, almost entirely, on the depth of that branch.
    - olliej 4y ago
      No that’s not the case. Having a single solution does not mean that there is a logical path to it. If I have a puzzle where I’m down to a bunch of different options and the only way to make progress is to just try fixing different numbers until the puzzle resolved that not a logical progression , it’s an exhaustive search.
      - 53x15 4y ago
        If the solution is unique then there is a logical path to it, though maybe not one feasible to discover for an agent with bounded time and (especially for humans) bounded working memory. Consider the search tree of a backtracking algorithm operating on a SAT-based representation of a puzzle. A leaf of the tree corresponds to some clause that becomes empty after eliminating literals assigned on the path to that node. If you flip the tree upside down and start from the clauses at the leaves, then two leaves with a common parent represent two clauses with complementary literals that can be resolved upon. So any branch of the algorithm's search tree can be viewed as a tree-structured resolution-refutation proof eliminating some value given a set of prior assignments on the path to the branch, and the tree as a whole can be decomposed into an ordered set of proofs for each elimination in the path to an overall solution. Or, if you prefer, start again from the SAT-based representation and run a prime implicates algorithm like Tison's. Such an algorithm never advances a "guess" or generates a clause that is not entailed. It simply finds one logical consequence after another until it has found all of them, throwing away subsumed clauses along the way until all that's left is the unique solution. Either way you will always produce a path to a solution and proof that the solution is unique using elementary rules of propositional logic that anyone can recognize. That, I think, is what your parent means. Of course, the existence of a proof doesn't mean that a human can find that proof, and that's what we usually mean when we say there's no logical solution. That is, nothing new can be proven by scanning the puzzle looking for pattern matches against a fixed library of known proof templates taken to be the universe of logical techniques, and nothing can be proven from less structured heuristic search within the limits of human working memory and patience.
- Barrin92 4y ago
  guess and check for a human works when the problem space is small enough. You can't guess and check yourself through a 300-move forced mate in chess or some bizarre sudoku before dying of old age. Yeah in theory a human can brute force or guess like a computer, but that's obviously not the point of a meaningful game or problem to solve because it's mindless.
  - lupire 4y ago
    IOW: intelligence is data compression.
    - shagie 4y ago
      Intelligence is the ability to craft a more optimal solution than a brute force approach would take. In the domain of data compression, Kolmogorov complexity https://en.wikipedia.org/wiki/Kolmogorov_complexity https://en.wikipedia.org/wiki/Kolmogorov_complexity is one of the approaches to try to measure that amount.
      - chongli 4y ago
        Guess-and-check is not the same as brute force (nor exhaustive search). No one is sitting there with an empty sudoku grid, filling the whole thing in with guessed numbers, checking to see if the solution is valid, then erasing everything and starting over. Literally no one does that, not even software sudoku solvers (it takes way too long). Guess-and-check is literally just another name for backtracking algorithms. These do not work (for humans) without an adequate suite of rules that can be use to prune the search space.
  - chongli 4y ago
    Nothing about the guess and check strategy implies that you have zero prior information and must guess blindly in an attempt to win the lottery for picking the correct move. Typically, people using guess and check have other principles, rules, or heuristics they use to narrow the search space down to a handful of options. My original point still stands. A cultural bias against guess-and-check is just another way of saying that strategies which determine an exact sequence of moves using only strict deduction from known theory are the only “acceptable” way to play sudoku. That, to me, is highly limiting and absurd. It’s also inefficient because often you’re faced with a choice between two mutually exclusive options and it’s just plain faster and less error-prone to guess and check than it is to carry out all of the deduction in your head before making the correct move.
- kazinator 4y ago
  > New strategies are discovered I highly doubt it. In Sudoku, it is either logically deducible that a particular value is to be placed into a given square. Or else it isn't; one can deduce that one of several values can be placed there, after all other exploration elsewhere has been exhausted. Deducing what can be placed into what square is a simple elimination. If the square is in a row that already has 7, 7 cannot be placed there. If it's in a 3x3 square that has 5, 5 cannot be placed there. If it's in a column that has 4, 4 cannot be placed there. For every square of the Sudoku board, we can do this evaluation. We hit upon a square where all values are eliminated but one, and so that one is confirmed. Based on that confirmation, we can update the other eliminations and keep going. When this process cannot continue, there is no choice but to guess. OK, here we can have a 7 or a 4, and so it goes. I don't see how you can pretend to have some strategies here, let alone ones with pet names and all. People have different systems for tracking the information, to be sure.
  - lgas 4y ago
    Sure, you can always use backtracking to solve any sudoku, but people come up with new, more effective strategies all the time, eg. https://www.youtube.com/watch?v=ZLcey7qiXv8 https://www.youtube.com/watch?v=ZLcey7qiXv8
    - kazinator 4y ago
      What is "more effective" than "solve any"?
deleted 4y ago
[deleted]
wongarsu 4y ago
I think there's some leeway for bifurcation, so "guess and check" when there's only two possibilities. It's not as "clean", but from what I gather it's commonplace in competitive sudoku because in some situations it's the fastest way to find the next digit. But obviously to get to bifurcation you still need to infer enough to narrow a cell down to two choices, so that would still put a limit on solvability.
Someone 4y ago
I would not call what the GP describes as ”guess and check”, but as “backtracking”. That is just making logic observations, using the grid as a memory aid (“let’s see, if foo is a 1 and bar is a 2, then that’s a 7, and then that must be a 4, and that a 3, and then we hit a dead end, so the claim “this is a 1 and this is a 2” in’s true. Maybe foo is a 1 and bar is a 3? No, that’s clearly incorrect. Maybe foo is a 1 and bar is a 4? Etc) I think human Sudoku solving is different, though. Humans don’t do a depth-first search, but a breadth-first one for paths that soon lead to being able to fill in some squares. Experienced solvers probably have heuristics for finding them. I think I would rate the difficulty of a puzzle by the ¿average? depth needed in such a depth-first search to permanently place a new digit in a new cell, with correction factors for the number of paths at that depth that do that and the number of cells to fill in.
- olliej 4y ago
  Generally if a puzzle requires bifurcation it’s considered to be at least partially broken. The setter is expected to have made it so that determining each cell can be done without simply seeing if a choice eventually succeeds. Of course exactly how many steps to count as bifurcation is fairly nebulous.
kazinator 4y ago
> frowned-upon by the Sudoku community {citation-needed} What community, and does it include mathematicians and logicians? Sudoku puzzles that are solvable without guessing must be generated in a way that this is assured. There is also an understanding that Sudoku puzzles should have exactly one solution. It's possible for Sudoku puzzles to have a unique solution, yet be impossible to solve without guessing and backtracking. The process of deduction reaches a point at which it cannot be deduced what value to fill next into what square. It is narrowed down to several possibilities, which have to be pursued in parallel; e.g with backtracking. You follow all the paths, and discard them, returning to the divergent point, whenever a contradiction is reached: violation of the Sudoku constraints. You can't just frown upon some solution method which is inescapable.

chongli 4y ago

Obviously, any such classification would be subjective, but there’s probably a “reasonable” limit to solvability. (Without guess and check) It’s totally subjective. Since sudoku is a closed (fixed size grid, fixed number of symbols), guess-and-check is just a catch-all label for logical inference strategies which haven’t been named yet. New strategies are discovered (and named) all the time and one of the ways to do this is to guess and then, if the guess was correct, go back and try to understand why. This bias against guess and check seems to be some deep-seated issue from our culture. I know a lot of mathematics teachers frown on guess-and-check as well and that can rub off on their students, possibly implanting the bias for life. Unfortunately, having this bias can really damage a person’s ability to learn and succeed at mathematics in university. It turns out that guess-and-check makes a triumphant return as a strategy for quickly completing proofs when one is unfamiliar with established theory. Sound familiar? That’s just like sudoku! Working mathematicians, in contrast to poor math teachers at lower levels, have a healthy relationship to the guess-and-check strategy. And that’s good news for them, since they are often working in areas where there is insufficient established theory to make any progress.

rhdunn 4y ago
It's all down to whether or not there is any logic to the guess and check strategy. Most of the computer algorithms work by picking a number in the possible values, following the eliminations, and repeating. If they hit an error, they backtrack to the last decision, choose a new number from the set and repeat. If you look at some of the Cracking the Cryptic puzzles on YouTube with "computer" in the title, that covers cases where the computer resorts to a guess and check strategy but where better underlying logic is available in the solve path.
- chongli 4y ago
  The finite nature of sudoku puzzles guarantees that there is an underlying logic to a given move, whether the solver is aware of it or not. Ultimately, all sudoku strategies are backed by an overriding master logic: "Does this branch of the game tree contain the completed solution or not?" Whether or not humans have come up with a name for a given strategy depends, almost entirely, on the depth of that branch.
  - olliej 4y ago
    No that’s not the case. Having a single solution does not mean that there is a logical path to it. If I have a puzzle where I’m down to a bunch of different options and the only way to make progress is to just try fixing different numbers until the puzzle resolved that not a logical progression , it’s an exhaustive search.
    - 53x15 4y ago
      If the solution is unique then there is a logical path to it, though maybe not one feasible to discover for an agent with bounded time and (especially for humans) bounded working memory. Consider the search tree of a backtracking algorithm operating on a SAT-based representation of a puzzle. A leaf of the tree corresponds to some clause that becomes empty after eliminating literals assigned on the path to that node. If you flip the tree upside down and start from the clauses at the leaves, then two leaves with a common parent represent two clauses with complementary literals that can be resolved upon. So any branch of the algorithm's search tree can be viewed as a tree-structured resolution-refutation proof eliminating some value given a set of prior assignments on the path to the branch, and the tree as a whole can be decomposed into an ordered set of proofs for each elimination in the path to an overall solution. Or, if you prefer, start again from the SAT-based representation and run a prime implicates algorithm like Tison's. Such an algorithm never advances a "guess" or generates a clause that is not entailed. It simply finds one logical consequence after another until it has found all of them, throwing away subsumed clauses along the way until all that's left is the unique solution. Either way you will always produce a path to a solution and proof that the solution is unique using elementary rules of propositional logic that anyone can recognize. That, I think, is what your parent means. Of course, the existence of a proof doesn't mean that a human can find that proof, and that's what we usually mean when we say there's no logical solution. That is, nothing new can be proven by scanning the puzzle looking for pattern matches against a fixed library of known proof templates taken to be the universe of logical techniques, and nothing can be proven from less structured heuristic search within the limits of human working memory and patience.
Barrin92 4y ago
guess and check for a human works when the problem space is small enough. You can't guess and check yourself through a 300-move forced mate in chess or some bizarre sudoku before dying of old age. Yeah in theory a human can brute force or guess like a computer, but that's obviously not the point of a meaningful game or problem to solve because it's mindless.
- lupire 4y ago
  IOW: intelligence is data compression.
  - shagie 4y ago
    Intelligence is the ability to craft a more optimal solution than a brute force approach would take. In the domain of data compression, Kolmogorov complexity https://en.wikipedia.org/wiki/Kolmogorov_complexity https://en.wikipedia.org/wiki/Kolmogorov_complexity is one of the approaches to try to measure that amount.
    - chongli 4y ago
      Guess-and-check is not the same as brute force (nor exhaustive search). No one is sitting there with an empty sudoku grid, filling the whole thing in with guessed numbers, checking to see if the solution is valid, then erasing everything and starting over. Literally no one does that, not even software sudoku solvers (it takes way too long). Guess-and-check is literally just another name for backtracking algorithms. These do not work (for humans) without an adequate suite of rules that can be use to prune the search space.
- chongli 4y ago
  Nothing about the guess and check strategy implies that you have zero prior information and must guess blindly in an attempt to win the lottery for picking the correct move. Typically, people using guess and check have other principles, rules, or heuristics they use to narrow the search space down to a handful of options. My original point still stands. A cultural bias against guess-and-check is just another way of saying that strategies which determine an exact sequence of moves using only strict deduction from known theory are the only “acceptable” way to play sudoku. That, to me, is highly limiting and absurd. It’s also inefficient because often you’re faced with a choice between two mutually exclusive options and it’s just plain faster and less error-prone to guess and check than it is to carry out all of the deduction in your head before making the correct move.
kazinator 4y ago
> New strategies are discovered I highly doubt it. In Sudoku, it is either logically deducible that a particular value is to be placed into a given square. Or else it isn't; one can deduce that one of several values can be placed there, after all other exploration elsewhere has been exhausted. Deducing what can be placed into what square is a simple elimination. If the square is in a row that already has 7, 7 cannot be placed there. If it's in a 3x3 square that has 5, 5 cannot be placed there. If it's in a column that has 4, 4 cannot be placed there. For every square of the Sudoku board, we can do this evaluation. We hit upon a square where all values are eliminated but one, and so that one is confirmed. Based on that confirmation, we can update the other eliminations and keep going. When this process cannot continue, there is no choice but to guess. OK, here we can have a 7 or a 4, and so it goes. I don't see how you can pretend to have some strategies here, let alone ones with pet names and all. People have different systems for tracking the information, to be sure.
- lgas 4y ago
  Sure, you can always use backtracking to solve any sudoku, but people come up with new, more effective strategies all the time, eg. https://www.youtube.com/watch?v=ZLcey7qiXv8 https://www.youtube.com/watch?v=ZLcey7qiXv8
  - kazinator 4y ago
    What is "more effective" than "solve any"?

deleted 4y ago

[deleted]

wongarsu 4y ago

I think there's some leeway for bifurcation, so "guess and check" when there's only two possibilities. It's not as "clean", but from what I gather it's commonplace in competitive sudoku because in some situations it's the fastest way to find the next digit. But obviously to get to bifurcation you still need to infer enough to narrow a cell down to two choices, so that would still put a limit on solvability.

Someone 4y ago

I would not call what the GP describes as ”guess and check”, but as “backtracking”. That is just making logic observations, using the grid as a memory aid (“let’s see, if foo is a 1 and bar is a 2, then that’s a 7, and then that must be a 4, and that a 3, and then we hit a dead end, so the claim “this is a 1 and this is a 2” in’s true. Maybe foo is a 1 and bar is a 3? No, that’s clearly incorrect. Maybe foo is a 1 and bar is a 4? Etc) I think human Sudoku solving is different, though. Humans don’t do a depth-first search, but a breadth-first one for paths that soon lead to being able to fill in some squares. Experienced solvers probably have heuristics for finding them. I think I would rate the difficulty of a puzzle by the ¿average? depth needed in such a depth-first search to permanently place a new digit in a new cell, with correction factors for the number of paths at that depth that do that and the number of cells to fill in.

olliej 4y ago
Generally if a puzzle requires bifurcation it’s considered to be at least partially broken. The setter is expected to have made it so that determining each cell can be done without simply seeing if a choice eventually succeeds. Of course exactly how many steps to count as bifurcation is fairly nebulous.

kazinator 4y ago

> frowned-upon by the Sudoku community {citation-needed} What community, and does it include mathematicians and logicians? Sudoku puzzles that are solvable without guessing must be generated in a way that this is assured. There is also an understanding that Sudoku puzzles should have exactly one solution. It's possible for Sudoku puzzles to have a unique solution, yet be impossible to solve without guessing and backtracking. The process of deduction reaches a point at which it cannot be deduced what value to fill next into what square. It is narrowed down to several possibilities, which have to be pursued in parallel; e.g with backtracking. You follow all the paths, and discard them, returning to the divergent point, whenever a contradiction is reached: violation of the Sudoku constraints. You can't just frown upon some solution method which is inescapable.