zebra.js: Generating Zebra puzzles.

What do you think of this post?
  • Awesome (0.0%)
  • Interesting (0.0%)
  • Useful (0.0%)
  • Boring (0.0%)
  • Sucks (0.0%)

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 5x5 "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 😉

What do you think of this post?
  • Awesome (0.0%)
  • Interesting (0.0%)
  • Useful (0.0%)
  • Boring (0.0%)
  • Sucks (0.0%)

2 thoughts on “zebra.js: Generating Zebra puzzles.

  1. I am interested only in Zebra generator, and this is the second time I see the same approach to generating the puzzle (generating side is pretty thin on the net, unlike solving it). And what I don’t like with this approach that you have to have solver just to check if the clues are sufficient. I hope there is middle way — which is enough to check if the puzzle is not ambigous without actually computing the solution.

    1. Hi,
      I understand what you are saying I have the same problem looking for a zebra puzzle generator algorithm.
      Well I am still working on my zebra lib and trying to improve it and I think there is one possibility to check if constrains are enough without running all combinations.
      Lets say that our constrains vars have a domain, by adding constrains the variable will get less possible values, you will reach a unique solution when variables have only one possible value, because if you end up with more values it means constrains are not enough to restrict variables values.
      This approach don’t require backtrack that will try all possible values until fail or end. Now what I am not sure is that there may be more complex deductions that may not be applied (at least on my lib) and using backtrack I force a try/fail search that I know it will drain all possible solutions.
      My last implementation (https://github.com/fsvieira/zebrajs/blob/master/examples/zebra/puzzleslib.js#L405) uses kind of both, there is still a lot to improve, the idea is simple, I apply
      clue constrains using unify that will constrain the values and then I try to find one solution using backtrack. If I could improve the constrain mechanism on variables I think I could discard backtrack. What do you think?

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>