8 ms·
Will We Ever Run Out of Sudoku Puzzles?
- CJefferson 4y agoThis 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 agoNot 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 agoObviously, 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 agoIt'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 agoThe 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 agoA 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 agoThere are lots of Sudokus wuth multiple correct solutions, and no way to differentiate them.
- pwinnski 4y agoThese shouldn't be considered valid sudoku puzzles. Uniqueness is an attribute of valid puzzles.
- pwinnski 4y agoThe 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 agoPuzzles 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 agoGenerally 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 agoI 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 agoThis 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 agoSearch 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 agoNo, 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 agoThen 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 agoWhy? 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 agoIt'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
- tobr 4y ago> Using combinatorics, we can take any one Sudoku grid and, with various simple tricks, create enough unique grids for you to do one each day for the next century. Simply by transposing and rotating the grid or interchanging columns and rows we get exponentially more unique puzzles. You can sort the three columns of boxes in six ways, same for the rows of boxes. Within each column of boxes there are three columns that can be sorted in six ways - same again for the rows. That gives us (6 × 6) × (6 × 6 × 6) × (6 × 6 × 6) = 1 679 616 variations. You can also turn the grid 90 degrees, 1 679 616 × 2 = 3 359 232. Then you can shuffle the order of the nine digits, since they don’t have any mathematical meaning, but are just arbitrary symbols. That’s another 9! = 362 880. 3 359 232 × 362 880 = 1 218 998 108 160 That’s going to keep you busy for more than the next century. In fact, even if you solve one per minute, you’ll be busy for 2.3 million years solving permutations of a single sudoku.
- chongli 4y agoFunny that you bring this up. These puzzles would not be considered distinct within group theory. A simple application of Burnside’s lemma would allow a person to recover the true number of distinct puzzles from this figure. A person playing the same puzzle every day that’s just been rotated or had the symbols permuted is going to quickly get bored. While the puzzle looks superficially different the graph structure and the logical steps in the solution will be identical. So doing this kind of combinatorial shenanigans is “cheating” and should be considered dubious, if not fraudulent, within the sudoku community.
- tobr 4y agoI always thought it would be a fun prank to create a book of sudokus that were all permutations of the same puzzle. See how long it would take for someone to notice that they are solving the same puzzle over and over again.
- Ekaros 4y agoWith or without same symbols? There is 362880 ways to map symbols. That is replace 1 with 9 and so on.
- s1mon 4y agoNo, because once I’ve finished one, it’s not like I’m going to remember the solution a week later.
- mod 4y agoAlso, can't you get more/less difficult puzzles by altering where the clues are, or how many? It would feel like a totally different puzzle.
- OneOneOneOne 4y agoAny good sites for super difficult sudoku?
- mhuffman 4y agoI like these types of Sudokus[0] they can get challenging. Also these guys[1] have some apps[2] with some pretty difficult ones (some classic Sudoku and some with novel rules). Also, if you are a Sudoku fan, you might want to check out kakuro-type games to see if you like those as well. [0]https://puzzlemadness.co.uk/greaterthansudoku/hard/2022/10/7 https://puzzlemadness.co.uk/greaterthansudoku/hard/2022/10/7 [1]https://app.crackingthecryptic.com https://app.crackingthecryptic.com [2]https://crackingthecryptic.com/#apps https://crackingthecryptic.com/#apps [3]https://www.kakuroconquest.com/8x8/expert https://www.kakuroconquest.com/8x8/expert
- shagie 4y agoAre you interested in "pure" sudoku? Or are killer, arrow, thermo and so on clues allowed? There are ones like this - https://app.crackingthecryptic.com/sudoku/6dP4FN27HB https://app.crackingthecryptic.com/sudoku/6dP4FN27HB (solve https://youtu.be/zfIomUELg6c https://youtu.be/zfIomUELg6c ) Normal sudoku rules apply but in the final grid, every clue is wrogn (aka invalid)... Clues are valid if: [Everything is "totally standard" Undar promises...] -Digits in a killer cage sum up to the small clue in the top left of the cage; -Clues outside the grid are correct X-sums. ie Clues show the sum of the first X digits in that direction where X is the 1st digit. - Clues outside the grid are correct skyscraper clues. ie The digits in the grid represent the "heights" of skyscrapers. Clues represent the number of skyscrapers seen from that direction. Taller skyscrapers block shorter ones. -Digits on a thermometer increase from the bulb end -Digits separated by a black dot has a ratio of 1:2 -Digits separated by a white dot are consecutive -Digits separated by X have a sum of 10 -Digits separated by V have a sum of 5 -All digits in a circle appear in the 4 cells touching it -Maximum cells are larger than all 4 adjacent cells That one is just crazy... but solvable. Apparently, there's a new one from just a week ago that is similar in construction - https://youtu.be/JTkvR5M0yFo https://youtu.be/JTkvR5M0yFo (you'll note the 2h long video) Another one https://cracking-the-cryptic.web.app/sudoku/pnf623FF7B https://cracking-the-cryptic.web.app/sudoku/pnf623FF7B (solve https://youtu.be/73iEwlTO_p0 https://youtu.be/73iEwlTO_p0 ) > Normal sudoku rules apply. > Group Sums: A number in a small circle indicates the sum of the digits in the cells covered by the corresponding circle. These digits may or may not repeat. Arrow Sudoku: Digits along an arrow must sum to the number in the corresponding circle. In this Sudoku all group sum clues contain a comparison operator. The clue ≥26 for example indicates a sum of at least 26. An arrow between two cells points to the smaller number. You'll note that I picked a particular channel with the longest videos. The community around that channel has some particularly difficult puzzles especially if you're willing to go beyond "normal Sudoku rules apply."
- somehnacct3757 4y agoA good example of calculable performance vs perceived performance. There's more sudoku puzzles in existence than anyone can memorize, therefore there's infinite sudoku puzzles from a human perspective. From a computer's perspective there is only one sudoku puzzle. Writing a sudoku solver is a college level weekend exercise
- ChicagoBoy11 4y agowhile I was learning lisp I did one as a way to learn the language a bit, and it was absolutely delightful. I feel like this sort of problem lent itself very well to the core features of the language I was trying to learn, so I highly recommend it as an exercise. Peter Norvig also has "his" solution to it in Python on the plane, and it's just remarkable how just looking at it I could tell that there was just a clarity of thinking to that man's code that was something I could only ever hope to emulate some day.
- kmstout 4y agoEarly in the pandemic I cracked my knuckles on writing generator for monster Sudoku [1]; an example can be seen at [2]. I haven't solved a single one of them by hand. [1] https://reindeereffect.github.io/2020/05/05/index.html https://reindeereffect.github.io/2020/05/05/index.html [2] https://reindeereffect.github.io/2020/05/05/images/5x5/new.png https://reindeereffect.github.io/2020/05/05/images/5x5/new.p...
- Penyngton 4y agoI'm surprised not to see any mention of satisfiability here. There are a few papers I've seen about it, but this blog post seems to give a reasonable overview: https://codingnest.com/modern-sat-solvers-fast-neat-underused-part-1-of-n/ https://codingnest.com/modern-sat-solvers-fast-neat-underuse... Then you just need to start counting models, which is the #SAT (sharp SAT) problem: https://en.wikipedia.org/wiki/Sharp-SAT https://en.wikipedia.org/wiki/Sharp-SAT Using software such as: https://github.com/marcthurley/sharpSAT https://github.com/marcthurley/sharpSAT
- SkyMarshal 4y agoI believe we already ran out of sudoku puzzles years ago when Peter Norvig solved them all: https://norvig.com/sudoku.html https://norvig.com/sudoku.html
- cylinder714 4y agoEli Bendersky solving and generating puzzles in Go, which references Norvig: https://eli.thegreenplace.net/2022/sudoku-go-and-webassembly/ https://eli.thegreenplace.net/2022/sudoku-go-and-webassembly...
- egberts1 4y agoTLDR; yes.
- davidpfarrell 4y agoClearly the actual digits used in constructing a standard sudoku puzzle are of absolutely no importance. Transpose some (or all) of the numbers, but leave the exact same shown+hidden squares, and your puzzle has not changed in the slightest. You can replace the digits with dingbat font characters and you would have the exact same puzzle with regards to actually solving the puzzle. So it seems obvious that this conversation comes down to the unique (post symmetry de-dupe) combinations of shown+hidden squares. Additionally, there can be a discussion on which combinations of shown+hidden squares may actually be fun for humans to work on.
- olliej 4y agoNo consideration of the more interestin variant sudokus however