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

51–60 of 71 posts

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

#51

Post by RyanCavanaugh »

JKCalhoun wrote: post #49

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

The article says "No digit can appear in the ostrich head _more than_ three times."

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

#52

Post by skybrian »

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…

I'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?

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

#53

Post by jamincan »

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.

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

#54

Post by snarf21 »

ryeguy_24 wrote: post #27

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

Very true. Wisdom is knowledge applied.

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

#55

Post by sandworm101 »

ryeguy_24 wrote: post #27

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

I'd be interested in whether solving them via brute force would be faster or slower than any AI-based technique. A first glance at the problem would say no, but if you started in from each corner sequentially then it shouldn't be into the billions.

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

#56

Post by jamie_ca »

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.

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

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

#57

Post by finnh »

sandworm101 wrote: post #55
ryeguy_24 wrote: post #27

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

I'd be interested in whether solving them via brute force would be faster or slower than any AI-based technique. A first glance at the problem would say no, but if you started in from each corner sequentially then it shouldn't be into the billions.

By AI-based do you mean "something with heuristics"? IIRC Algorithm X / Dancing Links is the main way to brute-force it quickly.

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

#58

Post by orlp »

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.

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

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

#59

Post by orlp »

skybrian wrote: post #52
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…

I'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?

That's almost the beauty of a lot of audio DSP filters. They can be 1-10 lines of code, but to understand why they work and how to create similar ones with properties you want you need a heavy math background and a 500+ page book (e.g. https://www.native-instruments.com/fileadmin/ni_media/downlo...).

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

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

#60

Post by zem »

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.)
Post reply on HN