Wednesday, February 11, 2015

Building Puzzles is the Hardest Puzzle

I picked up Hexcells recently on the basis of Kodra and Rae's talking it up, and have enjoyed it quite a bit. I've always been a big fan of logic puzzles of any sort, so it was right up my alley.  The basic gameplay is much like Minesweeper, where each cell is either part of a pattern (blue) or not (black). Yellow cells are of unknown status and must be marked by you. To solve the puzzle you must successfully mark all of the cells. Unlike Minesweeper, however, each puzzle gives you some information to start with and can be solved with no guessing at all.

As you graduate to more and more complex puzzles, additional methods of providing information to you are introduced. You'll be told how many blue cells are in a particular line of cells, or that all the blue cells in a particular line or around a cell are contiguous. Eventually you start getting cells that contain a number signifying the number of blue cells within two spaces of that cell. Ultimately you find yourself having to combine information from multiple sources to identify cells properly. It's very difficult by the end, but extremely gratifying when you successfully solve a puzzle.

There are 3 Hexcells games, each with 36 puzzles of increasing difficulty. The difficult also increases more quickly in each successive game, so you're quickly solving puzzles harder than the previous games hardest.  By the end they're downright fiendish and I found myself having to take a break and come back with fresh eyes on multiple occasions (thankfully the 3rd game saves your progress on partially completed puzzles).  Ultimately though, I made it through and finished the final puzzle.

My wife saw me playing and asked "Are you a bee?"

The third game, Hexcells Infinite, introduces Infinite Mode, which boasts 100,000,000 computer generated puzzles.  Put in a numerical seed, get a puzzle.  Sadly, but not at all surprisingly, they're just not as good as the set puzzles you get up to that point.  The game's main puzzles contain a paucity of information, forcing you to determine which of a very few existing clues your latest moves will combine with to identify your next move.  The generated puzzles I've tried, on the other hand, are overrun with numbers from the very beginning and are mostly a matter of scanning through the puzzle for the next obvious move.  Occasionally I'll have to stop and think a bit, but it's mostly just click click click done.

The problem is that programming a computer to build interesting puzzles is difficult.  Much more difficult than writing a program to solve puzzles; that's generally trivial if the puzzle is based on pure logic and intended to be human-solvable.  Building a puzzle requires you to develop explanations for what make a puzzle good that can be expressed in code.  I have no way of knowing how the Hexcells puzzle generator works, but if I had to guess I'd posit that it generates the field of hexes and assigns them each blue or black based on an algorithm that uses the seed as input, creates all the possible clues the puzzle could have, then starts hiding cells and removing clues while checking that the puzzle remains solvable.

With a million possible puzzles, I'd guess that from sheer happenstance some clever ones will show up, but Sturgeon's Law appears to apply in this case.  That said, it's still a great game and would have been well worth my time if the Infinite feature didn't exist at all.

No comments:

Post a Comment