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

[cn: This review is spoiler-free. I can’t speak for the comments.]

Obduction is a new game by the team that brought us Myst. Having played all the Myst games when I was younger,* I ended up buying Obduction, and almost immediately regretted it.

Hear me out, it’s not that it’s a bad game. It just reminded me of why I think retro pixelated games are so popular these days. Game creators can advertise high-quality graphics all they want, but ultimately the hardware required to render these graphics is sold separately. In many ways, this game had uglier graphics than Myst IV. I had to put the graphics on the lowest settings, deal with terrible frame rates, and sit through lots of long loading screens. My advice: bring a book.

That aside (and also putting aside numerous other technical issues), Obduction is an okay game. The main attraction is the story. Just sharing a bit of the game’s introduction: you find yourself teleported to a strange world, a deserted mining town surrounded by an alien landscape. You have to use environmental clues to figure out both the mechanics of the sci-fi world, as well as the events leading up to the desertion. But it’s not all mystery and sci-fi, it’s also about the human angle.

4215obduction-1024x740

Image credit: Cyan

[Read more…]

Paper: The Chaos within Sudoku

The Chaos within Sudoku” is a paper about solving Sudoku puzzles with physics. They simulate an imaginary physical system, let it run, and when it stops the puzzle is solved. See the video below:

The thing about Sudoku is that Sudoku is hard. More specifically, when Sudoku is generalized to grids of arbitrary size, it’s NP-complete. What happens when you translate an NP-complete problem to a physical simulation? The authors find chaotic dynamics.  And in the process, they identify the hardest Sudoku puzzle…
[Read more…]

A puzzle snob reviews The Witness

(Content note: this is a spoiler-free review, though I can’t speak for commenters.)

The Witness is a puzzle game created by Jonathan Blow, famed creator of Braid. The central mechanic of this game is a path-drawing puzzle, which looks like this:

Several grid-shaped puzzles in a row

When I first saw this mechanic, my reaction was, “So adventure game designers finally discovered Nikoli-style puzzles, eh?” Nikoli is a Japanese publication that popularized a certain genre of puzzles using numbers or symbols on a grid. The best known puzzle of this genre is Sudoku, but there are many others, like Fillomino, Heyawake, Numberlink, Masyu, Slitherlink, and Nurikabe (almost all of which I think are better than Sudoku).

Outside of Nikoli, you can find many more created by Grandmaster Puzzles, and you can try the annual US Puzzle Championship. I should mention that I am fairly competitive in the USPC.

The advantage to Nikoli-style puzzles is that they’re scalable. Contrast with the Myst series, where most puzzles revolve around poorly-designed user interfaces for fantastic mechanisms. Could you really pack hundreds of such puzzles in a game? It would be too hard to write all those puzzles, much less make the graphics to support them. And since there are so few of those puzzles in the game, you have to make sure each one counts for every player, without being so challenging that players start looking for solutions online.

On the other hand, as far as Nikoli-style puzzles go, dedicated puzzle-crafters will have video game designers beat. Sorry, Professor Layton! What I want to see in a video game are puzzles that could only be done in a video game. Luckily, The Witness passes this test, being a lot less like a Nikoli puzzle than it first appears, and not just because solutions are non-unique.
[Read more…]