Unbiased estimators in a Monty Hall problem

In my previous post, I talked about the German Tank Problem. And while discussing the frequentist approach, I defined the “unbiased” estimator. But seriously, unbiased estimators are really weird. Let me show you an example, in the form of a Monty-Hall-like problem.

Suppose that I’ve set up three closed doors A, B, and C, each with a prize behind it. Two of them have $1000, and one has $2000. Doors A and B don’t really matter, your prize is behind door C. How much is this prize worth to you? But before you answer, please, look behind one of the other doors, A or B.

[Read more…]

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

Puzzle solving skills

Back when I was looking for a job, I did a lot of interview prep with other people. Among other things, that means practicing brainteasers in front of white boards. But as it turns out, I am extremely good at this already and don’t need the practice. Recreational math was a hobby in my youth, I participated in math competitions in college, and I’m mildly competitive in the US Puzzle Championship. I don’t want to brag, but friends have told me I ought to brag more often, so I am bragging. I am ridiculously good at puzzles.

So if I’m “good” at puzzles, what skills does that mean I have?  It’s hard to say.  (Does this imply that I’m also good at the jobs I interview for? Eh.)

There are, of course, many very different kinds of puzzles, and perhaps each category of puzzles requires unique skills. To name a few categories: programming puzzles where you seek to write an algorithm; logic problems where you deduce a solution from structured clues (e.g. Sudoku); puzzles where you make multiple moves in sequence (e.g. Sokoban); math problems; jigsaw puzzles; and what I call “linchpin” puzzles, where the goal is to have a particular realization. Some puzzle solving “skills” are more properly understood as puzzle-solving knowledge–knowing the solution to a bunch of common puzzles gives you a set of tools to solve new puzzles. But I also think there are a few general puzzle-solving skills, which I’ll try to describe.

[Read more…]

Challenging puzzle game tiers

I play a lot of challenging puzzle games. For others who are interested in the same niche, I’ve made a bit of a tier list.  Rather than using the classic S/A/B/C/D/F tier system, I’ve chosen more evocative tiers, which are not necessarily organized from best to worst.

The list only includes games that I’ve played and that I remember well enough. I’m also using an arbitrary definition of the “challenging puzzle” genre. (Honestly, Zach-like programming games ought to qualify, but I didn’t put them in this list so.)

Games winning my highest praise

Baba is You – This critically acclaimed game combines an entertaining and clever premise with amazing level design. Puzzlers looking for a challenge will also enjoy the optional puzzles, which go quite deep.

Recursed – A hidden gem, rough around the edges, but absolutely mind-blowing once you get into it. Chests within chests within chests within chests. Chests that contain themselves, or each other. Recursion beyond my wildest dreams!

Toki Tori 2 – The best metroidvania puzzler I’ve ever played. Instead of gaining new abilities, you gain new insights into the mechanics, finding new branch points and solving clever puzzles.

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