Logic puzzles, overexplained

By “logic puzzle”, I don’t just mean puzzles involving logic, but rather a specific genre of puzzles, whose most famous types are Sudoku and Picross. There are many other types of such puzzles, and creators of logic puzzles can create entirely new types, if they are so inclined. If you’re not sure what I’m talking about, or if you’re just interested in finding logic puzzles, at the bottom of this post I’ve included a list of places you can find them.

I’m fairly good at logic puzzles. I’ve done the US Puzzle Championship for over a decade, and I placed in the top 25 once? So not like top-of-the-world good, but decent. And I’m a generalist, which is to say that relatively speaking I’m not very good with Sudoku, and I do better with other types of puzzles, including entirely new types.

My goal here is to overexplain my understanding of logic puzzles, and solving strategy. I am not confident that this is actually helpful to someone trying to get better at solving logic puzzles, but that’s not really the point. The point is to explicitly describe what would otherwise only be understood intuitively.

[Read more…]

The physics of jigsaw puzzles

Wholesome jigsaw puzzle youtuber Karen Kavett recently did a challenge where she assembled a 1000 piece puzzle by selecting 100 pieces at random at a time. For a while, this just looked like a bunch of scattered pieces with only a few connections. But once she had 700 or 800 pieces, the whole puzzle started to come together, despite the gaps.

I found this fascinating, because it is a live demonstration of a concept in physics/math: the percolative transition. This is something I often think about when assembling puzzles.

[Read more…]

Computational complexity of jigsaw puzzles

During the pandemic, I started doing more jigsaw puzzles. Not real puzzles mind you—I found a jigsaw simulator on Steam that was fairly authentic to the real experience. And since I was doing jigsaw puzzles through the medium of video games, I couldn’t help but think about them in the context of puzzle video games. I realized, jigsaw puzzles are kind of weird! In your typical puzzle video game, the ideal is to have a set of levels, each of which require some crucial insight. In contrast, a jigsaw puzzle is more like a large task that you chip away at.

One way of thinking about this is through the lens of computational complexity. Take Sokoban, the classic block pushing puzzle upon which many puzzle video games are founded. In general, a Sokoban puzzle of size N requires exp(N) time to solve, in the worst case. However, the typical Sokoban puzzle does not present the worst case, it presents a curated selection of puzzles that can be solved more quickly. This gives the solver an opportunity to feel clever, rather than just performing a computation.

Jigsaw puzzles, on the other hand, are about performing a computation. And, if you wish to do a large jigsaw puzzle in a reasonable amount of time, you look for ways to perform that computation efficiently. This raises the question: what is the computational complexity of a jigsaw puzzle?

According to the open access paper, “No easy puzzles: Hardness results for jigsaw puzzles” by Michael Brand, realistic jigsaw puzzles require Θ(N2) steps both in the worst case and on average. On the other hand, this is not born out by my own statistics, which seem to fit a straight line.

[Read more…]

Review scores: a philosophical investigation

Normally, in the introduction to an article, I would provide a “hook”, explaining my interest in the topic, and why you should be too. But my usual approach felt wrong here, since I cannot justify my own interest, and arguably if you’re reading this rather than scrolling past the title, you should be less interested than you currently are.

So, review scores. WTF are they? I don’t have the answers, but I sure have some questions. Why is 0/10 bad, 10/10 good, and 5/10… also bad? What goals do people have in assigning a score, and do they align with the goals of people reading the same score? What does it mean to take the average of many review scores? And why do we expect review scores to be normally distributed?

Mathematical structure

Review scores are intuitively understood as a measure of the quality of a work (such as a video game, movie, book, or LP)–or perhaps a measure of our enjoyment of the work? Already we have this question: is it quality, or is it enjoyment, or are those two concepts the same? But we must leave that question hanging, because there are more existentially pressing questions to come. Review scores do more than just express quality/enjoyment, they assign a number. And numbers are quite the loaded concept.

[Read more…]

From the Archives: Evaluating FiveThirtyEight

This is a repost of a simple analysis I did in 2012, evaluating the presidential predictions of FiveThirtyEight.  What a different time it was.  If readers are interested, I could try to repeat the analysis for 2020.

The news is saying that Nate Silver (who does election predictions at FiveThirtyEight) got fifty states out of fifty. It’s being reported as a victory of math nerds over pundits.

In my humble opinion, getting 50 out of 50 is somewhat meaningless. A lot of those states weren’t exactly swing states! And if he gets some of them wrong, that doesn’t mean his probabilistic predictions were wrong. Likewise, if he gets them right, that doesn’t mean he was right.

[Read more…]

A 2D voting sim

I made a Monte Carlo voting simulation. No particular reason, I just think it’s neat.

Okay, so I was thinking about the Median Voter Theorem, which says that the winning position in an election is the position of the median voter. Of course, this conclusion only holds under certain assumptions, and none of those assumptions are actually true. And yet the conclusion is approximately correct in many situations. That’s why we care disproportionately about the median congress members (like Susan Collins), the median Supreme Court Justices (like Roberts), and the median “swing” states (like Pennsylvania).

But it should be obvious that the median voter fails in a lot of ways. In particular, it doesn’t predict the political polarization that occurs in US politics. And there are plenty of possible explanations: voter turnout, third parties, primary elections, politician’s charisma factors, multidimensional political spectra, and so on. But I’m not sure which among those explanations are most important.

The voting simulation won’t answer any of these questions, I’m just setting the context. One of the assumptions of the Median Voter Theorem is that political preferences exist along only one dimension. I thought I’d try running simulations with two dimensions to see what would happen, and to make some pretty graphs.

Plot showing all the voters and candidates along a two dimensional spectrum.

Voters and candidates in a 2D space

[Read more…]

A music theory analysis of SUNN O)))

I’ve complained before about music theory, and how it fails to actually address any of the music I actually like. One kind of music I have in mind is drone music. Consider, for instance, this reddit thread on the music theory of SUNN O)))

Honestly most drone is fifths and minor scales, it’s not really complicated.

The attitude being expressed is that drone music is too simple to require any music theory. This is a failure to engage with the music on its own terms. If that’s all there is, then what, pray tell, distinguishes different songs and artists? Are they just all interchangeable?

While it may be the case that drone music is particularly simple, I feel that this only makes the lack of a music theory all the more frustrating. Most music theory is frankly too complicated for me to understand, and it would actually be nice to have some simple music theory for once, if only music theorists didn’t think it was beneath them. In any case, I think the theory behind drone music is likely more complicated than they are making it out to be. Drone is highly preoccupied with texture (aka timbre)–a subject so difficult that music theory as a field has basically given up on it.

Anyway, in the spirit of being the change I want to see, I analyzed the spectrograms of a couple SUNN O))) songs.

[Read more…]