malvasia bianca

Conceptis has a bunch of very good mobile puzzle apps; probably my favorite three puzzle types of theirs are Slitherlink, Nurikabe, and Fill-a-Pix, but most of them are good enough that I play the free puzzles every week, and I probably buy one paid puzzle packs of one type or another from Conceptis every week on average.

Looking at those three puzzle types, I guess it’s a pretty clear sign that I like puzzles where you build out the solution locally, with a sort of geometric / organic feel to them? And puzzles with a rhythm of watching the puzzle grow as you do fairly obvious (but pleasant!) stuff for a while, then stopping and thinking until you can find a non-obvious way to progress somewhere, and then going back to obvious mode. (Admittedly, that last sentence describes an awful lot of puzzle types!)

Anyways, I want to talk about Fill-a-Pix. Conceptis actually classifies their Fill-a-Pix puzzles into two buckets: Basic, which can be solved purely by directly applying the rules, and Advanced, which require you to apply techniques that are consequences of the rules rather than restatements of the rules. And their UI supports this distinction, allowing you to switch between single-cell control and 3×3-group-of-cells control, where the latter tries to apply the rules directly.

Fill-a-Pix is, I think, unique among their puzzle types in having Conceptis make that specific distinction; part of the strength of the puzzle is that Basic puzzles really are quite pleasant to fill out, and sometimes I actually do get stuck for a minute or so trying to find the next place to continue. At least I get stuck if I limit myself to the direct techniques that Basic uses; I like to do that because it’s a pleasant restriction and because it’s useful practice to be able to see the foundational deductions quickly.

The Advanced puzzles are quite a bit more interesting, though. As with pretty much all interesting puzzle types, there are theorems that you can prove from the rules; they’re of the form of “if you have a group of cells with certain numbers in some of them matching some constraints and with some of the cells known to be filled or empty, then you can prove that certain other cells much also be filled/empty”. In Fill-a-Pix, these theorems are all basically algebra combined with constraints on needing small positive integer solutions; some of them I found quickly, some of them I found a little later as I got over the hump of being able to do Advanced puzzles, but I can think of one kind of subtle theorem that I only discovered after a year or two of doing these puzzles. (And who knows, maybe there are other useful theorems waiting for me to discover them!)

I’ve now settled into doing Advanced 50×75 grid puzzles on my iPad; I enjoy solving them while listening to podcasts, and, at that size, a single puzzle will take me a while. Looking at the last few I’ve solved, about half of them took me less than an hour and about half of them took me more than an hour, and it’s not surprising for one puzzle to take two or three hours.

And one thing about puzzles of that size is how the locality of solving the puzzle plays out. On the one hand, you absolutely have to focus on local areas: there’s no way you can think about 3750 different possible squares all at once! So instead I’ll pick some area to start (generally a place where there are some 0’s or 9’s near each other, so I’ve got some known empty / filled squares to work with), and I’ll see what I can figure out there, growing the known area by applying the basic rules, by applying simple theorems, by applying more complicated theorems. And then, once I get stuck, I’ll pick another part of the puzzle to work on, and rinse and repeat. And hopefully the different areas that I’m figuring out will merge, and I’ll solve the whole thing.

The problem, though, is: what if the areas that you’ve solved don’t merge? What if you end up having five or six blobs in different places in the puzzle, with those blobs being potentially pretty large, but still in total only adding up to half or two thirds of the puzzle? At this point, with the puzzle size that I’m working with, I might still have 1500 unknown squares; that’s a lot.

And, making things worse, Fill-A-Pix hits a fairly steep wall when you fall back to a speculative search strategy. You can try picking a square that seems key in some way, setting it to either filled or empty depending on which one you think is less likely to be true, and then applying deductions from that, hoping that you get a contradiction. And yes, sometimes that works, but a lot of the time it won’t; so, when I’m in that situation, it can often take me quite a few guesses before I manage to actually make stable progress.

But even a succesful speculative search doesn’t necessarily get me out of hot water! Sure, I now know the status of one square; and generally I try out squares where I know that I’ll be able to figure out more stuff locally if I can just prove that a certain square is, say, filled. But if I’m really only two-thirds of the way through the puzzle, then those deductions will almost certainly peter out at some point, at which point I’ll be just as stuck as I was twenty minutes earlier.

Which brings me to the reason why I’m blogging about Fill-a-Pix, as opposed to one of the other puzzle types that I like: much more than other puzzle types, a key part of my problem solving strategy (at least with the 50×75 Advanced puzzles) is: think about things really hard! And, if you can’t figure out what to do next, think even harder!

Because it turns out that, if I think hard enough, I really can figure out what to do locally. But, to do that, I have dig pretty seriously into one specific part of the boundary between the known region and the unknown region. Are there any theorems that I can apply that I just missed? (Which is the most common case: I’ve trained my pattern recognition skills pretty well, but even so, I miss stuff.) Or can I zoom in on a specific area and combine a multi-step deduction from this side of that area with a multi-step deduction from the other side of the area and prove that one specific square in the middle has a given value?

That latter kind of deduction is harder to come up with; so I used to bail out before reaching that stage, and just move to a different part of the puzzle. But what I found was that I really wasn’t saving myself time by doing that: I’d still end up having to do hard work once I’d used up the easier work, and when I got to that stage, I’d have way too many places to consider. Whereas if I focus on smaller regions of the puzzle, I can get to know those regions pretty well, and that makes it easier for me to make leaps.

So, these days, I really try pretty hard to extend a known blob, instead of jumping to a different part of the map; and in fact I’ll usually extend one part of the boundary in one specific direction, so I have a very specific area that I’m working on. If I can’t do that, eventually I’ll go to the other end of that same boundary, and see if I can extend it in the other direction; and eventually I’ll even give up on that and jump to a different section of the puzzle. (But hopefully a section that’s not too far away, so I can have a hope of merging the new blob with the older blob.)

Once I get to that stage, though, I’ll work even harder to not have to jump to yet another place in the puzzle. Because what I’ve learned is that, if I’ve got two blobs of the puzzle that I’m working on, the chances are very high that I’ll be able to make progress on one of those blobs. And if I’ve got three blobs, then I almost certainly can figure out something in one of them. So I try to never get into a situation any more where I’ve got, say, six different blobs that I’m trying to grow; long before then, I’ll decide that I didn’t in retrospect think hard enough about one of my earlier sections, and I’ll go back to it.

It’s been a long time since I’ve been a professional mathematician, but, in a way, I think Fill-A-Pix reminds me of doing math? You’re trying to make progress and bring clarity to a situation; you’ve got a bucket of techniques that you can apply, and they’ll let you make deductions locally, but you don’t know in advance which deductions will be the correct / useful ones even locally. And, even if you do improve your understanding of the situation locally, you might continue to be at sea in trying to understand the larger situation that you’re tackling. But hopefully, if you think hard enough, you’ll break through.

At least, with Fill-A-Pix, you know that there is going to be a solution, though…