Blog – SotiriosGames

The following shape is comprised of exactly five tetrominoes, shown in light gray. The borders between them, however, are not shown. Your job is to draw borders between the dots such that the tetrominoes are visible. Can you do it?

It’s a trick question: there is no unique solution. Here are the four solutions:

This particular puzzle is fairly easy, since it’s clear that there must be an I-block on the left. This is a form of forward-checking, and it’s something experienced puzzle solvers do all the time: they can eliminate fruitless search paths before spending any time on them. Even so, some tougher puzzles require you to backtrack: the hardest Sudoku puzzles may need multiple layers of recursion before a particular partial solution is identified as inconsistent.

Even if getting all solutions to a puzzle is easy, logic puzzles need to have a single solution. If not, solving them is bound to be a very frustrating experience, especially for more complex puzzles. How, then, can we come up with a puzzle based on the idea of tiling an orthogonal polygon with tetrominoes if such simple shapes have so many tilings? The answer is to impose a global constraint: for instance, if we require that there are no T-blocks, the only solution is the top-left one. So, how can we get all possible solutions to such a puzzle, such that we can come up with a constraint that enforces a single solution?

Constraint propagation

Constraint satisfaction problems (CSPs) are a very broad class of combinatorial problems. Logic puzzles such as Sudoku, Nonograms, Shikaku, Hitori, Hashi, and Nurikabe, to name a few, are all examples of CSPs, and so is the little tetromino puzzle above. Constraint satisfaction problems can be recast as SAT problems (Boolean satisfiability problems), but the geometrical nature of the tetromino puzzle means that expressing it as a SAT problem is not easy. Instead, let’s take advantage of the vast machinery of graph theory and express the puzzle above as a graph, where the 1×1 blocks correspond to vertices, and their shared edges correspond to edges.

This graph was reproduced in Mathematica, which features a powerful set of tools for graph theory visualisation. All we have to do now is delete enough edges, and a solution will reveal itself once the graph is composed of exactly 5 disconnected subgraphs with 4 vertices each. We could try to brute-force the problem, but that’s a recipe for disaster: checking all 2^25 possible states is not something that we want to do.

What, then, should we do? Here is where constraint propagation comes to the rescue. Instead of iterating over the vast state space, we will perform a breadth-first search, where the depth corresponds to how many edges we have removed from the graph. Thus, the decision tree is made up of nodes, each of which is a 25-bit binary number (since there are 25 edges to be deleted). A 1 corresponds to an edge which is still there, whereas a 0 corresponds to a removed edge.

The method we use is a simple version of arc consistency. At each node, we have already cut some edges (0s), and make further cuts (i.e. split the node into children, each of which turns a different 1 into 0). Then, we only propagate down the branch where the new cut will lead to a consistent solution: this is a simple implementation of backtracking (this may produce some double counting of states, which can be easily taken care of using the inbuilt RemoveDuplicates function).

And what is the consistency check we use? It’s very simple: given enough edge cuts, the graph will eventually become disconnected. The consistency check is therefore that all disconnected subgraphs have 4n vertices. Any partial solution that doesn’t satisfy this constraint will never satisfy it even if more edges are removed, and no further search is performed down that branch.

Forward checking/full look ahead (which take into account consistency between uninstanced variables) are generally faster, since they rule out bigger chunks of the search space. The difference is easily seen in the 8-queens problem: instead of adding queens to the board and checking whether they are in line of sight of another queen, we only place further queens not in a row, column, or diagonal of another queen. Applying such a constraint is slightly more challenging here, since it’s not much more algorithmically efficient to rule out child nodes (as opposed to checking them for consistency).

Running this algorithm returns more graphs than there are unique solutions. This is because some resulting graphs are equivalent up to relabellings within their disconnected components. Sorting the disconnected components of all the graphs in canonical order ensures that graphs whose disconnected components are relabellings of each others coincide, and so using the RemoveDuplicates function again produces all possible solutions:

Graph partitioning is a very exciting field (especially since graph partitioning is NP-hard, even subject to balancing constraints), and there are of course much more sophisticated algorithms than the one presented here. Even so, it’s quite interesting to see what kinds of puzzles can be generated and tested with the help of a simple algorithm.

A few more puzzles

I leave you with a few puzzles of the same variety – and this time, they do have a unique solution, honest. Can you solve them?

George Orwell once wrote an essay in which he fondly described his favourite pub: The Moon Under Water. He goes into great detail about the clientele, atmosphere, and offerings of The Moon Under Water before musing that, sadly, no such place exists (even though a few, he says, come quite close to his vision).

But what about the ideal board game? Unless you’re a lifestyle gamer, devoting all or nearly all your gaming time to a single game like Chess or Go or Magic: the Gathering, you’d probably be hard-pressed to come up with a list of ten games that you’d be happy to play exclusively for the rest of your life, let alone one. Perhaps Orwell, if he ever happened upon The Moon Under Water, would have been content to never visit another public house. I, on the other hand, know that I will never come across a game so great that it will chase away my desire to play anything else.

Still, I’m sure that every gamer has in their mind a list of traits that describe their “ideal” eurogame (in order to limit the scope of the discussion a bit). This is a game they would always be excited to talk about, play, and teach to new players, and they’d probably never turn it down, even after a long, grueling game session. With that, here is my review of my ideal eurogame: Merchants of Moonwater.

Merchants of Moonwater plays best with 3 players, though it scales very well to 2 and 4. It doesn’t need extensive modification to the rules to work with 2, and the rules haven’t been twisted in order to force it to work with 5, 6, or 7 players. It doesn’t overstay its welcome: games rarely last more than 90 minutes, and the structure of turns is simple enough that even if you’re playing with the sort of people who are particularly prone to analysis-paralysis, individual turns never last too long.

The theme of Merchants of Moonwater permeates the entirety of the game, from the artwork to the details of players’ turns. Every quirk of the rules has an explanation that ties it back to its theme, and the gameplay gradually builds up towards an exciting and satisfying conclusion. Winning the game isn’t just something you get to do after having collected the most points: it’s a mark that you have achieved something truly inspiring in the story that the players have woven while playing. Even so, Merchants of Moonwater never sacrifices mechanical elegance for the sake of theme – it still is a eurogame through and through after all.

Set-up is variable without being too random. Every game plays differently, but players can still make use of the knowledge they’ve accrued through repeated plays to adapt to new situations. There is a low amount of randomness involved, and it is never punishing: random elements serve to restrict players’ options rather than determine their failure or success once a course of action has been chosen. Players may not be in full control of what fate offers them, but they can rest assured that once they’ve made their decision, its outcome is not left up to the vagaries of the dice or cards.

Merchants of Moonwater features plenty of indirect player interaction. There are always numerous opportunities for players to mess with each others’ plans, but to intervene with another player’s progress is not a decision to be taken lightly. It needs to be carefully weighed against your other options, and it certainly requires more thought than simply playing a single card that reads “your opponents lose five coins”.

There are several resources in Merchants of Moonwater, but they are much more than coloured tokens to be pushed around. Each resource has a clear, well-defined mechanical role: different actions in the game require different proportions of resources, which makes choosing which resources to focus on a strategic decision in its own right, and discourages indiscriminate hoarding. The same goes for tracks on which players advance throughout the game: they confer very different benefits, and so anything but interchangeable.

Merchants of Moonwater has a venerable mosaic of different mechanics, some tried and true, some fresh and bold. None of them feel disconnected from each other: at no point do you feel you are playing a minigame parallel to the “real” game. The mechanics are just complex enough so that there is no one obvious path to victory, but intuitive enough to preclude players having to look up the minutiae of every action they take in the rulebook.

Speaking of: the rulebook is clear and intuitive, with robust, illustrated examples, an extensive F.A.Q., and a comprehensive index. It has a summary of the rules on the margins to help players who have played the game before quickly find information during play. Consulting it is rarely necessary: there are player aid cards that skillfully summarise most of the information required to play through the game.

The box is hefty and strong: it will not crease even if considerable weight is placed on it. It’s as big as it needs to be: all the game material can fit reasonably snugly inside it, without much room to wiggle around. There is no insert, so there is no fear that cards won’t fit once sleeved.

The artwork is a sight to behold: it has a distinctive style that pops out without being distracting, and there are plenty of unique pieces of artwork on the components. The graphic design is elegant and utilitarian at the same time: it is functional and serves to complement the player’s understanding of the rules, rather than obfuscating them. The game doesn’t try too hard to be language independent, and avoids the mistake of having an overabundance of icons served without context, hindering rather than aiding communication of game concepts to players.

Finally, the components are nothing short of pure tactile pleasure: thick player boards, sturdy tiles and cards, and beautiful, bespoke wooden meeples. Dice are wooden as well: there are absolutely no plastic components. The only plastic in the box is in the ample number of plastic resealable bags that are provided alongside a couple of cloth bags that allow you to draw tiles blind without stacking them.

Maybe this description asks too much, maybe it doesn’t. Merchants of Moonwater may never be made, or it may already exist under a different name. My vision for it is cobbled from different games I’ve played over the years. I know many games that come close to it, but I can’t think one off the top of my head that perfectly matches it. But I certainly won’t complain: even if Merchants of Moonwater doesn’t exist, I’ve played enough fantastic games to last a lifetime. I’m not going to let perfect be the enemy of good.

And, to conclude by paraphrasing Orwell, “if you know of a game that has a rich theme, clear mechanical distinction between resources, variable setup with low randomness, multiple paths to victory and no plastic bits, I should be glad to hear of it, even though its name were something as prosaic as Medieval Towns or Stone Miners”.