Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The Miracle Sudoku [video]

youtube.com

Post reply on HN
Print view View original

111–120 of 150 posts

Re: The Miracle Sudoku [video]

#111

Post by carapace »

nickysielicki wrote: post #71

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,…

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?

Re: The Miracle Sudoku [video]

#112

Post by lonelappde »

antfarm wrote: post #61
fredley wrote: post #53

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 cr…

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.

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.

Re: The Miracle Sudoku [video]

#113

Post by SubiculumCode »

helsinkiandrew wrote: post #32
SubiculumCode wrote: post #14

Earlier quoted context omitted.

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

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

Re: The Miracle Sudoku [video]

#114

Post by metalliqaz »

the_duke wrote: post #19
jurmous wrote: post #3

Earlier quoted context omitted.

You can also if you want turn the playback rate up of the video and have the same satisfaction in half 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…

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.

Re: The Miracle Sudoku [video]

#115

Post by chris_st »

acheron wrote: post #100
chris_st wrote: post #76

Earlier quoted context omitted.

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!

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

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

Re: The Miracle Sudoku [video]

#116

Post by thom »

rtpg wrote: post #104
thom wrote: post #102

Earlier quoted context omitted.

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?

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 sud…

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.

Re: The Miracle Sudoku [video]

#117

Post by GreedCtrl »

chongli wrote: post #85
fredley wrote: post #53

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 cr…

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 constrain…

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

Re: The Miracle Sudoku [video]

#118

Post by jansan »

GreedCtrl wrote: post #117
chongli wrote: post #85

Earlier quoted context omitted.

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 constrain…

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

+1 for the great formatting.

Re: The Miracle Sudoku [video]

#119

Post by kryptn »

carapace wrote: post #111
nickysielicki wrote: post #71

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,…

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 cons…

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

Re: The Miracle Sudoku [video]

#120

Post by msoucy »

accidentalrebel wrote: post #20
glenvdb wrote: post #5

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.

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.

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.

Post reply on HN