Answering 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.
And 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.)
Normally 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.
I 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.
Cracking 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.
There’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.
Puzzles 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.
Hi! 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.
I'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 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 ;-)
Your 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.
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.
Great 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.
TIL the G915 doesn't have a proper numpad. Maybe it's some hack to reduce dimensionality for wireless transmission over that proprietary lightspeed protocol thing.
Though the color of the inserted numbers and the highlight color of the current selected number are nearly the same, would be great if they were much more distinct.
Another thing I noticed is that the wrong entry highlight sometimes highlights multiple correct numbers as incorrect and some static numbers will vanish.
The 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.
I 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.
You'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.
I'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.
I 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!
> 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
> 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.
Thank 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/ 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"
Website is open source at 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/, I don't deserve any praise for that.
Oooh thank you! I totally thought it was public - just changed it. Thanks for that. I got confused as I had my old website public already (https://github.com/TN1ck/tomnick.org).
I like the badge idea, though I think a central repo would be nice as well. Need to curate and update obviously.
This would also work for my old idea of a "use this one, Grandma" generator - basically a way to print out (and annotate with instructions) a layout of a remote control, microwave/washer/etc. interface, or anything else that you might need to walk a relative through setting up or using.
Generating 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.
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.
Thanks 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).
Thank 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.
There’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.
Coincidentally, 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?
I 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.
In the article there is a link to one repo https://github.com/TN1ck/sudoku-analysis that returns 404 Not Found from GitHub. Maybe this repo is marked as private?
I 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.
>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.
If 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.
