I almost didn’t watch that’s because who cares about someone solving a sudoku puzzle, but that was brilliant.
That’s one happy solver; it was worth it just for the absolute joy he gets from it. Amazingly quick solving too. Good to watch him develop extra strategies during the process.
Yeah, I liked how he realized two possibilities for a number that were next to each other, also meant the box around it could be cleared.
I really enjoy finding patterns like these in constraint games. After confirming the pattern for myself a number of times, the brain later just does it on autopilot. If people have tips for similar games I would be happy to try them.
Edit, my tips: Simon Tatham's Puzzle Collection [0] has lots of them. Apps exists for mobile devices as well.
Everett Caser [1] also have lots of logic games where one can learn patterns. I've played Sherlock and Honeycomb, and my favorite is Willa's Walk. They look a bit funky, but the apps work fine on Android.
I am a huge fan of Simon Tatham's puzzles. His developer documentation [0] is absolutely amazing. All the puzzles are written in very high quality C with, in my opinion, a perfect ratio of comments to code [1].
I was hooked on his Tents [2] puzzle for a few weeks, then I started modifying the code to automatically fill in squares based on the tricks I found for adding constraints. Before I knew it, I had written a complete solver! Now I don't have to waste my time on it and I can get back to work :)
There's a book called "Puzzle Ninja: Pit Your Wits Against The Japanese Puzzle Masters" that covers these strategies for a bunch of similar games, as well as background info on the creators and examples of the puzzle try.
However, I've found that discovering these strategies myself is actually the bit I like most, so although I've bought the book, I try not to read about the strategies I haven't figured out by myself.
If you're into that feeling, learning a game like go might be something you'd enjoy. There's other parts to the game, but finding clever tactical moves is a huge rush of that.
There's also books and sites with "go problems", chosen puzzle positions, for a quick fix (but only after you know the game a bit).
It's non-interactive not just because I'm lazy, but also there's some reasoning for why you should solve problems rather than click around and randomly try things out :)
> Yeah, I liked how he realized two possibilities for a number that were next to each other, also meant the box around it could be cleared.
This struck me as a bit weird (as he's clearly 100% sharp): this is just the application of the same rule he had been applying everywhere else: if a number can be in one of two squares than anything that can reach those two by king or knight cannot be correct. He doesn't need to use speculation about which of the two cells it is in.
The puzzles in the Sherlock series have a wide range in complexity. I've tried all of them I think and I ended up gravitating to Mrs Hudson the most but I can see why other people would have other favorites. I like several of the non-Sherlock logic games as well -- someone mentioned Willa's Walk earlier in the thread which is a good one.
There have been a few games showing up on Steam with similar deduction gameplay with more contemporary design styles. (There have actually been a lot of interface improvements to the Sherlock games over the years, but style-wise they basically look the same as they did when they first came to Windows in 1996 or whenever!) HexCells was a decent series (there were three games), though to a EKS/Sherlock veteran, the first game was ridiculously easy. The second and third had some good puzzles in them, but they were all handcrafted rather than procedurally generated. I couldn't figure out why there weren't random puzzles, and then the third game (HexCells Infinite) did have random generation, and it turned out that the answer was: because the random puzzles were garbage. Still, the handcrafted puzzles in the second and third games were nice for a bit, but compared with a game like Sherlock that you can continue playing random puzzles for practically ever, it seems like a bit of a short stick. There were a couple others I found on Steam that were similar, but I mostly get my logical deduction habits on with Mrs Hudson still.
I discovered this channel with the four digit magic square[0]
When I first saw that video, I thought the same thing and just brushed it to the side. Later that day, SO and I were bored so I figured I'd toss it on the TV. Immediately she wanted to solve it with me before he started to explain his solution. Now we do these together every so often and compare strategies. Sudoku can be a good partner exercise, too :)
The lightning speed of his observing standard rules across the board is impressive but expected after months of practice. The agility with which he picks up new rules and starts working with them is sign of a beautiful mind. This was a pleasure to watch.
Yeah, the guy is a genius at solving sudokus and makes it look easy. It is amazing how he fast can develop new "algorithms" and the explanation for the for new rules he encounters. And the way he develops/explains those algorithms
I though that too at first but actually they seem well practiced too. Eg other sudoku-style puzzles also have knight move rules. The main trick I missed is the forking one (if I put a 3 here then it reaches here and here by knight’s move therefore it can’t go here).
That said It is still impressive and I think practice is not sufficient to explain how fast he is at it.
> (if I put a 3 here then it reaches here and here by knight’s move therefore it can’t go here)
A possibly-simpler way to look at it is the inverse. Putting a 3 here or here (where it must go) both block this other place, so we know this other place is blocked either way.
Yes, that’s something I tried thinking about but computing the intersection of two or more quite large regions turns out to be harder than using the symmetry to only look at one region. There are also tricks one can learn for eg dominos.
In case anybody sees this comment before the video: I'd highly recommend trying to solve the puzzle yourself. After you see the rules stated in the video, click the link in the info. It took me a bit longer than this guy, but it was a very fun puzzle.
Absolutely agree. When he was about to start the threes, I stopped watching and saved it to solve with my 7yo that night. My son was the one that got most of the three placements ruled out and enjoyed lording that over me. After completing it, we went back to watch the host solve it. Fun puzzle and just as entertaining watching the host gradually put it together himself.
I'd never done sudoku before and was a little disappointed to find it was so mechanistic. I'd sort of expected there to be some degree of exploration and backtracking, or perhaps having to solve multiple digits simultaneously while attempting to keep it all in your head. Is this puzzle representative of normal sudoku puzzles or do the additional constraints change it?
On the other hand, backtracking feels much more mechanistic to me. A dumb computer can guess and backtrack and check constraints with a simple algorithm. Humans ought to do better than that—with more logic and more deduction.
Check out a Hitori. It's kind of an "inverse Sudoku". More difficult puzzles always get to a point where you have to guess the state of a certain field and then backtrack if you were wrong.
Basically the challenge is in finding the thought process that leads you to an answer.
The kinds of puzzles done on this channel tend to be pretty tough. the designers of the puzzle usually make it so that there's really one good path for solving (and brute forcing _really doesn't work_ relative to thinking hard about the problem).
There's a lot of stuff going on in this puzzle that's not at all present in normal sudoku, and things like "OK let's try and look for where _all the 3s could be at once_" is easier said than done.
I guess to me if still _feels_ a bit like brute force. You just go over all the squares and all the rules in a loop, adding and eliminating possible digits. There don't seem to be any sticking points where it's not clear how to make progress.
The "exploration and backtracking" you mention originally is the brute force method of solving sudoku by computer: recursive backtracking. If you want an example of sticking points, I'd recommend the Robin Hood sudoku:
It can be brute forced with enough patience, but the fun for me comes in developing intuition on where to look next. The hints of a sudoku have meaning: they lead to the completed grid. Finding the next step in the puzzle amounts to understanding some of its construction.
I guess the bit I'm missing is why the miracle sudoku (the two I can find) are special. As far as I can tell, they don't require any intuition at all, you just sit down and work through the rules that are right in front of you. Surely they're much easier than normal sudoku because of the extra rules? Are they noteworthy because of the construction of the puzzle, rather than the solving of it?
It's mostly about the construction. The "miracle" part refers to just two clues (filled-in numbers) leading to a unique solution, which is a ridiculously low number.
Does anyone know of good places to look for similarly interesting puzzles? I'd recommend https://puzzling.stackexchange.com/ but I'm looking for others to supplement that!
So to reiterate, this is not solvable by normal sudoku rules alone. Further rules and constraints are provided on the placement of the digits that happen to render it solvable.
How on earth do you create a puzzle like that? Coming up with the rules it's presumably simple to generate solutions with a computer program, but how do you then work out the cells which need to be filled in order to not only minimally describe a single correct solution, but also leave a reasonable deductive pathway to that solution?
I think that's what boggles me most about this, the deductive pathway that's been created by the puzzle creator is a complete joy in its unfolding.
Sudoku at its heart is a graph colouring problem. When you add the new constraints, it changes the connectivity of the graph. This sudoku, with all of its extra constraints, becomes a highly connected graph which greatly reduces the number of possible valid puzzles. Throw in the fact that the grid is already symmetric about both axes of reflection and rotationally symmetric about the centre and that further constrains the set of valid puzzles.
I'm sure you could write a program to take all these constraints and generate a ton of puzzles and then scroll through them to find ones that look great. It also wouldn't be too difficult to sort them in ascending order of givens.
Speaking of great-looking puzzles, this youtube channel covered a visually stunning pi day sudoku some time ago. As you said, it uses extra constraints to reduce connectivity, but still, I find it amazing that the digits of pi can fit so well into a puzzle. (Pi begins at the top and moves clockwise.)
There is a pattern in the solution: Consecutive numbers are separated by one field and enumerated horizontally from the left to the right, wrapping around the edges, i.e. ..._4_3_2_1.
Every line of the solution has the same sequence of numbers, shifted by 4 places to the left relative to the line above it.
This makes me believe the construction is based on a clever observation and repetition of a pattern.
This guys is my "ASMR" bedtime watching. I just love his overall demeanor and child-like thrill from puzzle solving. I can be wired when I start his video and by the end I'll be blissfully calm and head-clear. I think he has a tremendous talent of focus. As other posters have said, he can spot constraints so quickly. I still get a small kick out of spotting something before he does, though. Doesn't happen often, mind.
I actually had to double check if Sean Lock (https://en.wikipedia.org/wiki/Sean_Lock) hadn't taken up a new hobby of solving sudokus on youtube, he both looks and sounds incredibly similar.
I once spent an hour trying to solve a sudoku puzzle on a whiteboard in college. It turned out that the person who left it there made a mistake when they started to solve it, so given the state it was in when I started (no way to tell what was original and what was their deduction) it was impossible to solve.
I don't mean this in a critical way, just an observation. To me the video was boring because watching a human do machine work is frustrating (to me). (As fast and as clever as that fellow is, he's still so slow compared to a computer.)
However, designing elegant constraint rules to encode the special constraints of this puzzle is also a puzzle, and that puzzle seems interesting to me. (Although not very because it's not that challenging.)
I have the same problem with most video games: after playing just a little while I get bored and want to reprogram the game itself instead of just playing it.
You can have fun at all those levels, jumping back and forth between them at your leisure. Just because you can program a computer to solve a sudoku doesn't mean that you can't enjoy solving one by hand from time to time. Digging a ditch can be fun too, as long as you don't have to do it all the time.
I recently started increasing playback speed on many videos I watch. It's really hard at first, but I quickly got used to it, to the point where I now use an addon to increase playback speed to 3-6x where appropriate.
When there's something complicated, or something I want to enjoy and savior, I jump back and slow down.
This is an incredible time saver.
I got inspired to do this by observing a blind programmer use a screen reader with insane speeds.
I only recently discovered this, too. I was complaining about how I preferred reading than watching videos, partly because I can read a lot faster than someone can narrate, and because I can "skim-read" text. They suggested playing the video back at a higher speed, and it works fine. Still haven't quite solved the "skim-read" thing - guessing where the narrator stops the "welcome to my channel, smash subscribe and like, etc" bit is tricky.
i don't know how you can go 3-6x. I listen to podcasts at 1.5x and if I go to 2x I don't absorb any information. I think to actually do 2x, I'd have to stop whatever I'm doing (driving, chores, gaming, etc) and focus specifically on the podcast. That feels like I'm wasting time again.
These work on any non-iframe HTML5 video player. I'm pretty sure you can edit to work on audio too, but that's less frequently useful. I guess this version of the code only works on the first video in a page; that has never limited me, but it's easy to fix by changing to `querySelectorAll` and using a `.map` (or `.forEach`) with anonymous function. The bookmarklet technique doesn't work on iframes (like embedded players often are), but only because of browser security restrictions, so if you open the dev console (ctrl-shift-i), you can choose from
1) just load the iframe itself, or
2) run the JS code yourself in the browser console, where the browser's security rules don't stop you
If you're an even modestly competent web developer, you can solve novel UX problems on any website you use moderately often, or in this case UX problems with HTML elements that appear on many many websites.
I agree with the grandparent poster. I watch nearly everything at 1.5x to 3x speed (anything where the timing/tempo isn't itself part of the subject matter). Perhaps I should up my game and go for the "3x-6x" GP claims, because still some content is just too damn slow. Basically the clearer the enunciation of the speaker, the faster you can watch it. Pause and rewind as necessary (e.g. on YT it's space to pause and left arrow to back up 5 seconds).
This is great. The max being only two bothered me and I completely forgot that one could do that as well. I'm going to expand on the small script I wrote that sets the playback rate to twice the speed by default [1]. Thank you! :-)
You can control YouTube's playback speed by pressing < or > on the keyboard. The default list of speeds are: 0.25×, 0.50×, 0.75×, 1.00×, 1.25×, 1.50×, 1.75×, 2.00×.
Once you see that each row appears to be a shifted copy of the same sequence, you'll spend at least part of that time yelling at the screen, hoping he hears you.
That's always true of all Sudokus. It follows from the rule "no number can appear twice in the same row (or column)" and the fact that there are exactly as many columns as numbers to put in them. What the parent was saying, that all rows are a shift of the same sequence, is much more unusual.
In case there's confusion over terminology: starting for example with 123456, then 345612 is a shift (and a permutation) while 345621 is a permutation but not a shift.
Lex Fridman's podcasts in particular have been sort of forking in two directions lately, one on artificial intelligence, consciousness and just a somewhat muted wonder how the human mind operates and our present lack of understanding of how it comes together systematically to create our experience. The other is about physics and how the experimental and theoretical come together to try to give us a better understanding of the fabric of our universe.
For this video, in the former case it shows how plastic the mind can be. I'm probably about the same age as the guy in the video and honestly have been struggling with an experience of cognitive decline lately. To see how adaptive the brain is to not only develop grooves that accelerate analysis in the long form, but also adapt to new rules and constraints almost as quickly is really quite remarkable (and for me personally, encouraging).
His quick pattern analysis at the end uncovered the second case for me. This is obviously something we've seen in many other situations as well, but how a collection of 'particles' with multi-dimensional constraints can form order and even crystalline structure from almost nothing.
There is something irreplaceable about the first time you solve a difficult puzzle, especially one that you anticipate to be daunting. As a Sudoku enthusiast (though not at Simon's level) this was surprisingly vicarious to watch for what's usually a silent solitaire experience. Well done!
For some reason this video ended up in my Youtube recommendations last week, and I clicked on it because the thumbnail caught my attention. Didn't regret it, and I've watched a few others. Another that was pretty interesting in the development of techniques to approach it: https://youtu.be/Zk4qNEDXFSw
Edit: Ah no, the first I saw was actually https://youtu.be/hAyZ9K2EBF0 which has a diagonal rule, and a magic square in the middle.
I made a sudoku solver back when I was in school. It's quite simple and almost a textbook case for backtracking. Even brute-force algorithms are instantaneous on the hardest puzzles.
At the beginning I was wondering whether 9 and 1 were to be considered consecutive. It's not stated anywhere, but it seems that the solution has this property.
This was great fun! They have a new miracle sudoku[0] up since a couple of days, as well. Seeing him color the potential twos (aside from two wrongly colored squares) and then piece by piece ruling them out almost looked like a game of life, with new patterns emerging.
It did the follow up sodoku (a new miracle sodoku), which I think probably is a bit easier as it starts with 3,4 in a slightly more useful constellation.
I have to say while I'm not the biggest fan of normal sudokus the ones with extra rules are quite interesting.
And the cracking the cryptic channel has quite a bunch of such sudokus.
Ever since seeing this video I've been wondering if there's some deeper mathematical basis for this puzzle, because of the extremely regular pattern that it happens to produce.
For example, the way consecutive digits are actually in order, but separated by a single square (and looping around the edge of the board)
I immediately saw what the full pattern was when he had half the 2s filled in and was wondering if he saw it and kept going through the solution for the purposes of the video, or didn't see it at all until the end.
That never ended up becoming clear and now I'm just left wondering.
The twos and the existing ones. I made a reasonable guess that proved to be correct.
All the twos had symmetry and can be plotted on the grid like a tile pattern...and every increasing number in a row is two positions to the left of the lower number. It was blatant at that point in the vid.
Right at around 12:14 and then confirmed by the 18 minute mark.
That is a "decision problem": Does this puzzle have a solution?
For Sudoku, that's easy to verify. That makes it an NP-problem. But for Sudoku, finding a solution is very difficult, so difficult that we say it's NP-Complete. So the only way to verify that a Sudoku can be solved, is really to try a bruteforce (potensially sped up with guesses/backtracking) and then find out if you cannot continue because of a broken constraint somewhere.
I meant: For Sudoku, it's s easy to verify that a given solution is correct. (cannot edit)
Of course, being given the solution first in order to even try, can be a bit boring. For that, there exists "zero-knowledge proof" where one can reveal one knows an answer, without actually divulging it. Here is a writeup about someone doing that for Sudoku: https://manishearth.github.io/blog/2016/08/10/interactive-su...
There's a whole world of chess composition/problems. You can even be a grandmaster chess composer or solver. Some composers are legendary in the chess world, e.g. Troitzky, Sam Loyd, Kubbel. Chess problems come in various kinds, and are a bit like cryptic crosswords - they seem impossible at first but there are customs, tricks, conventions which make them easier with experience. "The role of aesthetic evaluation in the appreciation of chess problems is very significant, and indeed most composers and solvers consider such compositions to be an art form."
As a college project in C, we were to write a soduku solver. Smart people solved it by programming in fancy heuristics. Not being smart, I just brute forced it...though I tried to be fancy by representing the data at the bit level. I doubt it made it any faster lol.
That said, when the hardest Soduku problems in the world succumbed to a brute force search to my lame program in less than a few something something ms, I kind of shrugged at the fancy methods. But I suppose that is why I'm still just a mediocre programmer :)
The brute force method was basically move forward until you hit a dead end, backtrack, go forward again until you hit another dead end, etc.
Edit: I'm not being dismissive of people who implemented better solutions. Honestly, at the time I was amazed at their skill. But I still chuckle just because the problem is trivially sized for brute force methods, and would have to be scaled much larger to actually make more sophisticated methods worth the effort in any situation other than personal satisfaction and education. In a business situation in which you do not expect the problem to scale, spending more time for a sophisticated solver may not be worth the effort. But yes, Soduku is for entertainment and R&R
> when the hardest Soduku problems in the world succumbed to a brute force search to my lame program in less than a few something something ms, I kind of shrugged at the fancy methods.
I think you're coming off as dismissive, which is why you're getting downvoted. Puzzles like these have the purpose to entertain a human solving them, and they do that pretty well.
If you seek entertainment in developing algorithms to solve these puzzles, you should adjust your challenge to modern computers: Up the size to 100x100 or more, see how your algorithm performs, and go from there. Spoiler: NxN Sudoku is NP-hard (NP-complete, to be precise), so have fun - maybe you'll even win a million dollars.
Now, if you want to really challenge yourself: Write an algorithm to create Sudoku puzzles that have a unique solution and as few initial numbers set as possible. Maybe you'll even improve your coding skills beyond mediocre. ;)
Wouldn't brute force be enumerating all possible combinations of numbers until you find one where all sums are correct? Your approach with backtracking sounds more fancy
It was a long time ago, but I think I randomly filled in numbers, save if numbers were already used in each row or column, then when it reached an impossible solution, it would work backwards one level, trying new numbers. If it ran out of numbers, it would go back two columns, and try a new number.
I doubt it was anything fancy. At the time, it bent my mind into knots. Programming is a wonderful mind trainer.
For those who want to see how a backtracking algorithm would work. Computerphile walked through a python approach (11 lines) a few months ago:
https://www.youtube.com/watch?v=G_UYXzGuqvM
I was discussing this with a friend. I too made a brute force sudoku solver. It was somewhat smart since it was keeping track of what options are available for each cell and updates those options as it puts/removes digits.
The friend told me he was working on a sudoku solver and was trying to explain his non-brute force algorithm. I told him I did a solver back in collage and it was basically instant even though it is brute force.
Similar story. A friend and i were arguing about whether you could solve sudokus by brute force in reasonable time. So we whipped out a couple of laptops and tried it. I had a brute force solver (kind of branch-and-bound-ish, ISTR) finished before he had his constraint-based approach running, and it solved any puzzle in the blink of an eye.
To capture some of the fun of human Sudoku-solving, i think you'd want to have some sort of metric for how brute the force is, and then see if you can write a solver which is as unbrutal as possible. I'm not sure what that metric would be, though.
Amazing. I got down voted for my story. HackerNews does not like Mediocre Programmers I guess lol.
I bet I could write a better algorithm today if I was motivated. Back then I was not as experienced in programming, and I struggled with even figuring out how to represent the data and the state. Its all about learning from where you were at the time.
Sure you can, just brute force your way to ensure there is only a single solution. You can try all combinations and count how many reached to the end and check if count == 1.
Generating sudokus while all you have a sudoku solver seems an interesting challenge. Sounds like it can be done though, just a matter of creating random boards by adding one digit at a time that doesn't break rules and check if # of solutions is 1. I imagine even that would be fast enough, at least enough to create sudokus at a reasonable rate that can supply entire human population.
Hmm I don't get what you mean. For a valid sudoku there shouldn't be any guessing involved? So during any stage of solution, there should be always a single move that is the only option option move solution forward?
But even then humans do "moves" like "if i put that number here then that eliminates all other possibilities, that leaves us only that other number", which is kinda like guessing. So even if there are no single so human also tries if a valid move will block all future valid moves. A brute force algorithm does just that, except that it has a much larger memory and computation speed so it can think that at 9x9 depth to find a perfect solution
> For a valid sudoku there shouldn't be any guessing involved?
In the philosophy presented on that channel, it's not that such a Sudoku puzzle is "invalid," it's just not particularly interesting or 'beautiful'.
From my viewing, there appear to be two differences between "logic" and "guessing" (or "bifurcation"):
* Bifurcation/guessing is just as happy with a correct guess as an incorrect one. If I guess that a square is a '1' and then fill out the rest of the puzzle without finding a contradiction, then that's a good (in fact the best!) guess. "Logic," on the other hand, seeks contradictions to rule out possibilities
* "Guessing" is content to proceed arbitrarily far down the solution tree to find a solution (or contradiction), whereas "logic" limits itself to a few steps that can stay in a human's working memory.
However, the difference is clearer with the kinds of puzzles highlighted on the linked channel. These puzzles often include additional constraints, such as "the first three cells in the row form an increasing/decreasing sequence." "Logic" then provides universal derived constraints (such as "a 9/1 can never be in the middle of this sequence") that are more obviously distinct from depth-first-search guessing.
I've never understood the difference. When I solve sudokus, including this one, I use backtracking all the time. "The 2 goes here or here, if it goes here then I get a 2 here, a 2 here and there's no room for the 6 there...so the 2 goes in the other spot after all". The "forward methods" are equivalent: just shortcuts to the same thing, spotting reusable patterns like the "ringing the domino" motif the solver identifies in the video.
Using my CL based sudoku solver [1], I got the following solution. The solution is valid but different from what is shown in the video. IIRC, a sudoku board can have multiple solutions but anyone out here can explain why so? I am no sudoku expert or enjoying solving sudokus anyways!
Your sudoku solver is solving a different puzzle altogether from the one posed in the video. Sudoku puzzles also don't normally have multiple solutions. The smallest known Sudoku satisfying that constraint have 17 clues. Offering only two clues is possible here because of the additional placement constraints.
That’s one happy solver; it was worth it just for the absolute joy he gets from it. Amazingly quick solving too. Good to watch him develop extra strategies during the process.