zebra.js: Generating Zebra puzzles.

The zebrajs is a variable constrain library that I developed to solve constrain problems like zebra puzzles (aka Einstein puzzles), sudoku and other constrain puzzles.

In this post I will explain how I solve and generate zebra puzzles using zebrajs.

The Puzzle

First lets define our puzzles. The puzzles are nothing more than a grid size and a list of clues, for example:

{
"grid":{"w":2,"h":2}, 
"clues":[
  {"type":"immediately to the left of","a":{"v":"var1_0","y":1},"b":{"v":"var1_1","y":1}},
  {"type":"immediately to the left of","a":{"v":"var0_0","y":0},"b":{"v":"var0_1","y":0}}]
}

We only considered puzzles with unique solutions, a puzzle with more than one solution is considered to be invalid.

The puzzles clues are defined with a constrain type and the related variables, for example:

  {"type":"immediately to the left of","a":{"v":"var1_0","y":1},"b":{"v":"var1_1","y":1}},

On the above case we have a clue with two variables “a” and “b”, I call the “v” variable property an item, they are defined as a string like this: “var0_0″, “var0_1″, …
The names of items are not important, what matters is that the same name refers to the same item.

The goal of the puzzle is to deduce all items positions, in our puzzles the “y” coordinate is already known, stored as property “y”. You can think of y as a class or group, for example in original zebra puzzle items are organized in category’s like: houses, nationality, animals, smokes and drinks.

Solving

Like I said before the goal of the puzzle is to find all item positions, we already know item y position so we only need to find out the x coordinate value.

To solve the puzzle, for every clue, we are going to create a zebrajs variable (x), the variable will be initialized with the domain of all possible x coordinates and with appropriated change events for the item/var clue.

For example the “immediately to the left of” setup function is defined like this:

var constrains = {
...
"immediately to the left of": function (grid, a, b) {
		var domain = [];
		for (var i=0; i < grid .w-1; i++) {
			domain.push(i);
		}

		a.x = v({domain:domain});
		
		var domain = [];
		for (var i=1; i < grid.w; i++) {
			domain.push(i);
		}
		
		b.x = v({domain:domain});
		
		b.x.change (function (a) {
			return function (b) {
				var da = a.getValues();
				var db = b.getValues();

				da.forEach (function (x) {
					if (db.indexOf(x+1) === -1) {
						a.setNoValue(x);
					}
				});
			};
		}(a.x));
				
		a.x.change (function (b) {
			return function (a) {
				var da = a.getValues();
				var db = b.getValues();

				db.forEach (function (x) {
					if (da.indexOf(x-1) === -1) {
						b.setNoValue(x);
					}
				});
			};
		}(b.x));
	},
...
}

We can invoke the function like this: constrains[clue.type](grid, clue.a, clue.b) and it will create the new x variable with the correct domain for every variable.

For example, if a is immediately to the left of b it means that in a grid of 5×5 “a” must be at possible x coordinates [0, 1, 2, 3] and “b” must be at [1, 2, 3, 4].
After creating x variables with corresponding domains we can setup change event on both variables to update related variables, for example if “a” domain changes to [1, 2] than “b” domain must change to [2, 3] because we know that “b” must be immediately to the left of “a”.

The last constrain that we need to setup on variables is that for every row “x” variable must have a distinct value, we can easily do it like this:

        function setVars (a, b) {
		if ((a && b) && (a.v!==b.v) && (a.y===b.y)){
			a.x.not_unify(b.x);
		}
	};

	for (var i=0; i < clues.length-1; i++) {
		var clue1 = clues[i];
		for (var j=i+1; j < clues .length; j++) {
			var clue2 = clues[j];
				
			setVars(clue1.a, clue2.a);
			setVars(clue1.a, clue2.b);
			setVars(clue1.b, clue2.a);
			setVars(clue1.b, clue2.b);
		}
	}

The code simple compares all clue variables and if they have the same y value and are not the same item ("v") then x variables are distinct and we say they don’t unify.

Now that all variables are created with the correct constrains we just need to unify all equal variables (variables with same item name), we do it like this:

        clues.forEach (function (clue, index) {
		items[clue.a.v] = items[clue.a.v] || clue.a.x;
		items[clue.a.v].unify(clue.a.x);
		if (clue.b) {
			items[clue.b.v] = items[clue.b.v] || clue.b.x;	
			items[clue.b.v].unify(clue.b.x);
		}
	});

What is happening? Why unifying would solve the puzzle?

Well we have created all variables with the according constrains and domains depending on the type of clues, clue variables are identified by their item name meaning same name refers to same variable so they must be unifiable.

A successful unified variable guaranties that no constrains on any unified variable are break and we can say that constrains are merged.

For example, lets say that we have a item "var0_0" on a "middle" constrain with x domain [1, 2, 3] and a immediately left constrain with same item "var0_0" and x domain [0, 1, 2, 3],
since the item is the same for both constrain variables we can unify the x variables and
since x must be in the middle the result of "var0_0" x coordinates domain would be
[1, 2, 3], by continuing to unify equal variables we are limiting x coordinate values for that variable (item) and if we end up with only one possible value for x coordinate than
position is determined.

Other deductions

Sometimes not so obviously deduction can be made, for this kind of deductions we use a brute force function called try values.

The function is very expensive since it will try all possible x variable values and check if any tried value would result on a variable with no values, if this happens than the value is marked as a not unifiable value, restricting the range of x possible values.

Since the function is very expensive I run it after all constrains have been applied, this will limit the number of possible values remaining.

vars.forEach (function (v) {
   v.tryValues(sl);
});

Generating Zebra Puzzles

The process of finding puzzles can be defined as this:

  • Let C be the set of all possible constrains
  • and S = Powerset(C).
  • for all elements s in S, s is valid puzzle if solve function can find a unique solution using s.

Now as you can imagine the size of search space will increase tremendous when increasing grid size and the number of constrains making it impossible to test all combinations.

I tried different search methods to speed up the search of a solution, I even tried genetic search, but they were taking to long, maybe my heuristic wasn't good enough.

Anyway I using a faster method, its a simple try and fail.

And it simple works like this:

  1. We start with a list of all clues,
  2. Shuffle the clues list,
  3. We try to find a clue that can be removed from our clue list (a clue can be removed if we can solve a puzzle with the remaining clues).
  4. When no more clues can be removed from the list we have found a puzzle and we stop.
  5. If a clue was taken from the list we repeat steps from step 2.

Well that’s it happy puzzling ;)

Posted in javascript, nodejs, prolog, zebrajs | Leave a comment

zebra.js: A variable constrain lib (javascript).

On my previews posts I talked about my tries on building a zebra puzzle generator, one of my goals was also to build constrain problem solver lib in Javascript with a prolog flavour.

I released the code on github zebrajs, and today I updated the code with a few improvements and some new features.

In this post I will talk about that changes.

zebrajs

The core of zebra lib are the variables, there is a few things that you can do with them:

Create a Variable

After importing variables lib, you can create a variable like this:

var a = v();

You can initialize a variable by passing a options object to the constructor, you can pass value and domain:

  • value (optional): the value of the variable,
  • domain (optional): an array of possible values that the variable can take.

Examples:

var a = v();
var b = v({value: "blue"});
var c = v({domain: ["red", "blue", "green"]});
var d = v({value: "blue", domain: ["red", "blue", "green"]});

Get value

The function getValue(), returns the variable value or undefined if variable as no value.
A variables with no initial value can return a value depending on variable manipulation and constrains.

var a = v();
var b = v({value: "blue"});
var c = v({domain: ["red", "blue", "green"]});
var d = v({value: "blue", domain: ["red", "blue", "green"]});
console.log(a.getValue()); // undefined
console.log(b.getValue()); // "blue"
console.log(c.getValue()); // undefined
console.log(d.getValue()); // "blue"

Unify

A variable can be unified with other var like this:

var a = v();
var b = v();
console.log(a.unify(b)); // true

Variable unification is like saying that variables are the same, meaning that if one of the unified vars get a value all other vars will have the same value.

Not all variables can be unified, a variable can only be successful unified if doesn’t break any constrains, for example:

var a = v({value: "blue"});
var b = v({value: "yellow"});
console.log(a.unify(b)); // false

a and b can’t be unified because they have different values.

Other example:

var a = v();
var b = v({value: "blue"});
a.unify (b);
console.log(a.getValue()); // "blue"

After unifying var a with b, a will get the b value.

A more interesting example:

var a = v([{domain: [1, 2, 3]});
var b = v([{domain: [3, 4, 5]});

console.log(a.getValue()); // undefined
console.log(b.getValue()); // undefined

a.unify(b);
console.log(a.getValue()); // 3
console.log(b.getValue()); // 3

Variable a and b, are initialized with possible values, but with no actual value.
After a is unified with b, the only possible value that a and b share is 3, since they must have the same value a and b can only be 3.

Set Value

A variable value can be set on initialization (always successful) or after initialization using setValue() function, like unify
a value can only be set if it doesn’t break any constrain.

Example:

var a = v();
var b = v();
a.unify(b);
console.log(a.setValue("blue")); // true
console.log(b.setValue("yellow")); // false

a and b start with no values and then a is unified with b, after a is set with value “blue” b will also have the same value “blue”, so setting b as “yellow” will
fail.

Not Unify

The function notUnify, sets a constrain on both variables than they can not have the same value.

Example:

var a = v();
var b = v();
a.notUnify(b);
console.log(a.setValue("blue")); // true
console.log(b.setValue("blue")); // false

a and b start with no values, and notUnify makes a and b distinct, meaning they cant have the same value, next variable a is set to value “blue” with success,
but setting b to same value (“blue”) will fail, since a and b cant have the same value.

* notUnify also affects unify behaviour, and unify affects notUnify behaviour.

Example:

var a = v();
var b = v();
var c = v();
console.log(a.notUnify(b)); // true
console.log(b.unify(c)); // true
console.log(a.unify(c)); // false

First a is set not to unify with b (a =/= b), next b is set to unify with c (b=c), so if a=/=b and b=c then a must be different from c, so unifying var a with c fails.

Set no value

The function setNoValue is used to discard possible values from the variable.

Example:

var a = v({domain: ["yellow", "blue", "red"]});
console.log(a.getValue()); // undefined
a.setNoValue("yellow");
a.setNoValue("red");
console.log(a.getValue()); // "blue"

The variable a is declared with possible values “yellow”, “blue” and “red”, after discarding possible values “yellow” and “red”, a can only be “blue”.

Get Values

The getValues functions will return all variable possible values (not the same as domain).

Example:

var a = v({domain: ["yellow", "blue", "red"]});
console.log(a.getValue()); // undefined
a.setNoValue("yellow");
console.log(a.getValues()); // ["blue", "red"]

While var a domain is “yellow”, “blue” and “red”, after discarding “yellow” as a possible value the only possible values remaining are “blue” and “red”.

Try Values

TryValues function is a brute force function that will try all possible variable values and check if other constrained variables hold (if they are guaranteed to have a value).

Example:

var a = v(domain: ["yellow", "blue", "red", "white", "green"]);
var b = v(domain: ["blue", "red", "white"]);
var c = v(domain: ["blue", "red", "white"]);
var d = v(domain: ["blue", "red", "white"]);
var e = v(domain: ["yellow", "blue", "red", "white", "green"]);

a.notUnify(b);
a.notUnify(c);
a.notUnify(d);
a.notUnify(e);

b.notUnify(c);
b.notUnify(d);
b.notUnify(e);

c.notUnify(d);
c.notUnify(e);

d.notUnify(e);

a.tryValues();
console.log(a.getValues()); // ["yellow", "green"]

The notUnify sets vars a, b, c, d and e as distinct, meaning they cant have the same value.

the a.tryValues will try to set all possible a values, and do the same to other vars, checking if all other vars still have at least on possible value.
For example, a=yellow, b=blue, c=red, d=white and e=”green” , is a possible outcome so yellow is a possible value.
But in case a=blue, b=red, c=white, but d cant be set to any value, even if we set b=white and c=red, d will still have no possible value so a cant be blue.

When tryValues end a can only have two possible values yellow and green.

Events: onchange

A function can be set to be triggered when a variable changes, a variable is considered to change if is value is change or possible values change.

Exemple:

var a = v({domain: ["blue", "red", "yellow"]});
a.onchange(function (v) {
  console.log(v.getValues());
});

a.setNoValue("yellow"); // it will trigger function that will print ["blue", "red"]

Thats almost it,

I also made a example on how to generate zebra puzzles, but since this is already a big post I will talk about that on
other post.

Happy coding ;)

Posted in Uncategorized | Leave a comment