Solving 0h h1 Puzzles

You might have stumbled across these puzzles, and maybe even suffered from some degree of addiction to them. In case you haven't, here's the gist.

The puzzle consists of a square grid of cells, which can be red or blue. Some of the cells are set to either colour at the begining, while most are blank. The task is to assign red or blue to all cells so that:

• each row and column has the same number of red and blue cells
• there are no more than two adjacent cells of the same colour in the same direction (horizontal or vertical)

The rules are deceptively simple; a good measure of reasoning goes into finding the solution, though. As you go through a few of them, patterns emerge. But can the solution be automated?

The large puzzle is a ten by ten grid; with about 20 pre-set, about 80 cells need to be decided. In a brute force fashion, that means about 2^80 combinations, or somewhat over 10^24. Clearly brute force is not going to cut it.

Exploiting the conditions that the solution must meet can add some intelligence. This limits the actual number of combinations, but it forces the algorithm to be a lot more clever when selecting which assignments to make. Enter constraint propagation.

In constraint propagation, the two constraints defined above limit the values that some of the cells can take, wiping out large swaths of combinations at once. Once the constraint propagation gets stuck, the next step is just trying out one or the other colour in one of the remaining cells, and see how it goes from there.

Let's look at the search space as a binary tree, with each level corresponding to one cell, and the two branches are each of the two colours. The procedure becomes:

1. set the known cells to their colours
2. propagate the constraints to set as many cells as possible
3. if all cells get filled or the problem reaches inconsistency (there is no way to meet the constraints), the algorithm is done
4. otherwise, select one of the remaining cells and arbitrarily assign one colour, and try to solve that (going back to 2, starting a recursion); if this solves the problem, success
5. otherwise, try the other color (again, going back to 2, starting a recursion); if this solves the problem, again, success
6. otherwise, the procedure ends, but reporting that the problem is unsolvable

This process recursively explores the binary tree, using constraint propagation as a shortcut whereever possible. In practice, I still have to find a puzzle where more than 10 branching operations are needed, as constraint propagation does most of the heavy lifting.

The solution procedure can be summarized in pseudocode as:

solve(problem):
    propagate_constraints(problem)
    if solved(problem) or infeasible(problem)
        return problem
    cell = get_unset_cell(problem)
    new_problem = problem + set(cell, red)
    candidate_solution = solve(new_problem)
    if solved(candidate_solution)
        return candidate solution
    new_problem = problem + set(cell, blue)
    candidate_solution = solve(new_problem)
    return candidate solution

The recursion is seen clearly in this pseudocode. If the constraint propagation does not directly solve the puzzle, a new problem is created by setting one cell to red, and passed over to the recursive call. If that returns with infeasibility, there is still the option of making it blue. After that, there is nothing else to be done: the cell can only be red or blue.

Up to now I have glossed over the actual constraint propagation. Each of the two constraints will have its own constraint propagation function.

For the first constraint, it is quite simple: cycle through each row and column; if the number of red cells is half the puzzle size, mark all unset cells in the row or column blue, and vice versa. That's all there is to it.

For the second one, a little more care is needed. Cycle through all cells, and for each one (that is not yet set) check:

• the cells one and two positions above
• the cells one and two positions below
• the cell immediately above and the cell immediately below
• the cells one and two positions to the right
• the cells one and two positions to the left
• the cell immediately to the right and the cell immediately to the left

If any of these sets has both cells set to the same colour, the current cell must be assigned the other colour. In practice a little more care is needed, as the cells close to the boundaries will not have all of the sets.

If you are wondering how to put all of this together and make it work, I have built a short Python program that implements this concept. Check it out at GitHub.

If you are looking for a way to solve the puzzles by hand, this is not your best option. Computers are terribly good at the laborious tasks of checking over and over every rule while propagating the constraints, keeping a list of the steps they take and backtracking when they reach a dead end to try a different path down the tree. We humans soon lose track of this even at small depths.

Instead, we can solve puzzles like this by latching onto more complex patterns, and thinking through the combinations that might succeed. It also works, but is much harder to automate.

Next time you want to sautomate the solution of a combinatorial problem where success is defined in terms of the rules that the solution must follow, give constraint propagation a chance. It goes much easier on your CPU than a brute force approach.

A Dice Rolling Server for Table-top RPGs

The typical tools of table-top RPGs

I have played RPGs (role playing games) for over twenty years. As life gets busier we find it harder to schedule a few hours when we all can sit together. Because of this we want to give playing via Google Hangouts a try.

Google Hangouts covers most of the issues: we will see each other's face and talk as though we were together (with limitations, of course); and we can share documents on-screen with Google Drive for maps and other props needed during play.

But there is one thing that we cannot do easily: rolling dice. Pointing the webcam at the table to broadcast the roll is clearly out of the question, and just announcing the results may be dangerous; too much of an incentive for cheating. So we decided to develop a dice rolling server and clients.

A dice rolling application may seem rather trivial at first sight: hey, get a random number between 1 and 6 with a uniform distribution and you're ready to go, right? If you have ever played one of these games you know it's not that easy.

First, there are different types of dice: 4-, 6-, 8-, 10-, 12-, and 20-sided are the regular ones, and there are variations like simulating a 100-sided dice using two 10-sided ones, one for units and one for tens (if you're not using an actual 100-sided die), or a 3-sided one by rolling a 6-sided die and dividing by two (rounding up).

Then there are the rolls themselves. If you are already familiar with RPGs you may skip the following four paragraphs; I recommend that you also skip them if you find them boring (which is likely); in a nutshell, what they say is that each game has its own rules about rolls and that makes it more difficult than getting a random number between 1 and 6.

In some games rolls are quite uniform; in The Call of Cthulhu all rolls are 1D100 (that is one 100-sided die), and you compare the result to the applicable skill level, which is the odds of succeeding, in percentage.

In other games they can be quite convoluted; in Dungeons & Dragons you may roll things like 2D8+1D6+3 (i.e. two 8-sided dice, one 6-sided die add the three together and then add 2 to that) and check the result against a table depending on your character's level, race, and profession and the opponent's level to determine if it is successful; and another roll may be 1D20, and so on.

In other cases, the result is not calculated by adding up the result of every die. In the World of Darkness games you roll a number of 10-sided dice, check each one against a set difficulty, and count how many are greater than, or equal to, that number; oh, and substract one for each die that yields a 1; oh, and re-roll any 10 if you have a specialty that applies to the roll.

And in Legend of the Five Rings you roll things like 6K3+5 (you read that as roll 6, keep 3, plus 5), roll six 10-sided dice, add up the result of three of them (usually you'll choose the highest ones, but you may want to fail or succeed by a small margin on purpose, say, to fool someone into believing you're not as skilled as you really are) and then add 5 to that; and check that the result is greater than, or equal to, the set difference; oh, and if you roll a 10 you re-roll that die and add it; oh, and sometimes you may also re-roll nines; and there is a specific arithmetic for the rolls: you may never roll more than 10 dice, so if you have more to roll, every two excess dice turn into an additional kept die; at the point where you would roll and/or keep more than 10 dice, the excess dice turn into a +2 each... welll, you get the point.

Welcome back.

So, what we want is an application that each of us will run, loaded with the data of our character; it should allow us to make the rolls needed, broadcast the public ones, share the private ones only with the master and help with the special roll arithmetic in some games.

We will use a server to do the actual rolling and (broad)casting at the behest of the clients. I just bought a new Raspberry Pi for that, taking advantage of the free hosting offer from PCExtreme to use as the server. I will develop the clients on the Pi I have at home, but they should be portable to any system.

At the moment the rolling part is done for World of Darkness games and Legend of the Five Rings. That should be enough to begin with, and the design is, I hope, easy to extend to include new games (The One Ring will be next). I still have to transform it into a server application, right now it's just a local application.

In future posts I will explore the architecture of both the server and the client as I advance on them, and when it is in good shape I will post it on github.

Stay tuned for more new on this topic.

Setting up a Raspberry Pi to serve as development computer and media centre

Connection diagram

I wanted to use my Raspberry Pi for coding projects; that's what the Pi was designed for, and it allows to unload that from the main computer. A clean separation of concerns.

But then I also wanted to use it as a media centre, keeping the media on a network drive. What I don't want is to rearrange it every time I switch from one configuration to the other, but just turn it off, swap the SD card, and turn it on again.

This is what I came up with.