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

31–40 of 71 posts

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

#31

Post by selestify »

iso1210 wrote: post #28
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…

That's depressing - the sudoku craze was nearly 2 decades ago.

Why is that depressing?

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

#33

Post by ykonstant »

rhdunn wrote: post #13
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.

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.

Since 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 . I highly recommend watching it, I think it is one of his best.

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

#34

Post by cevi »

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 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 :)

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

#36

Post by tromp »

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.

> a chessboard with dominoes when the board is missing two opposite corners.

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.

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

#37

Post by conv »

Buttons840 wrote: post #20

Makes 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?

Here is another experiment where you can hand-tune the weights of a neural network for a regression problem: https://asdf10.com/nn.html

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

#39

Post by Existenceblinks »

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

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

#40

Post by rhdunn »

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…

That's fascinating. Thanks for the information.
Post reply on HN