6 ms·
Generating sudokus for fun and no profit
- Smaug123 2y agoAnswering the object-level problem "my grandma wanted to play some sudokus on her computer", I really enjoyed the Cracking the Cryptic-affiliated game "Classic Sudoku", which is available on Steam, although some of the puzzles are really hard. The puzzles are all handmade, and many of them have some specific reason to exist: e.g. there's at least one which is clearly intended to teach you the swordfish pattern, and there are a few which appear to be built around some beautiful one-off ideas.
- 0xFF0123 2y agoCracking the cryptic is fantastic. The beauty in the setting of some of their showcased puzzles is truly wonderful to watch get solved.
- ziml77 2y agoI love the feeling of finding the beauty of how a puzzle resolves. The hand set puzzles are as much a challenge to player as they are a demonstration of the setter's own skill and cleverness.
- Skeime 2y agoAnd it is such a fantastic resource to learn! You want to get into puzzles like they do on the channel? Just open a video, pause it, and click the link in the description. Stare at the puzzle, trying to figure it out. The first time you do this, you probably won't. Once you lose patience (but give yourself some time!), watch the video until Simon or Mark get to the first deduction and explain it. Pause the video again, and try to continue using your new knowledge. When you get stuck again, what (or skim) through the video until they do enter a deduction that you have not found. Rinse and repeat. Do this a couple of times with different videos, and you will start to build a repertoire of techniques yourself. At some point, you will be capable of solving puzzles on your own. (And if you get stuck, the video is there to help you.)
- CamelCaseName 2y agoVery reminiscent of agadmator and his chess videos, but without the app
- Phlebsy 2y agoNormally I get a bit tired or skip ahead when technical topics or gameplay centered strategies are explained over and over again on the same channel, but I can watch them prove the Phistomefel ring or break down the logic on disqualifying candidates with their shaders every time.
- robin_reala 2y agoThere’s also the self-titled “Cracking the Cryptic” app that has a bunch of handmade Sudoku & friends puzzles that range in difficulty from pretty tricky up to fiendish. https://crackingthecryptic.com/#apps https://crackingthecryptic.com/#apps
- cdingo 2y agoCracking The Cryptic also has a "Genuinely Approachable Sudoku" community (Discord is the only public feed I'm aware of), where a handmade puzzle using all sorts of Sudoku variants is posted daily.
- wruza 2y agoPuzzles featured on their channel are usually too hard for me. Not all, but I spend 5-10x more time than regulars and get stuck often. So I solve these with Simon in a parallel tab (there’s a playable pink under every video). Sometimes I yell at him because he solves it in a very complex way when there was a sudoku move available.
- TN1ck 2y agoHi! I'm the author, didn't expect this to be posted here yet. I was still somewhat working on it, so please bear with me when you find anything weird. You can give me any feedback here.
- Yawrehto 2y agoGreat article, no comments. I know the angry/dissatisfied people tend to give lots of feedback, but I really enjoyed your article and playing around with it.
- jcynix 2y agoI'll second that: great article and description of the problem space. Love it. Once upon a time I programmed a solution finder for the game https://en.wikipedia.org/wiki/Ricochet_Robots https://en.wikipedia.org/wiki/Ricochet_Robots because a gaming magazine had monthly problems to solve. But I wasn't allowed to run my program until my wife found a solution manually first ;-)
- alexworks 2y agoYour article is fantastic. I really like the way you present information, especially with the interactive examples. I've been playing a lot with the logic programming language, Prolog. Sudoku is a popular "hello world" for it. If you haven't used Prolog before, here's an example of a Sudoku solver. It uses Prolog's Constraint Logic Programming over Finite Domains library -- CLP(FD) -- a form of CSP. https://swish.swi-prolog.org/example/clpfd_sudoku.pl https://swish.swi-prolog.org/example/clpfd_sudoku.pl The relation on line 8 basically encodes the rules of Sudoku verbatim. Logic programming is cool (at least to me) because relations can be run in any direction with any number of variables. I wonder how writing a Sudoku puzzle generator would differ in a language that had first-class support for CSP.
- nhatcher 2y agoSuch a beautifully written blog! I have no comments so far, but I will read it through tonight again. I wrote a Sudoku solver using a SAT solver compiled to wasm (it is just a simple exercise TBH): https://www.nhatcher.com/hats/sudoku.html https://www.nhatcher.com/hats/sudoku.html https://www.nhatcher.com/post/on-hats-and-sats/ https://www.nhatcher.com/post/on-hats-and-sats/
- MontagFTB 2y agoGenerating Sudokus is a fond area of computing for me. Great job; the website is very thorough and readable. Many years ago I wrote a Sudoku generator in C++ that was based on Knuth’s “dancing links” algorithm. It then analyzed the generated puzzle in terms of what techniques were necessary to solve it, and ranked them accordingly. Perhaps there is still something useful in there: https://github.com/stlab/adobe_source_libraries/tree/main/test/sudoku https://github.com/stlab/adobe_source_libraries/tree/main/te...
- thih9 2y agoI love the first sentence, peak hacking spirit. > Once upon a time I decided to create a complete sudoku application as my grandma wanted to play some sudokus on her computer and I wasn't satisfied with the free offers available. I liked the rest too and the website as well, especially the user friendly UX - the "applets" can be paused, the website has all kinds of display options, there are keyboard shortcuts and support for arrow keys. My dream would be a "made for grandma" embeddable badge - and websites like this becoming a trend in 2024.
- TN1ck 2y agoThank you! Definitely went on a lot of hacker side quests with this project and the article. And makes me happy you like the applets. I really like creating interactive articles, they can help so much with understanding, https://ciechanow.ski/ https://ciechanow.ski/ articles are the perfect example of this. It's crazy how easier something becomes to grasp if you can play around with it. Haha, the badge idea is definitely cool! I do fear for my less technical relatives becoming a target of a predatory app that should be free. Would be nice to quickly find good solutions. My trick is normally to search for "github" and find some random programmers project that is free of any monetization strategy e.g. "memory matching github"
- nbbaier 2y agoI love the website too! Came here to sing similar praises. What's the stack you're using?
- TN1ck 2y agoWebsite is open source at https://github.com/TN1ck/tn1ck.com https://github.com/TN1ck/tn1ck.com. Tech stack is literally just a Next.js website and I write my articles in React. I tried other things before e.g. Jekyll, but I found that dynamic content is really hard to do there, annoyingly hard. I keep it super simple and don't do "the proper way" of things at times (e.g. the blog index is manually done by me). But that keeps it simple & independent to me. Next.js here is just a detail, I can always move to some other React-based static site generator. It's hosted at Cloudflare. The design is heavily inspired by https://turbopuffer.com/ https://turbopuffer.com/, I don't deserve any praise for that.
- seb1204 2y agoI like this open source and privacy friendly app. https://github.com/SecUSo/privacy-friendly-sudoku https://github.com/SecUSo/privacy-friendly-sudoku
- ufo 2y agoI like this app but I'm not completely satisfied with its generation algorithm. The penultimate difficulty (Hard) is too easy. And the top difficulty (Challenge) always requires guessing/backtracking. But to me backtracking feels more like busywork and less like a fun puzzle. I wish there was an in-between that had more challenging puzzles but without any guesswork.
- Suppafly 2y ago>And the top difficulty (Challenge) always requires guessing/backtracking. That's sorta where I am with sudoku, up to a certain difficulty they are fun and challenging, after that it's just brute forcing and crossing off numbers and not fun. I think some of the better deduction techniques can come into play on the harder ones, but I haven't taught myself any of them.
- j7ake 2y agoVisualising an algorithm with animations is so attractive for readers, kudos.
- dhosek 2y agoThere’s a part of me that still wants to tackle the question of calculating the number of possible Sudoko solutions (i.e., 9×9 grids that meet the constraints for a Sudoko) analytically rather than by brute force (which is how the number is currently calculated). Back in my grad school days (which also corresponded to the height of the Sudoko craze), I got a start on it, but got lost in the weeds pretty quickly. Maybe I should give it another try.
- lisper 2y agoI highly recommend the Brainium sudoku app. https://brainium.com/games/sudoku/ https://brainium.com/games/sudoku/ It has selectable difficulty and a "hint" mode that teaches you how to solve even the hardest sudokus without any backtracking search at all.
- darkamaul 2y agoThanks a lot for your website - that was refreshing to see. While I like the idea of using ARC3 to grade sudoku, I much prefer the approach developed by Andrew C. Stuart in [0], where they rely on the human techniques* needed to solve the sudoku. Indeed, Sudoku are small enough that a reasonable greedy algorithm is enough to solve them quasi instantly on modern hardware. * techniques to solve the sudoku that can be applied by an human (as opposed to a computer). [0]: https://www.sudokuwiki.org/Sudoku_Creation_and_Grading.pdf https://www.sudokuwiki.org/Sudoku_Creation_and_Grading.pdf
- TN1ck 2y agoThank you, the article is really interesting - do you know if any popular app uses this grading system? Would be nice to test how it compares. I did feel like ACRC3 is a bit closer to how a human solves it, but it's still a backtracking algorithm at its core and looking at the analysis, it's not _really_ different than a simple brute force in terms of its rating.
- dahart 2y agoAndrew Stuart’s app is extremely popular and uses that algorithm. His solver is truly amazing and in a class of it’s own. https://www.sudokuwiki.org/sudoku.htm https://www.sudokuwiki.org/sudoku.htm This site is the place where I learned how deep sudoku goes. I was rather naive before I read about the X-wing, Jellyfish, Medusa, and Death Blossom…
- culi 2y agoWould love to see variants next. There's sudokus of different sizes,[0] irregular sudoku,[1] multisudoku,[2] sumsudoku[3] and many many more [0] https://www.conceptispuzzles.com/index.aspx?uri=puzzle/euid/0100000059a2f1f7277d69d841a889b06b60b9ad283a2de467777def822f009ec9749f8d424af7b40b36fa84563a0a6286aae6ee/play https://www.conceptispuzzles.com/index.aspx?uri=puzzle/euid/... [1] https://www.conceptispuzzles.com/index.aspx?uri=puzzle/sudoku/rules https://www.conceptispuzzles.com/index.aspx?uri=puzzle/sudok... [2] https://www.conceptispuzzles.com/index.aspx?uri=mobile/100012 https://www.conceptispuzzles.com/index.aspx?uri=mobile/10001... [3] https://www.conceptispuzzles.com/index.aspx?uri=mobile/100015 https://www.conceptispuzzles.com/index.aspx?uri=mobile/10001...
- jmull 2y agoI've found the best way to rate and generate puzzles of a certain perceived difficulty is to have a solver that works the way a human does. So if you have a puzzle that can be solved using only techniques that interested people can come up with fairly readily/intuitively and apply without a lot of ceremony, then that would be, perhaps, very easy. The more advanced techniques (for humans) needed to solve the puzzle, the harder it would be rated. You can also feed these techniques into the generation so that you can guide the difficulty as it's being generated (the way I did it, I found it would still fall into puzzles that are easier than the target, or get stuck on puzzles that are too hard, but applying adjustments to backtracking and forward progress based on heuristics observed in "stuck" scenarios seemed to do the trick.
- ball_of_lint 2y agoThe author calls this out specifically: > and this makes the whole analysis problematic, as we still don't know if this is actually a good difficulty indicator for how a human perceives the difficulty
- krazydad 2y agoThis is very much the approach I use as well (I've been publishing Sudoku for a long time at krazydad).
- foofoo55 2y agoI often ponder what the generator algorithm might be when I am solving "insane" 13x17 Kakuro puzzles [1], because there always seems to be just enough logical paths to solve each puzzle. Well done! [1] - https://krazydad.com/kakuro/index.php?sv=13x17I_v1 https://krazydad.com/kakuro/index.php?sv=13x17I_v1
- taeric 2y agoReally fun visualizations. Well done! I am a broken record on posts that mention sudoku in bringing in Knuth's treatment of it. He has a ton of really fun exercises on the game in the latest volume. Perhaps the most fun are the puzzles that have a single solution, but do not have enough information to place a single piece without ambiguity.
- tpurves 2y agoCoincidentally, while trying to get my daughter to sleep last night, I watched her solve a lengthy sudoko on my phone, while my own brain couldn't help to wander to imagining all the possible solver algorithms that might be out there. Or how I'd ever do in a technical interview if anyone asked me design one on the spot. I got at least as far as thinking through something like your list of algorithms here. But I could help but imaging that there must also be even-more efficient or interestingly exotic solutions out there. Like something amusing as a rainbow-table type approach where you calculate all the possible soduko boards in advance, then (somehow?) convert any given puzzle into just an index lookup of a matching solution. So like (perhaps a lot of) brute force up front, but O(1) in execution?
- Centigonal 2y agoI highly recommend writing a sudoku solver without looking at any solutions online beforehand. I ended up writing something that looks like Arc consistency but sloppier without knowing about it, and I found the process fun, challenging, but not too challenging. IMO it's probably too time consuming for a technical interview question.
- nevatiaritika 2y agoI regularly enjoy competing with strangers on the livesudoku website: https://www.livesudoku.com/ https://www.livesudoku.com/
- msg 2y agoSimon Tatham's Portable Puzzle Collection has a Sudoku generator called Solo. On web, desktop, and mobile for free. https://www.chiark.greenend.org.uk/~sgtatham/puzzles/js/solo.html https://www.chiark.greenend.org.uk/~sgtatham/puzzles/js/solo...
- chris_st 2y agoIf you like solving sudokus, and I'd be a bit surprised if you're here and don't :-), you might want try the app "Sumaddle" [1] available on (at least) iOS. It's a different kind of puzzle, but a very similar "get to a point where you can't figure out how to go forward, then realize there's a clever inference available" vibe. 1: https://apps.apple.com/us/app/sumaddle/id1552172214 https://apps.apple.com/us/app/sumaddle/id1552172214
- nanidin 2y agoI remember the good old days when a bingo card generator was enough to sustain a lifestyle business
- lifebeyondfife 2y agoThe exponential number of symmetries present in sudoku problems, means that once you've found one valid instance, you've actually found up to 9! * 3!^4 * 8 which are exactly the same. The numbers themselves are all interchangeable, so you have 9! combinations: 362,880. Columns 1-to-3 are all interchangeable, as are 4-to-6, and 7-to-9. On top of this, these blocks of columns (1-to-3, 4-to-6, 7-to-9) are all interchangeable. Read about wreath products in group theory to know more. Each of the above symmetries are 3!, combined to yield 3! * 3! = 36 combinations. As well as the columns though, the rows have the same property, so those can be combined too: 36 * 36 = 1,296. Finally, there are the symmetries of a square. Combining all rotations and flips yields a further 8. In total, sudoku has 3,762,339,840 symmetries. Owing to the starting state of the sudoku puzzle being incomplete, the orbit of the set of points (more group theory) will be smaller than 3 billion, but it provides an efficient method of recreating many more puzzles with the same property. In this case, human complexity.
- xjm 2y agoI counted one trillion or 9! * 3!^8 * 2 : the 8 because you have can choose 3 independent permutations of columns inside column blocks + 1 permutation of column blocks, plus same for rows. Then only one rotation should be counted, because flips are included in col/row permutations. I think wreath products relate to the second sentence; see this page, which mentions the same result: https://en.wikipedia.org/wiki/Mathematics_of_Sudoku#The_sudoku_symmetry_group https://en.wikipedia.org/wiki/Mathematics_of_Sudoku#The_sudo...
- lifebeyondfife 2y agoYou're correct, the horizontal and vertical flips for the square, are already accounted for in the wreath product. And I miscounted the products themselves. Up to 1.2*10^12 symmetries.
- roshankhan28 2y agonever seen a blog which is that interactive. great work!
- efilife 2y agoThen you must see https://ciechanow.ski/ https://ciechanow.ski/
- timonoko 2y agoLearn Sudoku and Prolog in 8 minutes: https://youtu.be/5KUdEZTu06o?si=WOHkzN_xIT-7HoxZ https://youtu.be/5KUdEZTu06o?si=WOHkzN_xIT-7HoxZ
- codetrotter 2y agoIn the article there is a link to one repo https://github.com/TN1ck/sudoku-analysis https://github.com/TN1ck/sudoku-analysis that returns 404 Not Found from GitHub. Maybe this repo is marked as private?
- TN1ck 2y agoThank you, it’s fixed now! It was indeed still private.
- codetrotter 2y agoThanks :)
- the_arun 2y agoI liked the simplicity of 'About' section of the blog. Nice way of presentation overall.
- mknux 2y ago[dead]