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…]

I read popular physics: A planet is born

This is part of my series where I read physics articles in Scientific American, and offer commentary as a former physicist.

I’ve had the June issue around for over a month, but I procrastinated too much and here we are in July. I’ll try to keep it short this time so I can move on to the next one.

The June issue is when COVID-19 really hits Scientific American. The cover says in big letters: “The Coronavirus Pandemic”. I already got the July issue, and the coronavirus is on the cover of that too. But, the cover notwithstanding, there are still physics articles, and that’s my area of expertise. This month’s article is “A Planet is Born“, by Meredith A. MacGregor.  This one isn’t paywalled so you’re free to read it yourself.

[Read more…]

I read popular physics: The Milky Way

It’s time for another entry in my series where I read through physics articles in Scientific American, now through the eyes of a former physicist. It’s a gratifying exercise because I used to struggle through these when I was in high school. Now, if I struggle, I know it’s not my fault!

Today’s article is “New View of the Milky Way” by Mark J. Reid and Xing-Wu Zheng in the April 2020 issue. Oddly the titles in the print version never seem to match the titles in the online version–also the online version is paywalled this time, that means no images, sorry folks!

The main thrust of the article is that they used radio astronomy to map out the Milky Way galaxy. Now you might think that since we’re inside the Milky Way, we have an especially clear idea of its shape. But it’s surprisingly difficult, because determining the distance of stars is hard, and there are dust clouds in the way. If you’ve ever seen an image of the Milky Way as viewed from the outside, those are all artists’ conceptions and we don’t know what it actually looks like.

So the first thing I see in this article, is an image of the Milky Way, as viewed from outside. At first I thought, this is really neat, finally an image that’s more than just an artist’s conception. But nope, it’s just another artist’s conception. Created to be consistent with the study’s results, but still just art.

[Read more…]

I read popular physics: The cosmic crisis

Someone went and got me a subscription to Scientific American, so for the past few months I’ve been covering physics articles, now with the benefit of a PhD. Perhaps it’s a way to keep in touch with my physics roots as my career has moved on to other things.

In this month’s issue, the cover article is “A Cosmic Crisis“, about a discrepancy between two measurements of the age of the universe.

Funny thing, there’s always a letter from the editor in chief where he introduces all the major articles, and here he contrasts the “cosmic crisis” with another ongoing crisis, that thing between US and Iran. Yep, this sure is an article that was written last month! FWIW, I could do with some reading that has nothing to do with COVID-19.

I thought I’d review the article in approximately the order in which I read it: pretty pictures first, walls of text last if at all. For serious, this is the correct way to read a science article, I can say that as a person with a PhD.

[Read more…]

I read popular physics: Giant Atoms

Someone went and got me a subscription to Scientific American. So I’ve been looking at these popular physics articles, marveling at what they look like post-PhD. I will continue doing this until I get bored.

Today, I will look at an article in the February issue, titled “Giant Atoms”, by Charlie Wood. It’s a short article about the MAGIS-100 experiment, which I was previously unaware of.

I got two main points from the article:

  • The MAGIS-100 experiment drops atoms down a 100 meter vacuum tube, creating “room-length” atom waves.
  • The experiment will eventually be sensitive to gravitational waves, and new forces that interact with dark matter.

[Read more…]

I read about the triple slit experiment

Someone went and got me a subscription to Scientific American, which is nice. Haven’t read one of those since before my PhD. In theory, I should be able to understand it a lot better. In practice, popular articles often omit crucial details or use “creative” explanations that would confuse most professionals.

So I went straight to the physics section and found an article titled “The Triple Slit Experiment” by Urbasi Sinha. Already this has me a bit confused. What’s so special about three slits? And why stop at 3? You can just have slits repeating indefinitely. It’s called a diffraction grating, and I had one when I was a kid (from this book).

Lightbulb as seen through a diffraction grating. A rainbow ring appears around it.

Diffraction gratings turn everything to rainbows, and are great toys. Credit: Wikimedia Commons

So I looked through the article to see what was going on. The article makes three main points:

[Read more…]

Intrinsic value of choice

I know that this question has practical and political implications, but for now, I’m treating it as a “just for fun” philosophical question.  Just wanted to be upfront.

What is the value of freedom of choice?  Does it have intrinsic value, or is its value purely instrumental?

A thing has “intrinsic value” if it is valuable in itself.  It has “instrumental value” if it is valuable because it is a means to get something else of value.  For instance, suppose we have a choice between mushroom and cheese pizza.  This choice has instrumental value, because it’s a means for people to have the kind of pizza they most prefer.  But does the choice also have intrinsic value?

Under an initial analysis, I thought the answer was “no”.  If I’m presented with a one-time choice between A and B, and I choose A, did the other option B do any good?  At least within a consequentialist ethical framework, it sure doesn’t seem like it.  After all, option B had no bearing on the consequences.

[Read more…]