TE
科技回声
首页24小时热榜最新最佳问答展示工作
GitHubTwitter
首页

科技回声

基于 Next.js 构建的科技新闻平台,提供全球科技新闻和讨论内容。

GitHubTwitter

首页

首页最新最佳问答展示工作

资源链接

HackerNews API原版 HackerNewsNext.js

© 2025 科技回声. 版权所有。

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

244 点作者 Ariarule大约 3 年前

16 条评论

ryeguy_24大约 3 年前
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.<p>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.
评论 #30866538 未加载
评论 #30869185 未加载
评论 #30866095 未加载
评论 #30868949 未加载
cevi大约 3 年前
Phistomefel’s Theorem (and the more general &quot;set equivalence theory&quot; described in the article) pops out directly from a standard technique known as the &quot;Linear Programming relaxation&quot; for Sudoku.<p>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&#x2F;no answers to questions like &quot;is the digit inside this box a 7?&quot; 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.<p>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&#x27;t need ontological remodeling when you know how to apply convex optimization :)
评论 #30866840 未加载
评论 #30871344 未加载
pdpi大约 3 年前
Cracking the Cryptic (the Youtube channel mentioned in the article) is a great channel to follow. Especially Simon&#x27;s videos offer great insight into his thought process solving through some pretty hard sudokus (and variants). They&#x27;ve also taken on different puzzle games (e.g. The Witness, Baba is You), and it&#x27;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.
评论 #30868683 未加载
nwbort大约 3 年前
It&#x27;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大约 3 年前
The author describes a process called &quot;ontological remodeling&quot;, 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.
评论 #30864878 未加载
评论 #30864275 未加载
评论 #30872332 未加载
评论 #30864797 未加载
pjungwir大约 3 年前
&quot;Ontological remodeling&quot; is a lovely term. I think it&#x27;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?<p>Btw is the footnote a joke? I don&#x27;t really get it:<p>The sum of the digits 1 to 9 is 45[1]<p>[1] This is a secret that Simon only tells his closest friends.
评论 #30864834 未加载
评论 #30865655 未加载
评论 #30864835 未加载
评论 #30865384 未加载
评论 #30866457 未加载
评论 #30864847 未加载
评论 #30864926 未加载
shisisms大约 3 年前
The 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.<p>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.
评论 #30864567 未加载
buzzdenver大约 3 年前
For anyone following along the article, it should be &quot;Row 4, Row 7, Box 4, and Box 6&quot; where it says &quot;Row 4, Row 7, Box 4, and Box 7&quot;. Somebody please correct me if I&#x27;m misunderstanding.
评论 #30867392 未加载
JKCalhoun大约 3 年前
If I&#x27;m not mistaken, you can in fact get the same digit three times in the ostrich head.<p>EDIT: I misread the article — it said you can&#x27;t place the same digit <i>more than</i> three times.<p>Such a deep dive on ontological remodeling that I found myself starved for oxygen about the time <i>palindromic lines</i> came up.<p><i>Phistomofel’s Theorem</i> though blew my mind. I&#x27;m still trying to convince myself it is legit. (Probably where I started to think about heading back to the surface.)
评论 #30868359 未加载
escapedmoose大约 3 年前
I don’t even care what the “real-world” implications are; this is just an awesome way to think about Sudoku, and number sets.
Buttons840大约 3 年前
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?
评论 #30866461 未加载
评论 #30865298 未加载
Gravityloss大约 3 年前
I am not familiar with the set theory field, or whatever it&#x27;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.<p>Maybe this is where a science journalist could do a good job! I&#x27;m thinking Vi Hart for example.
评论 #30865559 未加载
jcims大约 3 年前
This feels like it’s related to abstraction but not exactly the same thing. Can’t really put my finger on it.
评论 #30865131 未加载
haunter大约 3 年前
I&#x27;d love to read something similar about nonogram&#x2F;picross
imglorp大约 3 年前
setter: noun. One who does set theory.
aardvark179大约 3 年前
Is 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.