The widest selection in the world of articles, reviews, interviews and biographies relating to logic puzzles as a way of life. Read about education, health, handicraft, solving techniques, illusions, tutorials, championships, polls, travel, new games, and much more. Perhaps you want to publish an article as well?

Info

Difficulty of PAP puzzles: the limitations of being human

by
Mary Pat Campbell

Monday, March 3, 2003

Above are two PAP puzzles of the same size. One is very easy while the other is extremely tough. Which one is which?

"This is the great bug-a-boo of PAPs; they propagate globally. When you have every box in a column marked finally, it affects every single row which crosses it, and they affect all the columns crossing them... You can make a single mistake in the upper left corner of the puzzle and ruin the entire puzzle."

I solve PAPs on paper. Also, I am human. Both of these have an impact on the perceived difficulty of the puzzles as well as the time it takes me to finish them. But time and difficulty aren't necessarily linked.

I have worked on puzzles ranging from 15 by 15 to 60 by 100; anyone who tries a wide range of sizes knows that the larger the puzzle, the longer it usually takes. This doesn't have anything to do with an increasing logical difficulty -- it simply has to do with how many blocks need to be filled in. Like most solvers, I mark both filled-in squares (by, well, completely filling them in) and squares I know are empty. I put a little dot in the middle of the box -- I used to use Xs, but they made the final pictures difficult to see. Consider the 15 by 15 puzzle: it has 15 x 15 = 225 squares that will be filled in by the end; on the other hand, the 60 by 100 puzzle has 6,000 squares. Coloring all these boxes take time.

Taking it to an extreme

Still, just because something is larger doesn't mean it's more difficult. Taking it to an extreme, I could have a 15 by 15 puzzle that has some very involved logic and thus takes me 20 minutes to solve. On the other hand, I could have a 60 by 100 puzzle where ALL the boxes are filled in. If I fill in the boxes one-by-one, it could take me 20 minutes and almost zero logical thinking. But almost invariably larger puzzles are more difficult. And there are several reasons for this.

There is, at the core, only one thing going on logic-wise in PAP puzzles: in a given row or column, you determine all possible configurations and mark filled-in boxes that are filled in all possible configurations that fit the given pattern. You mark as blank all those that must be empty. For example, in a row that's 15 across, if there's a single block of 10, you know that the middle 5 boxes must be filled in. No matter how you move that block of 10, those 5 blocks will be filled in.

Just sweep

So now you know how to solve all PAPs: just sweep down all rows, one at a time, doing this, and then sweep across all columns. And repeat that cycle until done. Exciting, eh? That's about as fun as solving a wordsearch puzzle by going word-by-word and scanning through every single letter in the grid to find the word. You know that's a way to ensure a solution, but most people don't attack the puzzle that way until they're down to the last few words. Our brains are built to discover patterns, and most people can find words in a letter matrix if they simply start scanning over the entire matrix -- they don't even have to know what's in the word list. Often a word just "pops out".

Likewise, when I actually work on a PAP, especially a large one, I try to find a natural starting place. I look for large blocks; since they take up a lot of space, they're more likely to "overlap" in all possible configurations. Also, I'll add up all the block numbers for a given row or column, plus 1 for each interblock region, because there's at least one blank space between blocks. The larger the number, the more likely one will find overlaps. When you get those blocks, you check the crossing rows or columns to see what can be done with them. The best place of all to start is really large blocks on or near the border of the puzzle, because one can fill in information from the edges.

Frying pieces of food

So why are larger puzzles generally more difficult? Sure, they will have gigantic blocks or large total block counts, but the rows and columns are also so much larger, so any overlap is less. As well, if the large blocks occur on the edges, they tend to have less of an effect on the whole puzzle. Think about frying pieces of food, which cooks from the outside in; smaller chunks will cook faster because the center of the food is closer to the outside surface in smaller bits.

But that's not the only reason. Does this look familiar? 1 3 2 3 2 15 3 2 1 1 1 1 1 3 1 3 1 ... In working with bigger puzzles the designers could simply scale a smaller figure up to a larger one. Take a 15 by 15 puzzle and multiply everything by three to get a 45 by 45 puzzle. But what would be the point? When given a bigger canvas, these artists will put in more detail. That means you'll see a bunch of small blocks together in one row. This makes solutions grow more slowly so you'll have more back-and-forth between crossing rows and columns.

Also, when one is forced to scan across columns and down rows to see where the puzzle can grow, there are so many of them to check; going back to the word search comparison, one finds a single given word faster in a 15 by 15 grid of letters than in a 60 by 60 grid. As well, when rows and columns are long, one may be looking left-right or up-down between the part he is filling in and the numbers on the top or to the left; it's harder to take in the boxes and numbers in one glance in large puzzles. But it's not just the detailed logic and perceptual limitations that make large puzzles difficult in a pragmatic sense.

The great bug-a-boo of PAPs

Simply put, humans are fallible. I've learned the very hard way to slow down greatly when approaching these blocks. It's too easy to miscount. It's even easier to skip over repeats. For example, the row may have 5 3 2 3 2 7 8 filled in, and the info at the beginning of the row says 5 3 2 3 2 3 2 7 8. When there are repeated blocks like the "3 2" in that example, it can be too easy to miss. At this point, I've decided I've filled in everything in that row and am now dotting off the other blocks as empty. Oops. I've just ruined a puzzle I've been working on for 2 hours already. Once I realize I've made a mistake, I may be lucky enough to find the origin of the mistake, but it is extremely difficult to undo.

The worst mistake of all is deducing certain boxes as being filled or empty when they are not; a simple mistake in logic. This is the great bug-a-boo of PAPs; they propagate globally. When you have every box in a column marked finally, it affects every single row which crosses it, and they affect all the columns crossing them... You can make a single mistake in the upper left corner of the puzzle and ruin the entire puzzle. Eventually you will come across a row or column which cannot possibly work. Worst of all, your mistake is undetectable: the row or column in which the mistake was made can have the proper number of filled and empty boxes. Your only recourse is to start over entirely.

Not all picture-forming logic puzzles work this way. LAP is local; you can get a single path wrong, but it will mess up only a particular corner. You can erase that corner and do it over again. So though the logic involved in larger puzzles may not differ one whit in difficulty from a smaller puzzle, there are so many more opportunities to make mistakes. The puzzles fill in much more slowly because one has learned to be extra-careful or risk losing hours' worth of work. However, the larger puzzles are ultimately more rewarding. Who knows what's hiding in the next 60 by 100 puzzle? It could be the New York City skyline or a Renaissance mural. Try fitting that in a 15 by 15 puzzle.