The Miracle Sudoku [video] • Hacker News Board

Re: The Miracle Sudoku [video]

#81

Post by macintux » Wed, May 20, 2020, 12:18 PM UTC

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…

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

Re: The Miracle Sudoku [video]

#82

Post by macintux » Wed, May 20, 2020, 12:20 PM UTC

louisch wrote: post #37

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)

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

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

Re: The Miracle Sudoku [video]

#83

Post by dathinab » Wed, May 20, 2020, 12:32 PM UTC

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.

Re: The Miracle Sudoku [video]

#84

Post by Majromax » Wed, May 20, 2020, 12:42 PM UTC

shultays wrote: post #63

Marazan wrote: post #36

Earlier quoted context omitted.

That doesn't guarantee you that you generate a Sudoku solveable without backtracking. The human techniques are all about forward actions only, never guesses.

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…

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

Re: The Miracle Sudoku [video]

#85

Post by chongli » Wed, May 20, 2020, 12:49 PM UTC

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

Re: The Miracle Sudoku [video]

#86

Post by ghusbands » Wed, May 20, 2020, 12:52 PM UTC

dan-robertson wrote: post #35

jmiskovic wrote: post #12

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.

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.

Re: The Miracle Sudoku [video]

#87

Post by dreamer_soul » Wed, May 20, 2020, 12:55 PM UTC

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

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

Re: The Miracle Sudoku [video]

#88

Post by matsemann » Wed, May 20, 2020, 12:58 PM UTC

matsemann wrote: post #62

swah wrote: post #58

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

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

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

Re: The Miracle Sudoku [video]

#89

Post by yesenadam » Wed, May 20, 2020, 1:03 PM UTC

billfruit wrote: post #64

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

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

Re: The Miracle Sudoku [video]

#90

Post by carlob » Wed, May 20, 2020, 1:09 PM UTC

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.