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

Art, success, and rewards

I recently read a story where an artist sold a recording for a flat fee, and then the song went on to become hugely popular, but the artist didn’t receive any royalties. It’s a familiar story of exploitation, especially of Black artists who systematically receive less credit than they are due in American music.

However, I was distracted by an alternative interpretation that came to mind. To some extent, the rights to royalties for a song is essentially a lottery ticket. Song popularity follows a power law distribution (I presume, based on how these things usually work), so that a few songs become extremely successful while the vast majority remain in obscurity. It makes sense to want to sell your lottery ticket–provided that you get a fair price for it. If you have a losing ticket–as most people do–then selling that losing ticket is a way to still make money.

[Read more…]

Game Diary: Feb 2021

On Pillowfort, I’ve been writing a “video game diary” where I write mini-reviews of video games I’ve played recently (or watched my husband play). This diary is the inspiration of a few of my articles, including “Bugsnax’s twofold queerness” and “Practice and sight-reading in video games“. Since Pillowfort has been down for an extended period, it seems like a good time to try importing the feature here. I’m just calling it “game diary” because I might occasionally include a board game.

I may or may not decide to continue this feature on this blog, so let me know if you like it.

[Read more…]

Blogging and ambition

When I started blogging in 2007, I had ambitions of being popular blogger with a certain amount of authority. Those ambitions burnt out within a year or two, as I realized I did not actually want to be a famous blogger, and would rather satisfy my own preferences in blogging. Why did I have such ambitions, and why did they burn out? More broadly, how do other creators experience ambition, and are there differences from my own experience?

Okay, so 2007. Towards the end of the Bush administration, when Bush reached peak disapproval. New atheism was just getting rolling, and blogs held a particularly important place in the conversation, much like lefttube or twitter hold an important place today. I was an undergrad, and had been reading blogs myself, starting with Phil Plait, Hemant Mehta, PZ Myers, and branching off into many smaller ones.

My ambition was to become as well-known as the big names, or perhaps at least one of the smaller ones. It’s hard to remember why I had this mentality, especially since I now see it as irrational. I suppose I had a lot of opinions to share, and believed my opinions were the Good Ones that would transform how we thought about stuff and resolve all the issues that bloggers argued about. I have always been very modest, and though nobody throughout my education would ever let me forget that I am “smart”, I have never felt that my opinions are super valuable just because they are my opinions. Nonetheless, in my experience reading blogs, there were countless places where I thought bloggers and other readers were missing something important, and I felt I could supply that something if only people would hear me.

[Read more…]

Link Roundup: February 2021

This month’s link roundup includes a wide range of articles, from masculinity, to blogging, to commentary on Gamestop.

What Hades Can Teach Us About Ancient Greek Masculinity | Wired – Recommended even if you’re unfamiliar with the game Hades.  And if you’d like to read even more about ancient greek masculinity, I recommend an article by cartomancer a while back.  Among other things, I was amused to learn that classical observers disagreed on whether Achilles was the erastes or eromenos in his relationship with Patroclus.  It’s like the ancient version of an argument over which character is the top and which is the bottom.

My Life as a Failed Pundit | Tris Mamone – I enjoyed this first-person account of the stress that comes from trying to have an opinion about everything.  I don’t consider myself a pundit, I’m an analytical blogger.  There’s some superficial similarity, but I don’t feel the need to comment on any of the hot topics of the day, because nobody is paying me to do so.

[Read more…]

Origami: First cubes

I try to post origami every month, but as of late, my rate of production has been less than that.  That’s okay, I still have a huge backlog of photos.  One thing I’ve never posted, are my very earliest photos, when I started doing modular origami in………. 2012.  Well here’s the very first one:

sonobe cube

Sonobe Cube, by Mitsunobu Sonobe

I started out by folding designs from Beginner’s Book of Modular Origami Polyhedra: The Platonic Solids by Rona Gurkewitz and Bennett Arnstein–it’s not the book in the photo, it’s more beginner-friendly than that.  It’s a good starter book for modular origami, I recommend it.

I didn’t dedicate much effort to the photos at the time.  The book is there because that’s what I had on the shelf.  I put my hand in the photo to give it a sense of scale; also, as if to say “Zap!  A cube!”  I went on to zap more cubes from there on.

[Read more…]