The zebra puzzle

The Zebra Puzzle is a well-known logic puzzle that can be fun to solve if you are bored.
Try below your logic skills in the interactive version I made. Your objective is to get all the conditions true (green). To change the order of elements just click in the ones to swap consecutively.

If you find yourself struggling or you want an elaborated explanation of how to solve it you can find it here.

Of course this little problem is ripe to be solved with a little help of code, but the naive brute force implementation would take some time to finish; there are (5!)^5 possibilities after all, that is: 24883200000 possible arrangements that we'll need to check.
Here you can find a brute force solution using Web workers, just don't hold your breath.

Some kind of optimizations would be needed to solve this fast. I was planning to post here my crappy constrained generator code until I found this amazing post of some guy that created a whole working online Prolog interpreter to solve this kind of problems. So you better continue there.

Prolog is "the language" to solve these type of problems, here is my solution in case you are wondering:

Just ask for: "puzzle(Houses)" in the online interpreter.

Dynamic programming

Dynamic Programming (DP) problems are fun, but they can be also difficult to solve. For a better definition than I could give you here I'll redirect you to the Wikipedia article, and there are some nice tutorials and sample problems in TopCoder and CodeChef. In this post I'm just going to add commentaries to the DP problem I solved previously without giving much explanation. This problem comes from the Project Euler site:

An n×n grid of squares contains n^2 ants, one ant per square.
All ants decide to move simultaneously to an adjacent square
(usually 4 possibilities, except for ants on the edge of the grid or at the corners). 
We define f(n) to be the number of ways this can happen without any ants ending on 
the same square and without any two ants crossing the same edge between two squares.
You are given that f(4) = 88. Find f(10).

Combinatorial explosion and Project Euler 393

Last week I found a nice video about algorithmic combinatorial explosion. It was very interesting but it's a bit sad to see the big sister throwing away her life in order to teach her little students the perils of trying to compute combinatorial problems that grow very fast. The problem they studied didn't seem to be hard, just enumerate all the ways you can go from one corner to the opposite corner in a rectangular grid without passing the same node twice. Deceptively simple, for a 1x1 grid there are only 2 ways, for a 2x2 grid there are 12 ways:

Solving the Princess in a Box Puzzle

We can solve the puzzle of my last post using a Breadth-first search (BFS) algorithm. The key idea is to realize than the problem is just a Shortest Path problem where the graph, even when it is not completely known at the beginning (because we don't have the graph's adjacency list or adjacency matrix), can be built joining the states the board takes after every movement. The image below can help to understand this. It shows some of the states the board cab take after some movements starting from the beginning.

Chess problems in your phone

This little thing can make you waste serious time if you like chess problems :)
It has been only tested in my SonyEricsson W810i, but I hope it could run in most of the phones with MIDP 2.0 + CLDC 1.1 support. It requires a phone with at least 176x176 pixels in screen resolution.

It supports UNDO and REDO and has the first move of the solution as a hint (if you feel impatient). The problems belong to the books:

J. W. Abbott: 121 Chess Problems (1887)
F. Healey: 200 Chess Problems (1866)
[link]

I must thank to the guy who converted those PDF files to PGN files, without that I would have spent more time translating the positions to FEN, I only needed to prune off the bad problems and add the hints, the original PGN files can be found here:
[link]

You can choose from 4 different sets of pieces, every set has been composed by me, so every one of those pixels belong to me!! :D
To say the truth, the "Da Vinci" set was inspired in this article:
[link]

DOWNLOAD:chessProblems.jar
chessProblems.jad

Have a nice day!