Generating sudokus for fun and no profit | Hacker News Reader

Generating sudokus for fun and no profit

tn1ck.com

358 pointstodsacerdoti64 comments

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.

Cracking the cryptic is fantastic. The beauty in the setting of some of their showcased puzzles is truly wonderful to watch get solved.

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.

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.)

Very reminiscent of agadmator and his chess videos, but without the app

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.

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.

https://crackingthecryptic.com/#apps

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.

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.

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.

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.

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.

Such 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/post/on-hats-and-sats/

Thank you and all the others here for the kind words, means a lot:)

And the WASM solver is super cool, definitely useful for generating them as you have to do quite a lot of iterations!

Hey well if you insist, I did find something weird: numpad number entry doesn't work.

Thanks! That's what happens if you only use keyboards without a proper numpad, will fix soon.

Edit: Should be fixed now.

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.

Seems like it's fixed now though, thanks :)

Is there a way to download the problems via an API, or have them available in a file like https://norvig.com/top95.txt?

It would make a great dataset for benchmarking different solver approaches.

Thanks for asking, I made the data that I used for the analysis available as JSON here: https://github.com/TN1ck/tn1ck.com/tree/main/lib/sudoku.

Really love the UI!

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.

Thanks for the feedback, changed the color to orange for the highlight.

Thanks for the quick fix!

Another thing I noticed is that the wrong entry highlight sometimes highlights multiple correct numbers as incorrect and some static numbers will vanish.

Before:

https://ibb.co/Dtk3YXT

After:

https://ibb.co/mvJWC1f

(Also now red and orange are a bit too similar ^^, maybe introduce the color blue?)

Fantastic work. You have many other hidden gems on your site I'd recommend people read too.

This should be an academic paper, great writing.

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.

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_sudo...

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.

The 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

This is very much the approach I use as well (I've been publishing Sudoku for a long time at krazydad).

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!

[1] - https://krazydad.com/kakuro/index.php?sv=13x17I_v1

I 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.

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"

I love the website too! Came here to sing similar praises. What's the stack you're using?

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.

> Website is open source at https://github.com/TN1ck/tn1ck.com.

I had actually looked in your GH and hadn't found this - it 404s when I use this link so the repo may be private

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.

Perhaps there is still something useful in there: https://github.com/stlab/adobe_source_libraries/tree/main/te...

Really 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.

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).

[0]: https://www.sudokuwiki.org/Sudoku_Creation_and_Grading.pdf

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.

Andrew 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

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…

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.

Would 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/...

[1] https://www.conceptispuzzles.com/index.aspx?uri=puzzle/sudok...

[2] https://www.conceptispuzzles.com/index.aspx?uri=mobile/10001...

[3] https://www.conceptispuzzles.com/index.aspx?uri=mobile/10001...

Visualising an algorithm with animations is so attractive for readers, kudos.

Simon 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...

I highly recommend the Brainium sudoku app.

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.

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?

Thank you, it’s fixed now! It was indeed still private.

Thanks :)

Learn Sudoku and Prolog in 8 minutes: https://youtu.be/5KUdEZTu06o?si=WOHkzN_xIT-7HoxZ

I remember the good old days when a bingo card generator was enough to sustain a lifestyle business

I like this open source and privacy friendly app. https://github.com/SecUSo/privacy-friendly-sudoku

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.

I regularly enjoy competing with strangers on the livesudoku website: https://www.livesudoku.com/

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.

1: https://apps.apple.com/us/app/sumaddle/id1552172214

I liked the simplicity of 'About' section of the blog. Nice way of presentation overall.

never seen a blog which is that interactive. great work!

Then you must see https://ciechanow.ski/

Reply on news.ycombinator.com