The Miracle Sudoku [video]
youtube.com
youtube.com
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.
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.
[0]: https://www.chiark.greenend.org.uk/~sgtatham/puzzles/ [1]: http://www.kaser.com/ww.html
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 :)
[0]: https://www.chiark.greenend.org.uk/~sgtatham/puzzles/devel/
[1]: https://git.tartarus.org/?p=simon/puzzles.git;a=blob;f=tents...
[2]: https://www.chiark.greenend.org.uk/~sgtatham/puzzles/js/tent...
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.
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 :)
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.
And YEAH, his art-style is funky indeed!
Of his many variations on the theme, I like "Mrs. Hudson": http://www.kaser.com/mh.html
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.
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 :)
reminds me of race car drivers that do live narration
That said It is still impressive and I think practice is not sufficient to explain how fast he is at it.
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.
there are more advanced patterns and techniques that can be used with sudoku, but this puzzle doesn't feature all of them
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.
https://www.youtube.com/watch?v=pdtWTg4LrqQ
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 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.
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.
+-----v-----+
| |431| |
| 8| |4 |
| 3 | | 1 |
|---+---+---|
|2 | | 5|
|3 | 6 | 9|
|9 | | 2|
|---+---+---|
| 7 | | 6 |
| 9| |5 |
| |853| |
+-----------+
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.
https://twitter.com/NikhilBukowski/status/126262285333933670...
A few minutes later... when the first three on the board causes a cascade of solvable cells after a build up of deduction. Amazing.
It was fun seeing him slowly realize that it was not a joke at all.
I'm not bitter, of course not.
(note, most of the code coming from here, I just slopped together the additional constraints, https://ericpony.github.io/z3py-tutorial/guide-examples.htm )
$ time python3 game.py
[[4, 8, 3, 7, 2, 6, 1, 5, 9],
[7, 2, 6, 1, 5, 9, 4, 8, 3],
[1, 5, 9, 4, 8, 3, 7, 2, 6],
[8, 3, 7, 2, 6, 1, 5, 9, 4],
[2, 6, 1, 5, 9, 4, 8, 3, 7],
[5, 9, 4, 8, 3, 7, 2, 6, 1],
[3, 7, 2, 6, 1, 5, 9, 4, 8],
[6, 1, 5, 9, 4, 8, 3, 7, 2],
[9, 4, 8, 3, 7, 2, 6, 1, 5]]
python3 game.py 7.47s user 0.15s system 97% cpu 7.801 totalI get instantaneous answer with apparently zero backtrack with both SAT and SMT module. Though I don't know how reliable this statistics is.
That is, you can rotate the first row by 6 to get the second row, then rotate again by 6, then by 5, etc.
The columns are almost as consistent, but not quite.
https://swish.swi-prolog.org/p/Boring%20Sudoku.swinb
- - - -
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.
Do y'all feel me, or am I just a freak?
Adding constraints that encode the additional rules is also a little puzzle, eh?
I'll probably work on it later this evening for fun.
I wouldn't think Sudoku is machine work. Yes, a machine can solve it, but it's not intended to be machine work.
Or like digging a large ditch without aid of a backhoe.
To me there is a clear hierarchy or graduation of puzzles. Metaphorically:
1. Ditch digging by hand.
2. Planning efficient ditch layouts to be dug by machines.
3. Designing new and better ditch digging machines.
- - - -
1. Solving Sudoku puzzles.
2. Designing new Sudoku puzzles (with additional constraints even.)
3. Designing e.g. CLP(FD) programs to solve all sudoku puzzles everywhere.
- - - -
What I'm saying is, Why don't people move up that hierarchy? Why is level 1 so fascinating to people?
I believe that anyone who can solve sudoku can program a computer, but they don't. Why not?
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.
Interactive variable-rate:
javascript:void%20function(){document.querySelector(%22video%22).playbackRate=parseFloat(prompt(%22Set%20the%20playback rate%22))}();
javascript:void%20function(){document.querySelector(%22video%22).playbackRate=2.7}();
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).
// ==UserScript==
// @name Mediabord
// @version 01.1
// @description tryd to take over the world!
// @author j
// @match *://*/*
// @grant metadata
// ==/UserScript==
document.addEventListener('keydown', function(event) {
var vidz = document.querySelectorAll('video');
function is_text_box(element){
var tagName = element.tagName.toLowerCase();
return tagName === "textarea" || tagName === "input";}
if(is_text_box(event.target))
return false;
vidz.forEach(vidz => {
switch (event.keyCode) {
case 221: // (])
vidz.playbackRate+=0.25;
break;
case 219: // ([)
vidz.playbackRate-=0.25;
break;
case 220: // (\)
vidz.playbackRate = 1;
break;
case 83:
vidz.currentTime+=3;
break;
case 65:
vidz.currentTime-= 3;
break;
}
});
});Made by a Google employee. I use it all the time on Youtube, Netflix, Vimeo, etc.
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.
Impressive work from a board that initially appears too open-ended to solve but turns out to have sufficient constraints.
Well worth watching. (Aside: the solver reminded me oddly of Professor Falcon.)
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.
Very fun video to watch. Thanks for sharing.
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.
Backtracking and eliminating numbers can be easily automated.
However, it does show how cool and versatile SAT solvers are for people who haven't used or seen them yet.
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.
For example, the way consecutive digits are actually in order, but separated by a single square (and looping around the edge of the board)
https://twitter.com/NikhilBukowski/status/126262285333933670...
https://cracking-the-cryptic.web.app/sudoku/tjN9LtrrTL
About the guide to controlling the interface for the game:
https://cracking-the-cryptic.web.app/how-to-play
(Links are little odd, if you want to find them yourself, just click the YouTube, view the video description, it’s the top link.)
That never ended up becoming clear and now I'm just left wondering.
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.
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...
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
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. ;)
I doubt it was anything fancy. At the time, it bent my mind into knots. Programming is a wonderful mind trainer.
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.
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.
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.
But the trouble with brute force sudoku solvers is you can't use them to create sudokus solveable by humans with a unique solution.
That's the fun stuff in writing a sudoku solver/generator.
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.
You can do anything given enough brute force!
The human techniques are all about forward actions only, never guesses.
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
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.
The latter point is certainly fuzzy, and it leads to developing some heuristics (such as https://www.sudokuoftheday.com/techniques/hidden-pairs-tripl... or https://www.learn-sudoku.com/x-wing.html) to reduce more complicated deductive chains into "single steps."
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.
[1] https://github.com/dmsurti/sudoku
```
(setf board
#(0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 2 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0))
```
* (sudoku:print-board (sudoku:solve board))
1 2 5 | 6 4 7 | 8 9 3
8 3 4 | 5 9 1 | 6 7 2
9 7 6 | 3 2 8 | 4 5 1
- - - - - - - - - - -
5 8 9 | 2 3 4 | 1 6 7
2 6 1 | 7 8 9 | 3 4 5
3 4 7 | 1 5 6 | 2 8 9
- - - - - - - - - - -
4 9 2 | 8 1 5 | 7 3 6
6 1 8 | 9 7 3 | 5 2 4
7 5 3 | 4 6 2 | 9 1 8
```
edit: formatting
One of the constraints is that no consecutive numbers can appear orthogonally.
This isn't a standard sudoku, there are extra rules. There would be a huge number of valid solutions to the board under regular sudoku rules.
EDIT: and you've missed the King's move constraint as well and I presume the Knight's move as well.