（评论）

（评论）
(comments)

原始链接: https://news.ycombinator.com/item?id=41062072

由于其对称结构，数独问题拥有许多相同的解决方案。找到单个解决方案会导致定位多个实例，最多为 9 阶乘乘以 3 的 4 阶乘乘以 8。这是因为每行或每列中的数字可以交换，而不会改变谜题的解决方案。此外，三列的集合（例如列 1-3、4-6 和 7-9）可以相互交换，从而产生额外的 3 个阶乘平方的可能性。通过“花圈积”探索群论可以更深入地理解这些模式。每组互换的列或行的可能对称数量总计为 3 个阶乘组合，从而产生 36 种独特的配置。行也具有这一特征，与现有排列配对时会产生另外 36 种可能性。考虑到正方形的标准 9 种对称性（包括旋转和反射），我们得出数独谜题的大约 370 万种不同对称性。尽管起始配置可能存在缺失的部分，但使用对称性有助于生成大量新的谜题，同时保持原始的挑战级别，即“人类复杂性”。

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.

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.

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.

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.

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!

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.

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.

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.

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

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

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"

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.

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.

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.

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.

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.

（评论） (comments)

（评论）
(comments)