Generating sudokus for fun and no profit

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.

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.

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.

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 like this open source and privacy friendly app. https://github.com/SecUSo/privacy-friendly-sudoku

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.

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

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?

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?

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

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

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

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.

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

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

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.

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

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

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

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