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

What do new Sudoku techniques teach us about real-world problem solving?

desystemize.substack.com

Post reply on HN
Print view View original

61–70 of 71 posts

Re: What do new Sudoku techniques teach us about real-world problem solving?

#61

Post by fsckboy »

markisus wrote: post #3

The author describes a process called "ontological remodeling", which is when a change in viewpoint radically simplifies a previously intractable problem. This is the story, not just of Sudoku, but all of mathematics.

> "ontological remodeling", which is when a change in viewpoint radically simplifies a previously intractable problem. This is the story, not just of Sudoku, but all of mathematics.

it's such a powerful tool that the only problem it leaves is, what benefit is there to calling it ontological remodeling instead of "a change in viewpoint"?

Re: What do new Sudoku techniques teach us about real-world problem solving?

#62

Post by vikingerik »

pjungwir wrote: post #50
WithinReason wrote: post #25

Earlier quoted context omitted.

Also, using a similar trick as with the dominoes, can a certain Legend of Zelda puzzle be solved? https://gazj.substack.com/p/python-and-the-legend-of-zelda?s... Article doesn't contain a mathematical proof (only a brute force one), but I wrote one up. Spoilers: https://news.ycombinator.com/item?id=30639211

That's a cool puzzle! It's the same as the Bridges of Königsberg, right? If each square is a node, connected by edges to adjacent squares, then it's only solvable if there are at most two squares with an odd number of edges. Think about it like this: except for the squares where you start and finish, you must use one edge to enter and another to leave. I guess the Zelda puzzle is different because in Königsberg you c…

The Zelda puzzle isn't the same as Königsberg because in Königsberg the goal is to traverse every edge, while the Zelda puzzle doesn't care about that. Think about the rows of tiles along the edges of the room - the Zelda room has dozens of tiles with 3 edges each, but it's no problem walking across them exactly once. You enter each tile from one edge and leave by a second, and it doesn't matter if you never traverse the third edge.

Swapping nodes and edges doesn't work, because many of the Zelda nodes have 3 or 4 edges, but an edge is defined as 2 endpoints. It doesn't make sense to talk about an edge with 3 or 4 ends.

The proof of non-solution to the Zelda puzzle is a simple checkerboard argument. The room's dimensions are 13 x 9, both odd, so all the corners are the same color (call it black) and there is one more black square than white. And the prize square replaces a white square. So there are two more black squares than white squares, making the problem unsolvable, since you must always alternate visiting white and black squares. The statues are a red herring - there are two on each color and so they don't affect this proof.

Re: What do new Sudoku techniques teach us about real-world problem solving?

#63

Post by yen223 »

jamincan wrote: post #53
pdpi wrote: post #42

Cracking the Cryptic (the Youtube channel mentioned in the article) is a great channel to follow. Especially Simon's videos offer great insight into his thought process solving through some pretty hard sudokus (and variants). They've also taken on different puzzle games (e.g. The Witness, Baba is You), and it's absolutely fascinating to see how being very highly skilled in solving one type of puzzle does or does not…

I occasionally watch Simon on Cracking the Cryptic and find it interesting how different his approach to solving Sudoku is to mine. I wouldn't even be able to start most of the puzzles he does, but nevertheless, I almost always find myself yelling at him in my head at some point where I see something so obvious to me that he overlooks.

I would "yell at the screen" whenever he misses things. Then I realised that he still solves these puzzles much faster than I did, which makes me realise he probably just better than me at paying attention to the parts that are important to the solve.

Re: What do new Sudoku techniques teach us about real-world problem solving?

#64

Post by lupire »

gravenimage wrote: post #10
pjungwir wrote: post #9

"Ontological remodeling" is a lovely term. I think it's ubiquitous actually, but another nice example is the puzzle about tiling a chessboard with dominoes when the board is missing two opposite corners. Can you do it? If so, how? If not, why not? Btw is the footnote a joke? I don't really get it: The sum of the digits 1 to 9 is 45[1] [1] This is a secret that Simon only tells his closest friends.

Using the 'secret' is a common way of deriving further digits in a Sudoku - if you know the sum of digits in a row or a box has to be X, then the missing digits must sum to 45-X. In the 'Cracking The Cryptic' videos, Simon is always careful to explain this, and always prefaces it with a warning that he only tells it to his closest friends (all 400k of them).

It's a joke. The numerical value of the digits has no meaning. There is no addition in sudoku.

Re: What do new Sudoku techniques teach us about real-world problem solving?

#65

Post by cevi »

sischoel wrote: post #43
cevi wrote: post #34

Phistomefel’s Theorem (and the more general "set equivalence theory" described in the article) pops out directly from a standard technique known as the "Linear Programming relaxation" for Sudoku. Essentially, the Linear Programming relaxation of a puzzle is a standard way of approximating the solution space with a system of linear equations and inequalities, replacing discrete yes/no answers to questions like "is the…

Do you know any sources on on how set equivalence theory is related to integer programming? Because I don't see the immediate connection and I could not find anything on the internet, but maybe I used the wrong terms.

I don't know any reference for this - it's something I worked out after hearing about Phistomefel's Theorem from a friend. The idea goes like this:

The standard Linear Programming relaxation of the constraint "the nine variables x_1, ..., x_9 are a permutation of 1, ..., 9" is defined in the following way. First we make real variables p_ij which we think of as representing the "probability" that x_i is equal to j. Each p_ij has to be between 0 and 1, of course, and they have to satisfy the following system of linear equations:

- for each i, the sum over j of p_ij is equal to 1 (since every x_i has to have some value), and

- for each j, the sum over i of p_ij is equal to 1 (since every value from 1, ..., 9 has to show up in the list of x_is somewhere).

The fact that this system of equations, together with the inequalities 0 To describe the full Linear Programming relaxation of Sudoku, instead of just having 9 variables x_i you have 81 variables x_ab, which leads to 729 real "probability" variables p_abj between 0 and 1, and for each row, column, and square of the Sudoku these probabilities have to satisfy the equations listed above (applied to the relevant variables). That gives you a system of 324 (slightly redundant) linear equations in 729 unknown real variables p_abj, each of which is constrained to be between 0 and 1 - a piece of cake for a computer.

For a human, you don't want to write down that entire system of equations - you want to use just a few of them to quickly figure out some piece of the puzzle. The technique of set equivalence theory does just this: instead of focusing on all of the probabilities p_abj, you just use the fact that the sum of the probabilities p_ab1 along every row/column is 1, and add/subtract the equations you get from some rows and columns to notice that the sum of the p_ab1s for the (ab)s corresponding to the corners is equal to the sum of the p_ab1s for the (ab)s corresponding to the ring around the center. Then you do the same for the 2s, and so on.

Re: What do new Sudoku techniques teach us about real-world problem solving?

#66

Post by cevi »

zem wrote: post #60
cevi wrote: post #34

Phistomefel’s Theorem (and the more general "set equivalence theory" described in the article) pops out directly from a standard technique known as the "Linear Programming relaxation" for Sudoku. Essentially, the Linear Programming relaxation of a puzzle is a standard way of approximating the solution space with a system of linear equations and inequalities, replacing discrete yes/no answers to questions like "is the…

set equivalence is something a human can do while solving the puzzle, though, and forming overlapping sets and then removing the common elements is very satisfying when you hit on the right sets. (hitting on the right sets is hard, and needs a good feel for the specific constraints in the grid. mark and simon are, of course, very good at it.)

Agreed on all counts.

Re: What do new Sudoku techniques teach us about real-world problem solving?

#67

Post by sellyme »

lupire wrote: post #64
gravenimage wrote: post #10

Earlier quoted context omitted.

Using the 'secret' is a common way of deriving further digits in a Sudoku - if you know the sum of digits in a row or a box has to be X, then the missing digits must sum to 45-X. In the 'Cracking The Cryptic' videos, Simon is always careful to explain this, and always prefaces it with a warning that he only tells it to his closest friends (all 400k of them).

It's a joke. The numerical value of the digits has no meaning. There is no addition in sudoku.

There is plenty of addition in modern sudoku, as visible in the example shown in the linked article featuring killer cages.

Re: What do new Sudoku techniques teach us about real-world problem solving?

#68

Post by [deleted] »

fsckboy wrote: post #61
markisus wrote: post #3

The author describes a process called "ontological remodeling", which is when a change in viewpoint radically simplifies a previously intractable problem. This is the story, not just of Sudoku, but all of mathematics.

> "ontological remodeling", which is when a change in viewpoint radically simplifies a previously intractable problem. This is the story, not just of Sudoku, but all of mathematics. it's such a powerful tool that the only problem it leaves is, what benefit is there to calling it ontological remodeling instead of "a change in viewpoint"?

[deleted]

Re: What do new Sudoku techniques teach us about real-world problem solving?

#69

Post by sriram_malhar »

orlp wrote: post #18
rhdunn wrote: post #13

Earlier quoted context omitted.

3Blue1Brown has a few videos where he discusses and uses this technique to solve some complex problems. One of those was for a mathematical competition. It's also common in audio manipulation, e.g. change to the frequency domain in order to modify pitch, then change back to the time domain.

> It's also common in audio manipulation, e.g. change to the frequency domain in order to modify pitch, then change back to the time domain. Funnily enough, yes but actually no. For understanding and mathematical proofs the Fourier Transform is obviously essential. But when you first get into audio DSP programming it might seem that the FFT is crucial as well. But virtually all digital audio filters directly operate…

Excellent explanation. Thank you!

Re: What do new Sudoku techniques teach us about real-world problem solving?

#70

Post by 112233 »

10000truths wrote: post #46
orlp wrote: post #18

Earlier quoted context omitted.

> It's also common in audio manipulation, e.g. change to the frequency domain in order to modify pitch, then change back to the time domain. Funnily enough, yes but actually no. For understanding and mathematical proofs the Fourier Transform is obviously essential. But when you first get into audio DSP programming it might seem that the FFT is crucial as well. But virtually all digital audio filters directly operate…

Is there any scenario where the discrepancy between FFT and its analog cousin cannot be resolved by upping the sampling density? Distortion is always there, whether it comes from an imprecise sensor/instrument or from extrapolating sampled data. In the audio space, nothing above 20 kHz is audible anyways, so even a bog-standard 44.1 kHz sampling rate should do "good enough" for most DSP operations there.

Transients. FFT is time-symmetrical, so signals that start because of an event (like a mallet hitting something) have a lot of "nothing audible "above 20kHz", because of the abrupt start. Forcing nyquist limit on such signal alway causes pre-ringing, that breaks causality - you have sound starting before the event happened.

(edit) e.g. bandwidth limited signal with only a single non-zero sample does not represent a rectangular function, but a sinc.

So, FFT is a lie. But very useful one.

Post reply on HN