9 ms·
What do new Sudoku techniques teach us about real-world problem solving?
- nwbort 5y agoIt's been pretty amazing to watch the evolution of sudoku theory over even the last two years, some truly genius work by eg Phistomofel, Aad van de Wetering, Totally Normal Cat as well as the enormous contribution of Cracking the Cryptic
- markisus 5y agoThe 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.
- barathr 5y agoChapman's writings on the subject are worth a read: https://metarationality.com/remodeling https://metarationality.com/remodeling
- marmshallow 5y agoIndeed. After reading the title of the post, I thought it may be about the Cook-Levin theorem, which is about how all NP problems (of which Sudoku is one) can be reduced to one another.
- rhdunn 5y ago3Blue1Brown 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.
- orlp 5y ago> 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.
- rhdunn 5y agoThat's fascinating. Thanks for the information.
- 10000truths 5y agoIs 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.
- orlp 5y ago> Distortion is always there, whether it comes from an imprecise sensor/instrument or from extrapolating sampled data. Specifically regarding the latter part of "extrapolating sampled data", I would highly recommend watching this video: https://xiph.org/video/vid2.shtml 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.
- 112233 5y agoTransients. 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.
- skybrian 5y agoI'm just using simple IIR filters because it's one float of storage and one line of code, but I'm curious: which filtering algorithms are you talking about?
- ykonstant 5y agoSince you mention it, 3b1b has a splendid video juxtaposing two attitudes to problem solving via an example here: https://www.youtube.com/watch?v=ltLUadnCyi0 https://www.youtube.com/watch?v=ltLUadnCyi0 . I highly recommend watching it, I think it is one of his best.
- fsckboy 5y ago> "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 5y ago[deleted]
- shisisms 5y agoThe extrapolated concept is great for life in general. Quite literally use different vocabulary to reframe an existing challenge to force a shift in perspective and thereby arrive at a different problem. 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.
- CollinLysford 5y agoThe article I link at the beginning of this one, Representation and Uncertainty, is about exactly this - how to think about the extrapolated concept of representation for life in general. Self-promo I know but I think anyone who resonates with your comment would really enjoy it: https://desystemize.substack.com/p/representation-and-uncertainty?s=w https://desystemize.substack.com/p/representation-and-uncert...
- shisisms 5y agoThat wasn’t skimmable, lol. But a striking point no-less. 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 :)
- jcims 5y agoThis feels like it’s related to abstraction but not exactly the same thing. Can’t really put my finger on it.
- iainmerrick 5y agoIt strikes me as a kind of modularisation. There's a constraint on the solution that involves dozens of rows, columns and boxes in combination; but you can treat combinations of that style as a reusable module, like "center ring and corners". 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.
- pjungwir 5y ago"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.
- tomstuart 5y agoYes, it’s a joke. Simon discloses “the secret” in almost every video, so the joke is that it’s always presented as mysterious insider knowledge even though it’s clearly not.
- gravenimage 5y agoUsing 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).
- twiceaday 5y ago"A secret I only tell my friends" is how Simon usually introduces 1 to 9 sum to 45 when he needs that fact to explain his train of thought in Cracking the Cryptic videos.
- deleted 5y ago
- Gravityloss 5y agoI am not familiar with the set theory field, or whatever it's called more exactly. The language in the article, from a layman point, is vague, and I think also uses many words that have somewhat a different meaning to their mainstream one that it makes it pretty much impossible to read for me. Maybe this is where a science journalist could do a good job! I'm thinking Vi Hart for example.
- zem 5y agohttps://www.youtube.com/watch?v=e9_FkcNAZcA https://www.youtube.com/watch?v=e9_FkcNAZcA and scroll to 9:20 if you want to watch simon explain phistomefel's theorem
- Gravityloss 5y agoThanks, a good and patient explanation!
- Buttons840 5y agoMakes me wonder, if we were able to make a fun puzzle out of training machine learning models by hand, would we soon find better training algorithms?
- milliams 5y agoHere's a fun experiment along those lines: https://koaning.github.io/human-learn/ https://koaning.github.io/human-learn/ It's not a game, but it is investigating how having a human in the loop can improve ML models.
- conv 5y agoHere is another experiment where you can hand-tune the weights of a neural network for a regression problem: https://asdf10.com/nn.html https://asdf10.com/nn.html
- ryeguy_24 5y agoI took an AI class back in college 16-17 years ago. In that class we had to solve a sudoku puzzle using multiple approaches to find the fastest approach (backtracking, backward propagation, forward propagation) for a few difficult puzzles. 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.
- iso1210 5y agoThat's depressing - the sudoku craze was nearly 2 decades ago.
- selestify 5y agoWhy is that depressing?
- techer 5y agoIt seems/feels rather recent…
- Ensorceled 5y agoBecause I'm 20 years older?
- Existenceblinks 5y agoI don't think I remember implementation detail of any algorithm I learned in AI class (for me, it's just 13 years ago). If I'm going to do it today, I'd have to re-read its concept again. ps; all projects, I did it by myself, and my friends just sit watching and collecting grade.
- snarf21 5y agoVery true. Wisdom is knowledge applied.
- 5y ago
- aardvark179 5y agoIs this really a new technique? Dividing a puzzle up into a different set of regions that can still be reasoned about is something I’ve done occasionally while solving them, and I’ve definitely done it while designing and generating puzzles because it can really help cut down the degrees of freedom.
- cevi 5y agoPhistomefel’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 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 :)
- sischoel 5y agoDo 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.
- cevi 5y agoI 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 <= 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.
- haunter 5y agoI'd love to read something similar about nonogram/picross
- imglorp 5y agosetter: noun. One who does set theory.
- pdpi 5y agoCracking 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 translate into other classes of puzzle.
- jamincan 5y agoI 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.
- jamie_ca 5y agoYeah, he's commented many times that his scanning is sometimes terrible (especially I notice when he's working with brand-new puzzle mechanics), but I remain super impressed at his ability to not only work out the complex logic, but do it (a) mostly in his head when there's no easy way to notate it on screen while (b) simultaneously explaining it to viewers in a very understandable fashion.
- yen223 5y agoI 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.
- buzzdenver 5y agoFor anyone following along the article, it should be "Row 4, Row 7, Box 4, and Box 6" where it says "Row 4, Row 7, Box 4, and Box 7". Somebody please correct me if I'm misunderstanding.
- escapedmoose 5y agoI don’t even care what the “real-world” implications are; this is just an awesome way to think about Sudoku, and number sets.
- JKCalhoun 5y agoIf I'm not mistaken, you can in fact get the same digit three times in the ostrich head. 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.)
- RyanCavanaugh 5y agoThe article says "No digit can appear in the ostrich head _more than_ three times."
- deleted 5y ago[deleted]