What do new Sudoku techniques teach us about real-world problem solving?
desystemize.substack.com
desystemize.substack.com
I definitely don’t remember much of the content in any of my college courses. But I could reimplement those algorithms today without a problem. It’s amazing how “doing” really contributes to good memory retention. It was also one of the projects that sparked a fire in me. It really showed me the possibilities of computers and computer science.
ps; all projects, I did it by myself, and my friends just sit watching and collecting grade.
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 digit inside this box a 7?" with real numbers between 0 and 1 (which can be interpreted as probabilities, if you like). This system of linear inequalities and equations can then be solved efficiently with techniques from convex optimization.
Even the example from the Cracking the Cryptic video, with the conclusion that those three boxes at the bottom have to be 1, 2, and 3 in some order, would be deduced immediately from the Linear Programming relaxation of Sudoku. You don't need ontological remodeling when you know how to apply convex optimization :)
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 <= p_ij <= 1, corresponds exactly to the "convex hull" of the constraint that the x_i are a permutation of 1, ..., 9 is a fairly famous early result from the theory of the Linear Programming relaxation of the bipartite matching problem.
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.
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 on the on the time domain.
The problem is that we always work with a sampled signal. And while the Nyquist theorem tells us that as long as our sample frequency is at least twice as high as the highest frequency in our input that our sampling doesn't lose any information, we still have to be aware of it.
When you convert a fixed frequency sampled signal into the frequency domain, you get a sum of a fixed set (co)sine functions, because we're still sampled. Now some operations you can do in this frequency domain exactly and simply. E.g. if 100Hz is part of our fixed set of functions and we wish to subtract a 100Hz signal, we can directly do that on our coefficient. A pitch shift by an exact multiple of the frequency sample delta is possible exactly too, assuming the lowest/highest frequencies shifted off are inaudible.
But you almost never want to do these operations. A classic example of something you might want to do is a low-pass filter. Simple right? FFT to frequency domain, zero out the coefficients above the cutoff frequency, and convert back. No! Zeroing out coefficients is equivalent to subtracting those specific sine waves. But that is not a low-pass. As an example, suppose our sample frequency is such that the FFT's sine wave coefficients are 10Hz apart, and we wish to do a 30Hz low-pass filter. This means that a 25Hz signal should be completely unaffected, but a 25Hz signal can't be represented just using the 10Hz and 20Hz coefficients - you need higher order terms! Thus if we zero those out, we distort our 25Hz signal.
So to solve this in the real-world you get into the difficult topic of filter design, or other audio DSP algorithms that are vastly more involved than a simple FFT.
Specifically regarding the latter part of "extrapolating sampled data", I would highly recommend watching this video: https://xiph.org/video/vid2.shtml. As long as your input signal is low-passed to below 22kHz, the 44.1kHz sampling is perfect. No information is lost, no distortion.
I however am not qualified enough to tell you how the naive FFT filter approach changes in distortion as you raise the sampling frequency.
(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.
Other complicated DSP algorithms I've read about (but haven't come close to fully grokking) are:
- Band-limited oscillators. Ask yourself, how do you generate a square wave signal? It's "just" 1 for t seconds and -1 for t seconds, repeating, right? But what if t isn't a multiple of our sampling frequency? Also, a square wave can be interpreted as an infinite sum of ever increasing frequency sine waves. But Nyquist tells us we can't have those higher frequencies. So even if t was a multiple of our sampling frequency, it still wouldn't be right to have t/f samples of 1 followed by t/f samples of -1. But just taking the first N terms of the infinite sum (those below Nyquist) is slow, so you get things like polyblep: https://www.kvraudio.com/forum/viewtopic.php?t=375517.
- Resampling. So a sampled bandlimited signal is perfectly represented by the samples through the Whittaker–Shannon interpolation formula. To resample we simply have to pick equidistant samples using the interpolation formula. However this is slow (and global, so not real-time), so there's a bunch of techniques to speed this up with minimal distortion: http://ldesoras.free.fr/doc/articles/resampler-en.pdf
- Pitch shift. This seems innocuous enough, right? But suppose it were easy to shift pitch. Then we could resample our audio to 2x the frequency, shift the pitch up by an octave and play back at the original speed. Now we've made our audio twice as long without changing the pitch! Pitch shifting and timescaling are two sides of the same coin. And I don't understand either side. Fundamentally I don't really understand what it means to make an audio signal "longer", without changing the pitch, at the waveform level. But people do it anyway: https://en.wikipedia.org/wiki/Audio_time_stretching_and_pitc...
- The rabbit hole goes on...
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"?
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.
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
I guess the Zelda puzzle is different because in Königsberg you can revisit islands, just not recross bridges. But that feels like something you can finesse somehow. . . . Ah, just swap nodes & edges, right? Squares : bridges :: sides : islands. Indeed, that lines up not just the restriction but the goal too.
EDIT: Oh your second link is a much nicer solution. But still it feels like there is a relationship to Königsberg.
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.
A tricker version asks what square remains (unique up to symmetry) when covering a chessboard with 21 trominoes, each of which covers 3 adjacent board squares, i.e. 1x3 or 3x1.
A quite simple observation by the article on how perhaps to approach challenging life issues as well as say mathematical ones. As shifting perspectives when in the trenches of complex life challenges is really hard.
Put another way, a lot of the economic advantages of “problem solving” in big tech in particular is so dangerously devoid (or “bankrupt” as you state) of suitable representation that the framing leads to the dangerous social precipice we now find ourselves in.
It’s questions without representation, with lowly symbolism if any at all.
Eg “connecting people” is a useless solution without the correct representation.
I hope I didn’t totally miss your point :)
EDIT: I misread the article — it said you can't place the same digit more than three times.
Such a deep dive on ontological remodeling that I found myself starved for oxygen about the time palindromic lines came up.
Phistomofel’s Theorem though blew my mind. I'm still trying to convince myself it is legit. (Probably where I started to think about heading back to the surface.)
Maybe this is where a science journalist could do a good job! I'm thinking Vi Hart for example.
I'm not sure that's an accurate way of thinking of it, but if so it would make it similar to Rubik's Cube moves, where you string dozens of individual low-level moves together to build the desired effect.
Edit to add: hmm, thinking about it, many Cube moves have the form A-B-A', where you get into position with A, apply the key move B, then back out of A again. The Sudoku equivalent might be applying a grid permutation A that preserves the constraints, solving cell B, then backing out of A again. But that's probably not a convenient way for human solvers to think about it, as you can't physically permute a Sudoku like you can with a Cube.