6 ms·

This article is a good example (to me) of presenting a "maths result" as an incorrect fact. The "5,472,730,538" is the number of different (under symmetry) com

This article is a good example (to me) of presenting a "maths result" as an incorrect fact. The "5,472,730,538" is the number of different (under symmetry) completed grids -- so are we saying we could make a (hypothetical) book with 5,472,730,538 completed grids and say "Here is all your Sudoku"? Or, that we are only allowed to create exactly one Sudoku from each finished grid? Neither of those seem like reasonable claims. A more reasonable question would be, how many partially completed sudoku grids are there which have a unique solution. We don't know the answer to that. Even if we did do that, I've done some research on measuring difficulty of Sudoku -- many Sudoku grids are unsolvable by humans -- they are far too hard. A different, and interesting, question would be how many Sudoku are there which can be considered human-solvable. That's an even more open problem (we'd have to exactly define human-solvable to start).

AlbertVAustin 4y ago
> Even if we did do that, I've done some research on measuring difficulty of Sudoku -- many Sudoku grids are unsolvable by humans -- they are far too hard. > A different, and interesting, question would be how many Sudoku are there which can be considered human-solvable. That's an even more open problem (we'd have to exactly define human-solvable to start). What does it mean for a sudoku to be non solvable by human? I wrote a sudoku solver once and thought humans solving harder sudokus is basically exactly what a computer would do: guessing number and trying to solve it further, backtracking on failure. Or do you mean non-human solvable as "it would take a lot of time for a human to solve it"?
- CGamesPlay 4y ago
  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.
- adrianN 4y ago
  A human with sufficient pens and paper available is a (time-constrained) universal Turing machine, so the only Sudokus that aren't solvable by humans are those that take longer than a few decades to solve. In practice, humans don't like spending that much time on solving a single puzzle. And to most humans emulating a Turing machine is also not particularly enjoyable.
  - HideousKojima 4y ago
    There are lots of Sudokus wuth multiple correct solutions, and no way to differentiate them.
    - pwinnski 4y ago
      These shouldn't be considered valid sudoku puzzles. Uniqueness is an attribute of valid puzzles.
- pwinnski 4y ago
  The process you're describing is commonly (and usually derisively) referred to as "bifurcation," because experience solvers will generally only resort to "guessing" when there are only two possible values for a cell. Strategies for solving sudoku puzzles are many and varied, but if a puzzle can only be solved by "guessing a number" rather than logically working out where a number goes or which number goes in a cell, it's probably a pretty bad puzzle.
- plorkyeran 4y ago
  Puzzles which require guessing at any point are generally considered "not solvable". The goal of solving a sudoku puzzle is not actually to get a grid with 81 numbers in it, and trying to progress by guessing defeats the whole point.
- CJefferson 4y ago
  Generally people solve Sudokus in almost the exact opposite way. They do very clever reasoning (much more advanced than basically any computer sudoku solver), but very little, or no, backtracking. This is mainly because backtracking more than 1 or 2 times becomes unreasonable (do you start making hundreds of photocopies of your Sudoku?) The reason computer solvers don't do the advanced reasoning which humans do is it turns out it isn't worth it -- by the time you find and apply the reasoning, you can have done a few million backtracks, which will usually have solved the problem anyway.
- Viliam1234 4y ago
  I once wrote a Sudoku solver using the following algorithm: For each empty field, find which values could possibly be written there (which values are not already written in the same row/column/quadrant). Then it applied the following two rule: (1) If there is only one possible value for a field, write it there. (2) For each row/column/quadrant, for each value: if the value can possibly be written only in one field, write it there. Repeat this in a while loop, finish if you checked the rules and couldn't write anything. No recursion, constant memory usage. I assumed that this would not be enough. I was like "first I will code the obvious thing, then try the algorithm on examples from a book I bought, find the examples this cannot solve, and then think about further rules which could solve those examples". But as I tried it on the puzzles in the book, it solved all of them. Which went against my intuition, as I was pretty sure I sometimes use more complicated rules when solving Sudoku by hand. But it turned out that it is somehow really simply for me to miss an opportunity. This is of course not a proof that each uniquely solvable Sudoku can be solved by this algorithm, but I think that in practice at least 99% of them can be. Then I tried an opposite thing, to use this solver to create puzzles. Like, create a full board, then try removing random numbers and check if the solver can solve this; stop when no number can be removed. This actually created pretty hard puzzles; harder than any example in my book.
  - CJefferson 4y ago
    This is a fun way of solving, but I think your book was fairly simple :) A good way to find hard sudoku, and hard techniques, is "sudokuwiki.org".
  - chopin 4y ago
    Search for 'minimal Sudoku' I think it's 17 given numbers and try those on your solver. I wrote a backtracking solver which tried on the fields with least possibilities first. It needed considerable time for these puzzles.
Anon_troll 4y ago
> A more reasonable question would be, how many partially completed sudoku grids are there which have a unique solution. We don't know the answer to that. If you interpret "unique" to mean that two puzzles that lead to the same solution count as one, the answer would be equal to the number of completed grids. Just remove one number and you get a partially completed grid, and there cannot be more. The interpretation you mean is probably how many partially completed sudoku grids have only a single solution instead of multiple, which leads to a much more interesting question.
- Karellen 4y ago
  No, in Sudoku, the constraint of a "unique solution" is that a valid puzzle (i.e. an incomplete grid) must only have one correct way of being filled in without violating the rules. If there are two possible ways of filling the grid without violating the rules, the puzzle does not have a unique solution. It has nothing to do with whether then solution to one puzzle (starting grid) happens to be the same as the solution to a different puzzle (starting grid).
  - dougSF70 4y ago
    Then the maximum number of solveable puzzles must be the maximum number of unique grids...since you remove grid entries to make the puzzle and if you remove entries with the constraint that the puzzle remains solveable with a single solution etc etc
    - rpadovani 4y ago
      Why? If I have a complete grid, I can remove the top left number, and that's a puzzle. Or, I can remove the bottom right number, and that's another puzzle. So, one unique grid can be the solution to multiple puzzles.
      - Wowfunhappy 4y ago
        > Why? Because we said so earlier in this thread. >> If you interpret "unique" to mean that two puzzles that lead to the same solution count as one
Akronymus 4y ago
It's also not considering variant sudokus.
53x15 4y ago
> A more reasonable question would be, how many partially completed sudoku grids are there which have a unique solution. We don't know the answer to that. The number of minimal Sudoku puzzles is estimated (with 0.065% relative error) to be 3.1055e+37 (or 2.5477e+25 for non-isomorphic minimal puzzles). See Bethier https://arxiv.org/pdf/1111.4083.pdf https://arxiv.org/pdf/1111.4083.pdf

AlbertVAustin 4y ago

> Even if we did do that, I've done some research on measuring difficulty of Sudoku -- many Sudoku grids are unsolvable by humans -- they are far too hard. > A different, and interesting, question would be how many Sudoku are there which can be considered human-solvable. That's an even more open problem (we'd have to exactly define human-solvable to start). What does it mean for a sudoku to be non solvable by human? I wrote a sudoku solver once and thought humans solving harder sudokus is basically exactly what a computer would do: guessing number and trying to solve it further, backtracking on failure. Or do you mean non-human solvable as "it would take a lot of time for a human to solve it"?

CGamesPlay 4y ago
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.
adrianN 4y ago
A human with sufficient pens and paper available is a (time-constrained) universal Turing machine, so the only Sudokus that aren't solvable by humans are those that take longer than a few decades to solve. In practice, humans don't like spending that much time on solving a single puzzle. And to most humans emulating a Turing machine is also not particularly enjoyable.
- HideousKojima 4y ago
  There are lots of Sudokus wuth multiple correct solutions, and no way to differentiate them.
  - pwinnski 4y ago
    These shouldn't be considered valid sudoku puzzles. Uniqueness is an attribute of valid puzzles.
pwinnski 4y ago
The process you're describing is commonly (and usually derisively) referred to as "bifurcation," because experience solvers will generally only resort to "guessing" when there are only two possible values for a cell. Strategies for solving sudoku puzzles are many and varied, but if a puzzle can only be solved by "guessing a number" rather than logically working out where a number goes or which number goes in a cell, it's probably a pretty bad puzzle.
plorkyeran 4y ago
Puzzles which require guessing at any point are generally considered "not solvable". The goal of solving a sudoku puzzle is not actually to get a grid with 81 numbers in it, and trying to progress by guessing defeats the whole point.
CJefferson 4y ago
Generally people solve Sudokus in almost the exact opposite way. They do very clever reasoning (much more advanced than basically any computer sudoku solver), but very little, or no, backtracking. This is mainly because backtracking more than 1 or 2 times becomes unreasonable (do you start making hundreds of photocopies of your Sudoku?) The reason computer solvers don't do the advanced reasoning which humans do is it turns out it isn't worth it -- by the time you find and apply the reasoning, you can have done a few million backtracks, which will usually have solved the problem anyway.
Viliam1234 4y ago
I once wrote a Sudoku solver using the following algorithm: For each empty field, find which values could possibly be written there (which values are not already written in the same row/column/quadrant). Then it applied the following two rule: (1) If there is only one possible value for a field, write it there. (2) For each row/column/quadrant, for each value: if the value can possibly be written only in one field, write it there. Repeat this in a while loop, finish if you checked the rules and couldn't write anything. No recursion, constant memory usage. I assumed that this would not be enough. I was like "first I will code the obvious thing, then try the algorithm on examples from a book I bought, find the examples this cannot solve, and then think about further rules which could solve those examples". But as I tried it on the puzzles in the book, it solved all of them. Which went against my intuition, as I was pretty sure I sometimes use more complicated rules when solving Sudoku by hand. But it turned out that it is somehow really simply for me to miss an opportunity. This is of course not a proof that each uniquely solvable Sudoku can be solved by this algorithm, but I think that in practice at least 99% of them can be. Then I tried an opposite thing, to use this solver to create puzzles. Like, create a full board, then try removing random numbers and check if the solver can solve this; stop when no number can be removed. This actually created pretty hard puzzles; harder than any example in my book.
- CJefferson 4y ago
  This is a fun way of solving, but I think your book was fairly simple :) A good way to find hard sudoku, and hard techniques, is "sudokuwiki.org".
- chopin 4y ago
  Search for 'minimal Sudoku' I think it's 17 given numbers and try those on your solver. I wrote a backtracking solver which tried on the fields with least possibilities first. It needed considerable time for these puzzles.

Anon_troll 4y ago

> A more reasonable question would be, how many partially completed sudoku grids are there which have a unique solution. We don't know the answer to that. If you interpret "unique" to mean that two puzzles that lead to the same solution count as one, the answer would be equal to the number of completed grids. Just remove one number and you get a partially completed grid, and there cannot be more. The interpretation you mean is probably how many partially completed sudoku grids have only a single solution instead of multiple, which leads to a much more interesting question.

Karellen 4y ago
No, in Sudoku, the constraint of a "unique solution" is that a valid puzzle (i.e. an incomplete grid) must only have one correct way of being filled in without violating the rules. If there are two possible ways of filling the grid without violating the rules, the puzzle does not have a unique solution. It has nothing to do with whether then solution to one puzzle (starting grid) happens to be the same as the solution to a different puzzle (starting grid).
- dougSF70 4y ago
  Then the maximum number of solveable puzzles must be the maximum number of unique grids...since you remove grid entries to make the puzzle and if you remove entries with the constraint that the puzzle remains solveable with a single solution etc etc
  - rpadovani 4y ago
    Why? If I have a complete grid, I can remove the top left number, and that's a puzzle. Or, I can remove the bottom right number, and that's another puzzle. So, one unique grid can be the solution to multiple puzzles.
    - Wowfunhappy 4y ago
      > Why? Because we said so earlier in this thread. >> If you interpret "unique" to mean that two puzzles that lead to the same solution count as one

Akronymus 4y ago

It's also not considering variant sudokus.

53x15 4y ago

> A more reasonable question would be, how many partially completed sudoku grids are there which have a unique solution. We don't know the answer to that. The number of minimal Sudoku puzzles is estimated (with 0.065% relative error) to be 3.1055e+37 (or 2.5477e+25 for non-isomorphic minimal puzzles). See Bethier https://arxiv.org/pdf/1111.4083.pdf https://arxiv.org/pdf/1111.4083.pdf