Generating sudokus for fun and no profit
July 26, 2024 4:58 AM Subscribe
Generating sudokus for fun and no profit – 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. The project went on for some years and finally led to sudoku.tn1ck.com - a free and open source Sudoku app without any tracking. While working on it, I went down the rabbit hole of generating Sudokus of a specified "human perceived" difficulty and accidentally created a quite thorough analysis of it...
The explanations lost me about halfway through, but getting to see the solver in action was very fun! And...I honestly didn't realize how much work went into making these things.
posted by mittens at 7:17 AM on July 26, 2024
posted by mittens at 7:17 AM on July 26, 2024
I went down that route once but gave up when the variants of some patterns got out of hand. Kudos to them for finishing the job.
posted by Tell Me No Lies at 7:24 AM on July 26, 2024
posted by Tell Me No Lies at 7:24 AM on July 26, 2024
I love how the analysis page begins with "Once upon a time... my grandma wanted to play some Sudokus..." Now, look what you made me do!
It's funny how Sudoko has all sorts of out-there connections... to grandmas, to theoretical computer science, to physics, to neuroscience, to biochemistry...
To computational complexity: generalized to larger grids, it is NP-HARD.
To the physics of phase transitions: "Via an exact mapping of Sudoku into a deterministic, continuous-time dynamical system, here we show that the difficulty of Sudoku translates into transient chaotic behavior exhibited by the dynamical system."
To neuroscience: "The memory model and a related computational network for solving Sudoku puzzles produce answers that contain implicit check bits in the representation of information across neurons, allowing a rapid evaluation of whether the putative answer is correct or incorrect through a computation related to visual pop-out."
To chemistry: "Can a cell solve Sudoku? While few would take seriously the prospect of whether an individual E. coli could beat the puzzle page of the Daily Mail, this question of principle has significant implications... So our real question is whether 1 cubic micron of biochemistry could efficiently implement the kinds of algorithms necessary to solve difficult problems like Sudoku, and if so, how?"
Disclosure: that last one documents my own descent into the rabbit hole of Sudoku... madness, madness...
posted by brambleboy at 8:33 AM on July 26, 2024 [1 favorite]
It's funny how Sudoko has all sorts of out-there connections... to grandmas, to theoretical computer science, to physics, to neuroscience, to biochemistry...
To computational complexity: generalized to larger grids, it is NP-HARD.
To the physics of phase transitions: "Via an exact mapping of Sudoku into a deterministic, continuous-time dynamical system, here we show that the difficulty of Sudoku translates into transient chaotic behavior exhibited by the dynamical system."
To neuroscience: "The memory model and a related computational network for solving Sudoku puzzles produce answers that contain implicit check bits in the representation of information across neurons, allowing a rapid evaluation of whether the putative answer is correct or incorrect through a computation related to visual pop-out."
To chemistry: "Can a cell solve Sudoku? While few would take seriously the prospect of whether an individual E. coli could beat the puzzle page of the Daily Mail, this question of principle has significant implications... So our real question is whether 1 cubic micron of biochemistry could efficiently implement the kinds of algorithms necessary to solve difficult problems like Sudoku, and if so, how?"
Disclosure: that last one documents my own descent into the rabbit hole of Sudoku... madness, madness...
posted by brambleboy at 8:33 AM on July 26, 2024 [1 favorite]
This is great! My one dashed hope was that it was going to dig a bit more into the sub-tasks a human player would go through mentally in evaluating options in a puzzle or reasoning through tricky spots.
That it attempts to capture the human instinct of "look for the most constrained cells to work on" does a good job of emulating the most obvious (and very effective!) search strategy—people aren't likely to do a rote raster scan of the grid as their primary strategy, but rather look for crowded boxes and almost-full rows and columns to work on. But beyond that, a human working a puzzle is going to deploy a variety of small rubrics, in more or less increasing order of cognitive difficulty, and an analysis of a solution that tracks how far down that set of rubrics a person needs to go before getting a new cell would be a really appealing approach to judging difficulty in a more naturalistic way. Instead of just raw number of iterations, it could measure the sum of each iteration/step * the associated weight of the technique that was required for that step of progress. The big inferential "a ha!" moment that comes from realizing how three different ambiguous cells contribute to certainty about one represents a degree of corralling of technique and short term memory that is worth noting more explicitly!
In that sense puzzles might also be rated into buckets by which specific techniques are required to make progress; a puzzle that surrenders to only simple inferential rules, even if it requires more digits to be filled in in total, will be accessible to all players; a puzzle that requires some more complicated inferences based on dependencies between cells will only be accessible to folks who have internalized those techniques; and so on up to some of the most devilish wide-spread dependencies that the hardest puzzles require analysis of. This sort of ranking would still no doubt correlate pretty well to the more general approach in the write-up here, but I think it would be more telling about the kinds of challenges different cohorts would be up to in a way that captures the plateaus and sudden leaps players experience in puzzle solvability as they internalize new techniques.
posted by cortex at 9:36 AM on July 26, 2024 [3 favorites]
That it attempts to capture the human instinct of "look for the most constrained cells to work on" does a good job of emulating the most obvious (and very effective!) search strategy—people aren't likely to do a rote raster scan of the grid as their primary strategy, but rather look for crowded boxes and almost-full rows and columns to work on. But beyond that, a human working a puzzle is going to deploy a variety of small rubrics, in more or less increasing order of cognitive difficulty, and an analysis of a solution that tracks how far down that set of rubrics a person needs to go before getting a new cell would be a really appealing approach to judging difficulty in a more naturalistic way. Instead of just raw number of iterations, it could measure the sum of each iteration/step * the associated weight of the technique that was required for that step of progress. The big inferential "a ha!" moment that comes from realizing how three different ambiguous cells contribute to certainty about one represents a degree of corralling of technique and short term memory that is worth noting more explicitly!
In that sense puzzles might also be rated into buckets by which specific techniques are required to make progress; a puzzle that surrenders to only simple inferential rules, even if it requires more digits to be filled in in total, will be accessible to all players; a puzzle that requires some more complicated inferences based on dependencies between cells will only be accessible to folks who have internalized those techniques; and so on up to some of the most devilish wide-spread dependencies that the hardest puzzles require analysis of. This sort of ranking would still no doubt correlate pretty well to the more general approach in the write-up here, but I think it would be more telling about the kinds of challenges different cohorts would be up to in a way that captures the plateaus and sudden leaps players experience in puzzle solvability as they internalize new techniques.
posted by cortex at 9:36 AM on July 26, 2024 [3 favorites]
That's kind of how Sudoku Assistenten works. It tries to solve using standard human-known patterns, like pairs or X-wings or Skyscrapers, and gives it a 1-10 ranking depending on the degree of difficulty:
posted by MtDewd at 11:57 AM on July 26, 2024 [6 favorites]
1 Very Easy - (just elimination)I like it because you can also go into Analytical Mode and just see one number at a time.
2 Easy - Single Candidates
3 Average - Line vs Box/Box vs Line single
4 Hard - Line vs Box/Box vs Line multiple
5 Very Hard - Pairs, Triplet
6 Extremely Hard - X-Wing
7 Super Hard - Skyscraper, Turbo Fish, 2-string kite
8 Ridiculous - Swordfish, Jellyfish
9 Insane - XY wing
10 Perverse - More than one XY wing
posted by MtDewd at 11:57 AM on July 26, 2024 [6 favorites]
« Older Doubling as a delicious maths problem | I like big bums and I cannot lie... Newer »
This thread has been archived and is closed to new comments
posted by jacquilynne at 6:32 AM on July 26, 2024 [1 favorite]