Saturday 9 February 2013 — This is almost 12 years old. Be careful.
A friend shared a link to an unusual puzzle (click for a full-page PDF):
Each row has a regular expression indicating the letters to fill the row. Each cell is at the intersection of three rows, so there are a number of constraints to satisfy at each point.
Overlapping constraints are a good basis for logic puzzles. Sudoku, Ken-Ken, Nonograms, and plenty of other puzzle forms follow the same recipe: determine the contents of a cell, based on multiple simultaneous constraints.
But the regexes here add an extra dimension. Each of the regexes here has a different form, resulting in different levels of information. Two rows have .*, or no information at all. Another has [CR]*, so we know the entire row is C’s and R’s. Each row has a different regex, so the interaction is varied across the grid.
I wrote to the author, Dan Gulotta, about how he constructed it, and he told me,
I constructed the letter grid by building it up a few letters at a time. I started out with a blank grid and all of the regular expressions set to ‘.*’. At each step, I would find a place where I wanted to add a few letters to the grid and then see if I could replace some regular expressions with more constrained ones in order to force those letters to be there. In this way, I was able to ensure that the solution was unique.
A few times during my solving of the puzzle, I used the classic piece of puzzle meta-information as part of the deduction: there is a unique solution. A friend of mine said he solved it without using that fact, but I don’t see a reason to avoid it.
By the way, I didn’t realize this when I solved it, but there’s another level to the puzzle, which is to identify the phrase in it. It was part of the 2013 MIT Mystery Hunt.
Comments
First row, second to last slot, has the following constraints:
Across: could be anything, including one of the 2 mandatory H's (tho there could be more than 2 on that row).
Down: A, M or C.
Up: due to a partial solve putting an M somewhere else on that line, not an M (the regex dictates only one M on that line). If this were not the case, M would also be a possibility.
Thus, that cell could be at least either of A or C, but there are no outstanding constraints that would decide between the two, thus there are at least 2 solutions.
That's incorrect, [CR]* means 'matches zero or more instances of either C or R'. Any kind of string could fit this one.
It's a lot easier to write a checker than a solver, and not feasible to brute force even a single line normally, even given the only implicitly stated constriction of each cell containing only an uppercase letter.
An entirely brute force solver is easy to write, but would take a very long time to run. I think a true solver can't lean on an regex engine to execute the given patterns against a search space, because the overlapping constraints can't execute against the same space. Rather you have to explode them to establish individual cell constraints then chain discovered information to the crossed patterns.
https://gist.github.com/LeventErkok/4942496
It uses the Z3 theorem prover to find the unique solution.
Also, I thought at first that there would probalbly be several solutions, but solving it sequentially made those "alternate" solutions disappear by themselves, by showing new constraints (due to letters having been placed already, for instance).
All in all, a very nice puzzle, and I'm looking forward to more of that kind, if you ever lay your hands on those :)
Add a comment: