[HN Gopher] Generating sudokus for fun and no profit
___________________________________________________________________
Generating sudokus for fun and no profit
Author : todsacerdoti
Score : 193 points
Date : 2024-07-24 21:02 UTC (1 days ago)
(HTM) web link (tn1ck.com)
(TXT) w3m dump (tn1ck.com)
| Smaug123 wrote:
| 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.
| 0xFF0123 wrote:
| Cracking the cryptic is fantastic. The beauty in the setting of
| some of their showcased puzzles is truly wonderful to watch get
| solved.
| ziml77 wrote:
| 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.
| Skeime wrote:
| 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.)
| CamelCaseName wrote:
| Very reminiscent of agadmator and his chess videos, but
| without the app
| Phlebsy wrote:
| 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.
| robin_reala wrote:
| 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
| cdingo wrote:
| 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.
| TN1ck wrote:
| 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.
| Yawrehto wrote:
| 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.
| jcynix wrote:
| 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
| ;-)
| alexworks wrote:
| 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.
| nhatcher wrote:
| 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/
| TN1ck wrote:
| 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!
| moffkalast wrote:
| Hey well if you insist, I did find something weird: numpad
| number entry doesn't work.
| TN1ck wrote:
| Thanks! That's what happens if you only use keyboards without
| a proper numpad, will fix soon.
|
| Edit: Should be fixed now.
| ashish01 wrote:
| 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.
| TN1ck wrote:
| 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.
| SushiHippie wrote:
| 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.
| TN1ck wrote:
| Thanks for the feedback, changed the color to orange for the
| highlight.
| SushiHippie wrote:
| 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?)
| MontagFTB wrote:
| 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...
| thih9 wrote:
| 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.
| TN1ck wrote:
| 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"
| nbbaier wrote:
| I love the website too! Came here to sing similar praises.
| What's the stack you're using?
| TN1ck wrote:
| 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.
| nbbaier wrote:
| > 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
| TN1ck wrote:
| 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).
| maicro wrote:
| 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.
| seb1204 wrote:
| I like this open source and privacy friendly app.
| https://github.com/SecUSo/privacy-friendly-sudoku
| ufo wrote:
| 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.
| j7ake wrote:
| Visualising an algorithm with animations is so attractive for
| readers, kudos.
| dhosek wrote:
| There's a part of me that still wants to tackle the question of
| calculating the number of possible Sudoko solutions (i.e., 9x9
| 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 wrote:
| 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.
| darkamaul wrote:
| 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
| TN1ck wrote:
| 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.
| culi wrote:
| 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...
| jmull wrote:
| 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.
| ball_of_lint wrote:
| 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
| krazydad wrote:
| This is very much the approach I use as well (I've been
| publishing Sudoku for a long time at krazydad).
| taeric wrote:
| 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.
| tpurves wrote:
| 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?
| Centigonal wrote:
| 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.
| nevatiaritika wrote:
| I regularly enjoy competing with strangers on the livesudoku
| website: https://www.livesudoku.com/
| msg wrote:
| 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...
___________________________________________________________________
(page generated 2024-07-25 23:03 UTC)