HN Theater @HNTheaterMonth

Oh man, are you in for a treat!

https://www.youtube.com/watch?v=yKf9aUIxdb4

⬐ jmiskovic

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.

⬐ shultays

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

⬐ dan-robertson

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.

⬐ ghusbands

> (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.

⬐ dan-robertson

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.

⬐ ace32229

Decades of practice in fact

⬐ andrelaszlo

It's really impressive to me how clearly he articulates what is going on in his head while solving.

⬐ jgwil2

Yes! Bet he would ace whiteboard interviews too.

⬐ techslave

that’s my favorite part. not that he can solve it, but that he articulates the process, seemingly at full speed and totally relaxed.

reminds me of race car drivers that do live narration

⬐ zwegner

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.

⬐ thom

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?

⬐ kccqzy

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.

⬐ darekkay

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.

⬐ rtpg

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.

⬐ thom

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.

⬐ GreedCtrl

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:

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.

⬐ thom

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?

⬐ krajzeg

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.

⬐ thom

Understood, thanks very much for explaining.

⬐ graywh

extensive "exploration and backtracking" (what the community calls bifurcation) is generally avoided when setting puzzles

there are more advanced patterns and techniques that can be used with sudoku, but this puzzle doesn't feature all of them

⬐ chrisshroba

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!

⬐ vesinisa

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.

⬐ jowiar

The interesting thing about this puzzle is that it is in some ways easier than many regular sudokus, in that at any given time, you're working with a very narrow space of immediate next actions (and it's rather obvious what they are).

⬐ prawn

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.

⬐ fredley

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.

⬐ antfarm

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.

⬐ lonelappde

Alternatively, count up by 4 left to right (aka your -1 every two squares), and count up by 3 top to bottom within a box.

⬐ macintux

I don’t have the math background to assess the accuracy of these replies, but they might explain it.

https://twitter.com/NikhilBukowski/status/126262285333933670...

⬐ chongli

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.

⬐ GreedCtrl

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

    +-----v-----+
    |   |431|   |
    |  8|   |4  |
    | 3 |   | 1 |
    |---+---+---|
    |2  |   |  5|
    |3  | 6 |  9|
    |9  |   |  2|
    |---+---+---|
    | 7 |   | 6 |
    |  9|   |5  |
    |   |853|   |
    +-----------+

https://www.youtube.com/watch?v=N41yZsxIsK8

⬐ jansan

+1 for the great formatting.

⬐ Jestar342

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.

⬐ pilsetnieks

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.

⬐ glenvdb

My favourite part is his own disbelief as he ... spoiler ... continues to solve it.

A few minutes later... when the first three on the board causes a cascade of solvable cells after a build up of deduction. Amazing.

⬐ accidentalrebel

He also said he was closed to ending the recording because he thought he was being trolled by the creator.

It was fun seeing him slowly realize that it was not a joke at all.

⬐ msoucy

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'm not bitter, of course not.

⬐ nickysielicki

Here's a solver in python with z3: https://gist.github.com/sielicki/fd86d68733133f654128519b3c4...

(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 total

⬐ dreamer_soul

I love how z3 code looks like magic! Seems like a good library to start getting the hang of

⬐ gabrielsroka

Each row is a cycle [?] of 483 726 159. And even the cycles have a pattern: 665 665 66.

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.

⬐ carapace

FWIW, "Boring Sudoku" a solver in Prolog w/ CLP(FD):

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?

⬐ kryptn

> To me the video was boring because watching a human do machine work is frustrating (to me).

I wouldn't think Sudoku is machine work. Yes, a machine can solve it, but it's not intended to be machine work.

⬐ carapace

It's intended as recreation, yeah, but to me watching that video was like watching someone carry large rocks without aid of a wheelbarrow.

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?

⬐ carapace

Futamura Projections

⬐ dEnigma

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.

⬐ nickysielicki

That's cool, but that doesn't solve this puzzle. It's just a normal solver unless I'm missing something.

⬐ carapace

You're correct.

Adding constraints that encode the additional rules is also a little puzzle, eh?

I'll probably work on it later this evening for fun.

⬐ natrys

I used Picat which provides a uniform API for many different flavour of solvers (e.g. smt module uses z3 underneath): https://gist.github.com/natrys/c19be79ac93578674540cdfa7a0df...

I get instantaneous answer with apparently zero backtrack with both SAT and SMT module. Though I don't know how reliable this statistics is.

⬐ acangiano

25 minutes you'll be okay with never getting back.

⬐ CamperBob2

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.

⬐ mulmen

I’ve watched several videos from this channel over the last few weeks. Sometimes he identifies a pattern and calls it out but he never uses that information to find the solution.

I wonder if there are puzzles where there is a pattern that almost gives the solution but is actually misleading.

⬐ matsemann

In fact, all rows are just permutations of the numbers 1-9! Edit: ;)

⬐ quietbritishjim

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.

⬐ singlow

Been addicted to this channel since the lockdown started. Many more than 25 minutes I'm happy to be rid of.

⬐ jurmous

You can also if you want turn the playback rate up of the video and have the same satisfaction in half the time :)

⬐ yesenadam

Really, you can follow his explanations at 2x?! Less than 1x the satisfaction, I suspect.

⬐ the_duke

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.

⬐ metalliqaz

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.

⬐ JackDrury

which addon are you using for speedup?

⬐ Hitton

Enhancer for YouTube can do that, but you can also do it with simple userscript. The userscript I found somewhere few years ago:

  // ==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;
          }
  
      });
  });

⬐ unkulunkulu

Wait, what? Youtube has builtin control for that for years, behind the cog wheel at the bottom right of the video.

⬐ None

None

⬐ hummusandsushi

They're using the addon to be able to get 3x and 6x speedups, which are not available by default.

⬐ imjasonmiller

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

1. https://webapps.stackexchange.com/a/136744/233601

⬐ davidwparker

I'm a big fan of this one: https://chrome.google.com/webstore/detail/video-speed-contro...

Made by a Google employee. I use it all the time on Youtube, Netflix, Vimeo, etc.

⬐ nayuki

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×.

⬐ jholman

Add a bookmarklet. You add a bookmark, and then you replace the URL with one of these:

Interactive variable-rate:

  javascript:void%20function(){document.querySelector(%22video%22).playbackRate=parseFloat(prompt(%22Set%20the%20playback rate%22))}();

One-click (I have half a dozen of these):

  javascript:void%20function(){document.querySelector(%22video%22).playbackRate=2.7}();

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

⬐ marcus_holmes

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.

⬐ bmn__

> guessing where the narrator stops the "welcome to my channel, smash subscribe and like, etc" bit is tricky.

https://duckduckgo.com/?q=wadsworth+constant+video

⬐ marcus_holmes

hahaha that's awesome, thanks!

⬐ js2

"Once you eliminate the impossible, whatever remains, no matter how improbable, must be the truth."

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

⬐ andretti1977

Oh my gosh Professor Falcon!!! You reminded me of those times when as a kid i wad so excited and inspired by that movie!

⬐ jcims

This is clicking on an existential level for me.

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.

⬐ jianshen

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!

⬐ glandium

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.

⬐ this_is_not_you

Now I want a making-of video by the creator of the Sudoku.

⬐ redcodenl

I wonder how much of that is programmed/automated and how much work is still being done manually...

Backtracking and eliminating numbers can be easily automated.

⬐ antfarm

I commented on this thread regarding a similiar question: https://news.ycombinator.com/item?id=23245300

⬐ Fiahil

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.

⬐ ben-schaaf

I'm still mesmerized by the 15-line prolog sudoku solver: http://programmablelife.blogspot.com/2012/07/adventures-in-d...

⬐ bmn__

https://old.reddit.com/r/programming/comments/1awnv/solving_...

⬐ conistonwater

It's just using a library, you can get the same effect in any language with a constraint satisfaction library.

⬐ redcodenl

Completely agree here, the entire 'solver' is a library there.

However, it does show how cool and versatile SAT solvers are for people who haven't used or seen them yet.

⬐ carlob

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.

⬐ yesbabyyes

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.

[0] https://youtu.be/Tv-48b-KuxI

⬐ adenozine

I get the feeling that he would be a very impressive programmer.

⬐ dathinab

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.

⬐ louisch

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)

⬐ macintux

See this thread (disclaimer: I have zero clue to its accuracy).

https://twitter.com/NikhilBukowski/status/126262285333933670...

⬐ billme

Here’s link to the puzzle:

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

⬐ swyx

I was just thinking the other day how I've never seen a YouTube video at the top of HN. along comes this video to prove me wrong.

⬐ busterarm

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.

⬐ SamBam

Unsure what you mean by "the full pattern." Do you mean you could work out what the entire grid was, from just half the twos alone?

⬐ busterarm

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.

⬐ tudorizer

Not a big sudoku fan, but wow! I might have under-estimated how exciting it can be.

⬐ mywacaday

and we have rotational symmetry! brilliant!

⬐ swah

How do know if a certain puzzle is impossible (ie malformed)?

⬐ matsemann

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.

⬐ matsemann

> For Sudoku, that's easy to verify.

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...

⬐ billfruit

Any other puzzles with deep deductive reasoning where one can get better at through playing. One comes to mind: hexcells, any others?

⬐ matsemann

I also asked this question in another thread here, got some responses and included my tips: https://news.ycombinator.com/item?id=23245258

⬐ DonCopal

https://www.chiark.greenend.org.uk/~sgtatham/puzzles/

⬐ yesenadam

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."

https://en.wikipedia.org/wiki/Chess_problem

⬐ billfruit

What would be a good book to get into chess problems and the culture/aesthetics of them?

⬐ yesenadam

Sorry, I wouldn't know.

⬐ tshanmu

puzzles and progamming - two of the best ways to while away the time.

⬐ ropable

This video was just fabulous to watch.

⬐ 2easy

perverts.

⬐ residualmind

https://www.google.com/search?q=483726159

⬐ SubiculumCode

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

⬐ goto11

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

⬐ SubiculumCode

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.

⬐ helsinkiandrew

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

⬐ SubiculumCode

That brought back some memories...that was pretty much what I did.

⬐ shultays

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.

⬐ SubiculumCode

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.

⬐ Marazan

It's more that solving Sudoku by Brute Force is easy.

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.

⬐ shultays

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.

You can do anything given enough brute force!

⬐ Marazan

That doesn't guarantee you that you generate a Sudoku solveable without backtracking.

The human techniques are all about forward actions only, never guesses.

⬐ dmurray

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.

⬐ shultays

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

⬐ Majromax

> 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.

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.

⬐ twic

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.

⬐ mikejb

> 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. ;)

⬐ SubiculumCode

Good point. Thanks for bringing that up. I've edited my comment to bring context to my perspective.

⬐ deepaksurti

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!

[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

⬐ boomlinde

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.

⬐ hummusandsushi

Your solution doesn't respect the knight's move and king's move constraints, which cause the original puzzle to have exactly one solution.

⬐ prawn

The first line of your result fails the orthogonal adjacent rule of this puzzle eight times!

⬐ Marazan

You have consecutive numbers appearing next to each other.

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.

⬐ aidos

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.

⬐ leetbulb

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

[0]: https://www.youtube.com/watch?v=hAyZ9K2EBF0

⬐ ABeeSea

This was the longest unsolicited YouTube video I’ve watched in a long time. Truly enthralling.

I’m kind of interested in if there are any interesting insights in the symmetry he points out at the end. I know nothing about hard sudokus, but that symmetry seems worth diving into.

⬐ andrepd

Yeah all of his videos are great, in a wholesome kind of way.

⬐ mft_

Agree! I was very sceptical even opening the video. And then, 25 minutes later…

⬐ AS126

Now I have to watch it... God damn it! Because your comment I mean.

⬐ matsemann

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.

[0]: https://www.chiark.greenend.org.uk/~sgtatham/puzzles/ [1]: http://www.kaser.com/ww.html

⬐ ZeroGravitas

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.

⬐ kadoban

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

⬐ matsemann

Good suggestion. I already play chess and enjoy solving "tactics".

⬐ tasuki

Hey I made a website with books full of go problems. It's become quite popular: https://tsumego.tasuki.org/

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

⬐ kadoban

Thanks for your site! I've been there before. I really like the Cho problems.

⬐ tasuki

Cho Chikun is the popular one. My favourite is Gokyo Shumyo!

⬐ frankmcsherry

> 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.

⬐ panzerklein

Picross 3D is amazing. Should run without any problems on emulator.

⬐ chris_st

I'll second Kaser's "Sherlock"... Had a lot of fun with that back when I had a windows box.

And YEAH, his art-style is funky indeed!

⬐ acheron

I first played Sherlock as a MS-DOS program in 1992 or so.

Of his many variations on the theme, I like "Mrs. Hudson": http://www.kaser.com/mh.html

⬐ chris_st

Thanks, "Mrs. Hudson" is interesting. Still think I like the original Sherlock the best...

⬐ acheron

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.

⬐ cbsks

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

[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...