Thinking Deeply About Logic Puzzles
If you know anything about me, you know that I’m passionate about puzzles. I particularly like logic puzzles, by which I mean puzzles that require logical thinking to solve. In these notes I will try to “think deeply” about puzzles: What is a puzzle? What makes a good puzzle? How do I create new puzzles?
What is a puzzle?
There are many different types of puzzles, but the primary common feature is that they have a solution! Some puzzles explicitly define the elements of the puzzle and the valid operations or moves. Other puzzles don’t even make clear exactly what the goal is, and part of the puzzle is to “figure out just what the puzzle is”. Still other puzzles have hidden elements that may get revealed (e.g. MasterMind, or puzzle boxes with hidden mechanisms). Math problems and scientific research projects can also be viewed as kinds of puzzles, some explicit, others very open-ended. There are jigsaw puzzles where one has to use piece shapes and visual clues to assemble a target picture. There are popular paper-and-pencil puzzles (like KenKen and Sudoku). With the development of computers and videogame systems, there are now a wide range of interactive puzzles (and video games).
I personally am particularly interested in puzzles which are explicitly stated (goal is clearly defined, and the elements and operators are well-defined), and can be solved by logical thinking. I don’t particularly care for puzzles with hidden goals or hidden elements. Nevertheless, the class of explicit puzzles is quite broad . I enjoy physical puzzles, paper-and-pencil puzzles, and interactive (computer and smartphone) puzzles, among others.
A Few of my Favorite Puzzles
1. Physical puzzles: Rubik’s Cube, Hi-Q Peg Solitaire, Hi-Q Dominos, Rush Hour, numerous other sliding-block-puzzles (and many more!)
2. Paper and Pencil puzzles (newspapers, magazines, books): KenKen, Sudoku, RoundTrip and OneWayTrip (Monorail type path puzzles)
What Do I like about these puzzles?
a. They are challenging and fun to solve
b. Most involve visual / geometric elements
c. I can develop skills and expertise at solving (a variety of reasoning strategies that can be learned!). Best of all if there is a hierarchy of skills!
d. They are reasonably time-limited (typically solvable in hours — not days, weeks, or years)
Creating a new puzzle – case study of Target Tiling (inspired by Tetris)
I became a Tetris addict when it appeared back in the late 1980’s, playing first on the Mac SE, later on the NES (Nintendo Entertainment System). I loved the geometry, the challenge, and even the music (Russian folk tunes)! I was inspired to write my own Tetris simulator, so I could experiment with variations of the game. Over time, this project grew into a rather rich and extremely challenging interactive puzzle game (my Target Tiling – available for free download from my web site)
1. Identifying the elements:
Board size (Tetris had a fixed 10-wide board),
Pieces (Tetris had 7 pieces, each covering 4 grid cells) that could be rotated and placed in position
Row-clearing rule (completely filled rows are eliminated and the cells above move down to fill the vacated space)
2. Playing with (varying) the elements
Once I had written a general-purpose Tetris simulator, I began varying and playing with the elements. I tried different board sizes, both narrower (4, 5, 6, 7) and wider up to 20 or 30. I introduced different piece shapes, again, both smaller (1, 2, and 3-cell pieces), and larger (the full set of Pentomino shapes, which cover 5-cells each). I also varied the speed at which pieces would fall on their own, but I found I much preferred slower speeds (I also included a “Pause” feature”) – in general I’m not a big fan of timed puzzle solving or games – I prefer to think in a more relaxed mode.
3. Varying the puzzle objective
Tetris is fundamentally a game of survival — typically the pieces speed up until they fall so fast that you can’t control them, at which point the board “fills up” and you lose. I much prefer puzzles and games that I can “win” (solve). At some point I latched onto the challenge of “completely clearing the board”. I thought this made a nice clear objective, and provided satisfying closure when achieved! I first tried this (as a self-defined objective) in Tetris on the NES, but it was extremely difficult to achieve because the “Next Piece” was always chosen randomly – so one couldn’t plan ahead very far. I’d try to achieve a board pattern with the “bottom rows” filled except for a “hole” in the shape of one of the pieces. Even doing that is quite difficult, but once accomplished one has only a 1-in-7 chance of getting the necessary shape as the next piece. It struck me that this “puzzle objective” (clearing the board) would be much more interesting if the next piece was chosen deterministically, as this would allow planning.
4. Simplification (thinking deeply about simple things)
So I experimented with various simplifications / modifications
a. Make the board width smaller (5, 6, and 7, seemed to work well)
b. Use just a single piece type (this was the simplest way to make the next piece choice deterministic – you always get the same piece shape!) Through experimentation I found that the T-piece and the L-piece (or J-piece) seemed the most interesting. The Z-piece was impossible (on a 2D board), and the 2×2 square and the 1×4 “I”-piece seemed rather boring.
5. Skill learning
Using the T and L pieces on boards of width 5, 6, and 7 turned out to be very challenging and interesting. Over time, I was able to develop skills that let me reliably and fairly quickly solve these puzzles. I used a random start position (formed by dropping a specified number of pieces of the given type), and would then proceed to work the pattern down (reducing the number of rows) and finally clear the final bottom rows. I found this both challenging and immensely enjoyable. I particularly like the set of skills I developed that made me an “expert” at these puzzles! These skills formed a natural hierarchy, with higher-level skills building on and using lower-level skills. At the lowest levels there are standard Tetris skills (using the controls to rotate and place pieces in desired target locations, and exposing and filling “holes” to reduce the height of the remaining cell pattern). The final “WipeOut” skill (clearing the board exactly) involved learning to recognize specific “solvable patterns” and applying the associated move-sequences (macro moves) to solve them. Some of these macro-moves simply transformed one recognized pattern into another (simpler) pattern that could then be solved by subsequent macros.
6. Adding incremental complexity
After I became skilled at these basic puzzles, I started thinking about adding new challenges.
a. Multiple pieces
I tried a variation using both the T and L pieces (alternating so that the piece sequence was still deterministic so as to allow planning). Having 3 or more pieces can be extremely challenging, even when still deterministic, but experimenting with those possibilities led to a virtually endless set of rich challenges. I even tried returning to the complete set of 7 original Tetris pieces (presented in a deterministic fixed / cylic order) – that was difficult but still a fun challenge, though I still preferred narrower boards — width 10 gets rather tedious and takes a really long time to solve. I found that widths 5, 6, and 7 were most enjoyable.
b. Target Pattern (generalization of WipeOut)
At some point it occurred to me that I could generalize the puzzle objective from WipeOut to achieving a specified Target pattern (a particular set of marked cells to be filled). The WipeOut objective could be viewed as the special case of the “Empty Target pattern”. Initially, I would specify some cells to be left filled in the bottom row. This led to a new level of skill based on doing a “wipeout” in “mid-air”. Let me explain. If the target was a single cell in the bottom row, for example, then one could begin by doing a full WipeOut (clearing the board), but this would not “solve” the target puzzle, since the target cell is empty, and needs to be filled. Next, one could place a piece so that it covered the target cell, but no other cells in the bottom row – this might involve “standing the piece on end”, for example. This fills the target cell, but still doesn’t solve the puzzle — the objective is to match the exact target pattern by filling all the marked target cells and no other cells!). In our example, this can be achieved by wiping out rows 2 and above, while being careful never to fill any of the empty cells in the bottom row — I call this a mid-air wipeout. It turns out to require concave pieces (such as the T and L) which can then “hang over the side” of filled cells, so as to fill more and more of the rows to be cleared (wiped out). This introduced an entire new level of skills and patterns!
c. Mid-air Targets
There was an “Aha!” experience I had while playing Tetris on the NES. I asked myself it it might be possible to “suspend a piece in mid-air”, by which I mean have piece “floating” without obvious support (either from below, or cantilevered from a filled cell to its right or left). At first blush, it seemed like there was a kind of “gravity” at work in Tetris, so maybe this was impossible. But Tetris-gravity is different — when each row clears, cells above that row only move down 1 cell, in particular, they do not keep falling! So I set myself the challenge of “floating a piece”, and soon discovered that I could create a mid-air platform (2 or 3 nearly filled rows with a piece-shaped hole) cantilevered from a single support cell (that is the row below has 1 cell filled but the rest of that support row is empty).
Here’s an attempt to illustrate:
This graphic shows a platform (rows 2 and 3, not counting the red base row) with a T-shaped hole. A T-piece is descending in columns 3-5, and will “fill the hole” in the platform:
After the piece fills the platform hole, rows 2 & 3 will be filled and so will be removed, and the 4 cells resting on the platform will move down 2 spaces, ending up as “floaters” in rows 2-4. The floating T-piece will not fall further, it is statically floating:
d. 3-D Geometry
You might notice that the pieces are drawn in a “sort-of” 3D perspective. In fact, the current version of Target Tiling supports both 3D board grids and 3D pieces. Check out the game on my web page to try it out: Target Tiling (this gets you a page with instructions on how to download and install – it’s all free!) Eventually I hope to release a version for smartphones, but the current puzzle game runs on MacOSX, Windows, and Linux. To run it, you need to download the LispWorks PE (which is also free) – just follow instructions on my page. If you do try it out, please send me your reactions and thoughts. Thanks!
… more next week