Update: This post is outdated and this project can now be found at github zebrajs

Zebra/Einstein puzzle is basically a constraint problem, where you have to find a unique solution that satisfy all constraints.

Its fun and can be easily solved on paper.

**The Poor Man JavaScript Prolog** its what I call a Variable Object implementation in JavaScript that can do two important things:

- Unify: variable unification,
- Not Unify: constrain variable to not unify with other variable.

My first solution of zebra puzzle, like many others out their, was kind of a brute force approach it wasn’t complete brute force because the defined constrains

make the program to fail earlier and try other options and also because the constrains or facts will fill some of the values.

I was thinking in the problem from the wrong perspective, I should have used a more constrain satisfaction approach.

For example, I can start with 5 vars representing the houses, and all vars start with all the possible house values: [“red”, “green”, “white”, “yellow” “blue”];

Using constrains I will start removing values from the variables until I end up with only one value per variable.

Using js Variable this can be done with defining a domain and not_unify.

So, first I start the initial state like this:

function getVars (domain) { var res = []; for (var i=0; iAll variables have a domain and are constrained to be distinct.

To solve the zebra puzzle, I defined the following functions:

- same_pos (x, y, state): x and y are at same position (column),
- position(x,p,state): x are at possible positions p,
- left_of (y,x, state): y is left of x,
- next_to (x, y, state): x is next to y,
After this functions are defined I can define constrains like this:

var state = initState(); var constrains = [ // The Zebra puzzle, a.k.a. Einstein's Riddle, is a logic puzzle which is to be solved programmatically. It has several variants, one of them this: // There are five houses. // The English man lives in the red house. function () {return same_pos("english", "red", state);}, // The Swede has a dog. function () {return same_pos("swede", "dog", state);}, // The Dane drinks tea. function () {return same_pos("dane", "tea", state);}, // They drink coffee in the green house. function () {return same_pos("coffee", "green", state);}, // The man who smokes Pall Mall has birds. function () {return same_pos("pallmall", "birds", state);}, // In the yellow house they smoke Dunhill. function () {return same_pos("yellow", "dunhill", state);}, // The man who smokes Blue Master drinks beer. function () {return same_pos("bluemaster", "beer", state);}, // The German smokes Prince. function () {return same_pos("german", "prince", state);}, // In the middle house they drink milk. function () {return position("milk", [1, 2, 3], state);}, // The Norwegian lives in the first house. function () {return position("norwegian", [0], state);}, // The green house is immediately to the left of the white house. function () {return left_of("green", "white", state);}, // The man who smokes Blend lives in the house next to the house with cats. function () {return next_to("blend", "cats", state);}, // In a house next to the house where they have a horse, they smoke Dunhill. function () {return next_to("dunhill", "horse", state);}, // The Norwegian lives next to the blue house. function () {return next_to("norwegian", "blue", state);}, // They drink water in a house next to the house where they smoke Blend. function () {return next_to("water", "blend", state);}, function () {return at_least_one(state); } // --- // The question is, who owns the zebra? ];The last constrain (function () {return at_least_one(state); }) is a special function, and its there to check if a variable as one possible value that is not

in any other variable, so that would be the value of the variable, for example:v1 = [red, green, blue, yellow, white];

v2 = .. = v5 = [green, blue, yellow, white];So red is in v1 but not in v2 .. v5, since all variables must have a distinct value then v1=red;

To apply the constrain I made the recursive function:

function run(state) { var end = true; constrains.forEach(function (c) { if (c()) { end = false; }; }); end || run(state); }; run(state);The run function will run until no constrain can be applied any more.

Some constrains will only have effect after other constrains are applied, and some can be applied more than once.For example left of is defined like this:

function left_of (y,x, state) { var xps = find(x, state); var yps = find(y, state); var change = false; var max = 0; for (var i in xps) { if (max < i) {max=i;} } var min = 4; for (var i in yps) { if (i >=max) { yps[i].not_unify(v(y)); change = true; } if (min > i) {min=i;} } for (var i in xps) { if (i < =min) { xps[i].not_unify(v(x)); change = true; } } return change; };What this constrain does is to find y and x positions since y is left of x then:

- y position must be less than the right most position of x,
- x position must be bigger than the left most position of y,
Exemple:

_ x x _ _

y y y y _It will became:

_ x x _

y y _ _I said constrain can be applied more than once, for example:

If other constrain transforms the previews example to this:

_ x x _

y _ _ _then running the left_of constrain again will result in:

_ x _ _

y _ _ _Well thats it ๐

Happy coding...