All posts by fsvieira

My Imaginary Operating System.

I kind of feel bad for not posting anything for so long, and so I decided to make a post about some ideas and random thoughts about my imaginary operating system.

First the problems that I identify for a new operating system:

  • Fragmentation:
    It creates users and developers division that are forced to choose between where they will run their favorite applications.
    In the end people just want to run applications with the least amount of effort.
  • Applications: the number of applications on a operating system depends on the number of developers that are creating new applications, and this
    is normally related with the number of users, therefor its a cycle/loop, we need developers to get users, we need users to get developers.
  • Developing: Operating systems are complex, hardware support is not easy sometimes closed and non-existing and they take a long time to develop.
  • Cant remember anything else…

My imaginary operating system should have this:

  • It should run everywhere: even on top of other operating systems as an application, on the browser, on the cloud, doesn’t matter.
    This should combat the fragmentation problem:

    • first we get users on the browser, where they can easily try the OS and switch to their host OS.
    • If users like the browser version they will get it as an application, that has more features (like file system access).
    • If users like the application version they will start trying the standalone OS.
  • It should build its own cloud: every instance of the operating system should be a node on the cloud, so if you are running on your android, desktop computer, tv, browser all resources are shared on the OS private cloud, such as CPU, files, … Same operating system everywhere.
  • Developing: to run everywhere the best option I think would be html5/js. The operating system should separate all services with a [REST] API, the client UI could be implemented as html5 or any other technology (but html5 would be better).
    The rest service should be stateless and use tokens. Client applications can be separated using different tokens and living on a complete isolated environment using frames.

Implementation Plan

  • First I would try to define a Operating System API that should be kind of a standard. The API should work locally and remotely, implementation doesn’t matter (this can be achieved by a rest service coupled with some client server library’s).
  • Its a good idea to separate Server (API) and Client (UI) as independent projects,
    this will allow server developers to concentrate efforts on doing a very stable server without concerning how data will be handled and displayed to the user,
    it will also give many options to client developers that would have the freedom to choose any technology and library’s that they like.
  • The server could be implemented as:
    • Headless Server: using nodejs with modules like express, fs …
    • Desktop Application: using nodewebkit that can use nodejs server and allow to call directly the API from the UI.
    • Mobile Application: similar to desktop app but implemented on cordova.
    • Standalone:The easy solution would be running linux booting to the “headless server” or “desktop application”. But what would be really
      great would be something like runtimejs

After a little of research I found the most promising, open-source, projects:

  • runtimejs,
    “Operating system kernel built on V8 JavaScript engine”. Its a very interesting project using v8 as intermediate layer between the hardware
    and the software, this level of abstraction makes it possible to code almost everything in javascript even drivers.

    I didn’t test it yet, but reading the page there is very interesting features and ideas: isolates, rpc’s, …

  • OS.js-v2,
    “OS.js is a JavaScript web desktop implementation for your browser with a fully-fledged window manager, Application APIs, GUI toolkits and filesystem abstraction.”.

Moving to OpenShift Host

From Godaddy To OpenShift

I am moving to other host, I will try to check all links and review everything so until I am finish it might be a lot of broken stuff here.


When I started my hobby website I decided to buy a cheap host, so I found Goddady with a nice price, at the time a shared host was very cheap and cheaper if I buy it for 4 years, so I did and I got stuck with Godaddy for 4 years. Now, after four years the host is going to expire, witch for me is not a bad thing because I wanted to move to other host that has better support, better management tools and nodejs would be a plus. But, since its a hobby, I didn’t want to spend much money on it, fortunately I found very good solutions being one of them the OpenShift.

Why OpenShift

When I started looking for cheap hosts with nodejs I always got to cloud servers, there was two with free plan that actually caught my attention OpenShift and Heroku.

Both of them are kind of similar, both have console management tools, git and are scalable. On Heroku I particular liked how easily you can manage and share the resources used by each application..on OpenShift if is possible its not so obvious.

Anyway, after trying to setup my wordpress blog on both, I quickly decided to go with OpenShift for the simple reason that the free plan as MySQL DB needed by wordpress and it has more DB space. Heroku free plan has a PostGresSQL DB and wordpress doesnt support it out of the box.

Until now OpenShift is …

…Great :D, I am really happy with OpenShift:

  • Free Plan: The free plan is a great feature on any service, because it lets you try it and see if it fits your needs. Besides the motto “Pay as you grow” make sense to me, its a great way to get customers and a good marketing tool. But yeah I like it because I don’t have to pay 😀
  • Git:For any project involving developing its great to have a version control system, and its great to use it as a deploying system as well. OpenShift uses git as
    the primary tool to deploy applications live.
    On my “real” work I always update my services and websites to deploy with git, its a simple matter of pull the master branch. Normally I use 2 “standard” branch’s: master (production ready branch) and dev (merge master ready branch). Any other developments are made on other branch’s.
  • Certificate Authentication: Tools like git and other OpenShift tools can login with a certificate so you only need to set it up once on your computer and then you never
    need to worry about authentication again 😀
  • Management Shell tools: OpenShift applications can be manage with a single shell command tool. The “rhc” command can perform a lot of management task, like
    setting up your account certificate, and a lot of other stuff. I especilly like the command
    rhc ssh , it simple starts the ssh shell where your app is.
  • Nodejs It supports nodejs :D…

There is probably a lot more great features that I will discover with time.

OpenShift DNS pain…

Attention that OpenShift is not domain name registrar or provider/management, but I need to put my domain names to work with it.
The biggest problem I found was to configure my domains names to work as they did before.

The problem is that I am using to point to my page and web services, I recently discovered that this kind of names are called naked or root domains, and apparently is not a good idea to use them on the web stuff.

The problem is that I can use a cname (alias) to a sub-domain, like points to , but I cant use an cname (alias) with, this limitation
seems not only be on the domain providers but also on the RFC, and with good reason, because
root domain name can be used on other services.

Anyway, so I made a sub-domain and point to my cloud, then I redirect (301) to with forward only because masking is really bad, it makes a iframe with source pointing to your redirect address, so the url will never change on address bar and if you have rest service send json it will be bad.

Redirect seemed to work ok, everything I access it was changed to and everything looked good.

But when I try to use my (ajax) rest public service (with cors enabled to allow everyone) it fails. It works for but not with because of the redirect.

So, the solution was to make a CNAME for to point to the cloud, and I did it with
cloudflare, it is very easy you don’t need to transfer the domain to be able to use their services and for what I saw there is plenty of interesting services that they provide.


OpenShift is a great hosting solution, even for hobbyists. CloudFare is great to manage your domain names and do stuff that you cant do with other domain providers.

If I knew what I know now I sure would have used the to point to my services,
it would have been much more simple to change them ;).

Thats it, I hope to finish the migration of my website very soon, and sorry for any broken links and pages.

zebrajs update, testing and testcase generation

ZebraJS Update

The last few days I have been rewriting the variables lib, this updates includes:

  • Added examples (exemples/logic/add.js), from my previews post,
  • Better memory management with version system (commit, revert, remove) instead the old dumb stack (save and load) system,
  • simplified the code to achieve better performance,
  • Testing and debugging libs:
    • lib/variables_test.js: Monitors all lib operations and throws a exception if it finds a inconsistency on the lib,
    • lib/variables_test_msg.js: Monitors all lib operations and stops the program with a error message,
    • lib/variables_testcase.js: Monitors all lib operations and stops the program with a error message and generates a testcase for mocha.

The sudoku puzzle takes now, almost 3 seconds to solve and check for all possibilities:
real 0m2.837s
user 0m2.496s
sys 0m0.038s

I think its good since we have to take into account the time nodejs takes to start up the program.

Testing and testcase generation

When we rewrite part of a program bugs will always appear especially on big rewrites, that’s why having a test framework is useful, we run all the test and fix everything that doesn’t pass the tests, then we run our examples and they all fail and burn lol…
So I think its good practice to find bugs and write some more test, this will prevent future fail, and will also confirm your bug suspicions…The problem is when you write a bunch of testcases but all of them passes, meaning that the bug is more tricky than you would expect.

So after I got tired to write tests, I tried to find a good tool to help me, but I found none, the problem was:

  • Debugger: Node-inspector doesn’t work very well for me and besides debugging requires a little work and inspection to find bugs,
  • Profiler: I cant understand the output of profilers and cant get the information that I need,
  • Symbolic Execution: I have been reading about this, seems great but didn’t find anything for nodejs,
  • Other options: There is probably other options, I just made a quick search didn’t bother to look how to personalize the tools to make what I expected…shame on me 😛 (any suggestion or comments are welcome)

So I decided to take on other approach, I made a proxy class, that has this features:

  • Monitor all calls of a object,
  • For every call made it constructs a call trace with the provided arguments,
  • Extensible with the functions:
    • before: execute before call,
    • after: execute after call,
    • error: execute if a exception occurs
  • Run the trace again and generate a minimal test case.
  • Setting up proxy trace should be only a matter of changing the require libs to proxy libs, no other changes in the code should be made.

And this is how its working for zebrajs lib:

  • I created a proxy to Variables and VariablesFactory,
  • On after and before calls I check my variables integrity with the should.js lib, if something wrong occurs I throw an exception,
  • On my error handling function I call proxy.sandbox to generate a small test case where the error occurs,
  • I go to one of examples, and change the ‘require(“lib/variables”)’ with my proxy ‘require(“lib/variables_testcase”)’, and then run the example like this
    ‘nodejs my_example.js > log.txt’. If a error occurs it will present me with a testcase on the bottom of the log.txt.
  • I copy the testcase to my mocha test/ folder, normally I change the testcase adding more tests, check the expected values and change them to what they should be, ect, etc…
  • I then correct the bugs, check if everything is right and keep the testcase for future development 😉

Until now I think this proxy object is pretty useful to test “real” programs/examples, of course not everything is great, proxy lib may have bugs (it probably has, since the code is a mess), the check functions may have bugs, the performance is decreased a lot and some testcases may take some time to generate.

Here is a testcase that was generated (This error occur as normal exception of js, the test case generated was really big, I then added some checks to catch the bug early…):

 it("should f_0 commit", function() {
                var f_0 = new VariableFactory();
                var v_71 = f_0.v({domain:[1,2,3,4,5,6,7,8,9], });
                var v_80 = f_0.v({domain:[1,2,3,4,5,6,7,8,9], });
                        invalid version number < 0
                        f_0 commit
                should(f_0.commit()).eql(0); // I changed this from -1 to 0 since it was the correct expected value,

This is a little trick bug, since it didn’t occur if I comment one of the lines with notUnify, It was cool to see that the test case generated was
exactly the smallest to the error occur, it made my day lol...
And that’s it 😉 ...

Testcase generator algorithm

The testcase generator is a pretty dumb piece of code, when a error occurs I do the following on proxy.sanbox:

  • It grabs only the calls on the root of the trace, its not interested on internal calls, and do a list,
  • After call list is created it will setup a "clean" and "controlled" environment to execute the calls,
  • Then it runs the call list, ignoring calls from the bottom of the list, if the error still occurs than it can remove the ignored call,
    it continues to do this until it reaches the beginning of the list,
  • It then creates a string, as a mocha testcase, with the remaining calls in the list, since it has all information like returned values it can
    create assertions of the expected values, of course some of them may be wrong but that’s must be checked by the programmer, and a wrong assertion is
    definitely a bug.

Well that’s it, Happy codding.

zebrajs facts: take that prolog :D

Today for fun I decided to implement some mathematical operators/logic operator on the zebrajs lib.

So I decided to make a post on the add operator.

The add implementation uses the idea of facts in prolog.
In prolog a fact is expressed like this:

father(rolando, filipe);
father(rolando, isabel);

Above I am simple saying that rolando is the father of filipe and isabel, and that is fact.
When I execute for example father(X, filipe), X will take the value rolando.

On the zebrajs there is no notion of facts, but a similar behaviour can be implemented, this is how I did it:

function Facts (values, factory, args, callback) {
	return function () {
		values.forEach(function (value) {
			if (value.length === args.length) {
				var ok = true;;
				for (var i=0; i!==args.length; i++) {
					ok = value[i].unify(args[i]);
					if (!ok) {break;}
				if (ok) {

And the function can be used like this to define for example AND operator:

function AND (p, q, r, callback) {
	return Facts ([
		[v({domain: [0]}), v({domain: [0]}), v({domain: [0]})],
		[v({domain: [0]}), v({domain: [1]}), v({domain: [0]})],
		[v({domain: [1]}), v({domain: [0]}), v({domain: [0]})],
		[v({domain: [1]}), v({domain: [1]}), v({domain: [1]})]
	], factory, [p, q, r], callback);	

The fact functions takes a table of values, and return a function that will try to unify the input variables with the variables on the table if it succeeds to unify a full table line then a solution was found and a callback function is called.

For example:

var AND(v(), v(), v({domain: [1]}), function (vars) {
  console.log(vars[0].getValue() + " AND " + vars[1].getValue() + " = " + vars[2].getValue());

It will print: “1 AND 1 = 1″, because the only line that can be unified with the input values is the last one “[v({domain: [1]}), v({domain: [1]}), v({domain: [1]})]”

Now the same thing can be done to define a simple 1 bit ADD operator, I will define
the ADD with input: p + q = r, c (previews operation carry) and cc (carry).
The table will contain all possible values to compute 1-bit add operation, for example:
p + q + c = r, cc
0 + 0 + 0 = 0, 0
0 + 0 + 1 = 1, 0
0 + 1 + 0 = 1, 0

1 + 1 + 1 = 1, 1

function ADD (p, q, c, r, cc, callback) {
	return Facts ([
		[v({domain: [0]}), v({domain: [0]}), v({domain: [0]}), v({domain: [0]}), v({domain: [0]})],
		[v({domain: [0]}), v({domain: [0]}), v({domain: [1]}), v({domain: [1]}), v({domain: [0]})],
		[v({domain: [0]}), v({domain: [1]}), v({domain: [0]}), v({domain: [1]}), v({domain: [0]})],
		[v({domain: [0]}), v({domain: [1]}), v({domain: [1]}), v({domain: [0]}), v({domain: [1]})],
		[v({domain: [1]}), v({domain: [0]}), v({domain: [0]}), v({domain: [1]}), v({domain: [0]})],
		[v({domain: [1]}), v({domain: [0]}), v({domain: [1]}), v({domain: [0]}), v({domain: [1]})],
		[v({domain: [1]}), v({domain: [1]}), v({domain: [0]}), v({domain: [0]}), v({domain: [1]})],
		[v({domain: [1]}), v({domain: [1]}), v({domain: [1]}), v({domain: [1]}), v({domain: [1]})],
	], factory, [p, q, c, r, cc], callback);

This operator can now be used to construct a n-bit operator, the input now would
be an array of variables (on reverse order), for example, p=2=[v({domain: [0]}), v({domain: [1]})]=10 (binary).

function ADDn (p, q, r, callback) {
	var c = v({domain: [0]});
	var f = function () {
		callback(p, q, r);
	p.forEach (function (_p, index) {
		var cc = v();
		f = ADD(_p, q[index], c, r[index], cc, f);
		c = cc;
	return f;

This function will construct a sequence of ADDs passing carry flag from one operation to other, a 2 bits operation would look something like this:
– ADD(p1, q1, v({domain: [0]), r1, cc, ADD(p2, q2, cc, r2, cc2, callback));
Notice that cc is the carry of first operation that is passed to the second operation.

Now I can use add function like this:

var add = ADDn([v(), v()], [v(), v()], [v(), v()], callback);

To make things simpler I defined a function to generate variables from decimal number to zebrajs vars and wrap it up on a nice add function.

And now the fun part :), use add function to solve [simple] equations, like this a+b=9:

var a = add(undefined, undefined, 9, 5 /* number of bits */, add_print); a();

And the result would is:

decimal: 2 + 7 = 9
bits: 00010 + 00111 = 01001

decimal: 3 + 6 = 9
bits: 00011 + 00110 = 01001

decimal: 6 + 3 = 9
bits: 00110 + 00011 = 01001

decimal: 7 + 2 = 9
bits: 00111 + 00010 = 01001

decimal: 4 + 5 = 9
bits: 00100 + 00101 = 01001

decimal: 5 + 4 = 9
bits: 00101 + 00100 = 01001

decimal: 0 + 9 = 9
bits: 00000 + 01001 = 01001

decimal: 1 + 8 = 9
bits: 00001 + 01000 = 01001

decimal: 8 + 1 = 9
bits: 01000 + 00001 = 01001

decimal: 9 + 0 = 9
bits: 01001 + 00000 = 01001

decimal: 10 + -1 = 9
bits: 01010 + 11111 = 01001

decimal: 11 + -2 = 9
bits: 01011 + 11110 = 01001

decimal: 14 + -5 = 9
bits: 01110 + 11011 = 01001

decimal: 15 + -6 = 9
bits: 01111 + 11010 = 01001

decimal: 12 + -3 = 9
bits: 01100 + 11101 = 01001

decimal: 13 + -4 = 9
bits: 01101 + 11100 = 01001

decimal: -6 + 15 = 9
bits: 11010 + 01111 = 01001

decimal: -5 + 14 = 9
bits: 11011 + 01110 = 01001

decimal: -2 + 11 = 9
bits: 11110 + 01011 = 01001

decimal: -1 + 10 = 9
bits: 11111 + 01010 = 01001

decimal: -4 + 13 = 9
bits: 11100 + 01101 = 01001

decimal: -3 + 12 = 9
bits: 11101 + 01100 = 01001

decimal: -14 + -9 = 9
bits: 10010 + 10111 = 01001

decimal: -13 + -10 = 9
bits: 10011 + 10110 = 01001

decimal: -10 + -13 = 9
bits: 10110 + 10011 = 01001

decimal: -9 + -14 = 9
bits: 10111 + 10010 = 01001

decimal: -12 + -11 = 9
bits: 10100 + 10101 = 01001

decimal: -11 + -12 = 9
bits: 10101 + 10100 = 01001

decimal: -16 + -7 = 9
bits: 10000 + 11001 = 01001

decimal: -15 + -8 = 9
bits: 10001 + 11000 = 01001

decimal: -8 + -15 = 9
bits: 11000 + 10001 = 01001

decimal: -7 + -16 = 9
bits: 11001 + 10000 = 01001

Some results are not mathematical right, this is due to overflow, in this case the number of bits is limited to 5, the same problem would occur on a normal CPU.

The cool part of defining operator this way is that they work on any direction, so we can have any number of unknown variables. The operator can be chained to make a equation and they can be solved by just running it.

For example I had defined a multiply function, this function can easily be used to calculate
a square root, example: x*x=16, x would be solved to 4.

The multiply function is much more complicated and really slow:

function MULn (p, q, r, callback) {

	var grid = [];
	var l = p.length;
	var f = function () {
		callback(p, q, r);
	for (var i=0; i<l ; i++) {
		var line = [];
		for (var j=0; j<i; j++) {
			line.push(v({domain: [0]}));

		p.forEach(function (_p, index) {
			var a = v();
			var b = q[i];

			f = AND(_p, b, a, f);
		for (var j=line.length; j<r.length; j++) {
			line.push(v({domain: [0]}));
		var gl = grid.length;
		if ((gl > 0) && !(grid.length&1)) {
			// 1, 2, [3], 4, [5]
			// save intermidiate add results.
			var line;
			if (i===l-1) {
				line = r;
			else {
				line = [];
				for (var j=0; j<r .length; j++) {

			// 0 1 [2], 2-2=0, 2-1=1, 2
			f = ADDn(grid[gl-2], grid[gl-1], grid[gl], f);
	return f;

It was fun to define this operators but there are still a lot of problems before any practical use for this.


  • Operations are too slow, not only operators should be optimized but also the zebrajs lib
  • Overflow results on wrong mathematical results, it should be a way to handle and avoid this.

The code is not yet on the repository, I will try to at least clean the code before a commit 😉

zebrajs improvements


(** Zebrajs a constrain problem solving lib **)

Recently I discover that my zebrajs lib was broken, mostly because of type conversion, so I decided that was time to start adding automated testing to the lib.

I didn’t want anything to much complicated so I choose the mocha with should.js and I am very happy with it.

The test file is here they are pretty simple.

Now with tests I hope to avoid breaking the lib and that it became much more stable.

Try it out 😀 and give me some feedback.

Balance a web and mobile math game


Balance is the next version of my ball12 game with a new interface.

Balance is a Logical game inspired by a famous variation of weighing coin mathematical problems.

In this game you have 12 balls, 11 of them have the same weight and 1 of them has a different weight, it could be heavier or lighter. You have a two plate’s scale and your goal is to find which ball has a different weight, and if it is heavier or lighter than the others. You have to find this out with just three weightings to get the best score.

Source Code

I released the source code of the game here Its a simple small game so I think anyone looking for a ionic/angular example to study may find the code usefully (even if the code is not great, and all messy lol).

The Algorithm

If you have read the previews (balls12) game algorithm you will find this one much more easy, because we don’t need to keep track of the individual balls, just total for each group like: Equal, Heavier, Lighter and Unknown.
Maybe I will explain the algorithm on some post, if anyone is interested please post it on the comments.

Happy coding/gaming :)

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:

  {"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.


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++) {

		a.x = v({domain:domain});
		var domain = [];
		for (var i=1; i < grid.w; 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.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) {

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)){

	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;
		if (clue.b) {
			items[clue.b.v] = items[clue.b.v] || 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) {

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 😉

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.


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.


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"


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

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.


var a = v();
var b = v();
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

Not Unify

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


var a = v();
var b = v();
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.


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.


var a = v({domain: ["yellow", "blue", "red"]});
console.log(a.getValue()); // undefined
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).


var a = v({domain: ["yellow", "blue", "red"]});
console.log(a.getValue()); // undefined
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).


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"]);





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.


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

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 😉

The Poor Man JavaScript Prolog: Generate zebra puzzle! (Part 4)

I just released the zebra puzzle generator on github as variable constrain lib.

I said I would clean up a bit the code, but its still pretty messy…

To run the generator go to folder examples/zebra and type:

nodejs main.js

The generator is very slow so it may take several minutes to generate the puzzles.

The puzzles are saved on a file as json format like this:

[{"constrains":[{"type":"next to","x":"dunhill","y":"dane"},{"type":"middle","x":"pallmall","y":null},{"type":"next to","x":"white","y":"tea"},{"type":"next to","x":"milk","y":"water"},{"type":"immediately to the left of","x":"water","y":"dog"},{"type":"next to","x":"beer","y":"norwegian"},{"type":"immediately to the left of","x":"prince","y":"horse"},{"type":"immediately to the left of","x":"horse","y":"cats"},{"type":"same position as","x":"yellow","y":"birds"},{"type":"immediately to the left of","x":"swede","y":"zebra"},{"type":"same position as","x":"blue","y":"dog"},{"type":"middle","x":"green","y":null},{"type":"middle","x":"coffee","y":null},{"type":"immediately to the left of","x":"german","y":"bluemaster"},{"type":"middle","x":"english","y":null},{"type":"immediately to the left of","x":"bluemaster","y":"prince"}],"missing":["red","blend"],"solution":{"houses":["yellow","blue","green","white","red"],"drinks":["water","milk","coffee","beer","tea"],"people":["german","swede","english","dane","norwegian"],"smokes":["blend","bluemaster","prince","pallmall","dunhill"],"animal":["birds","dog","zebra","horse","cats"]}}]

Its a array of objects, every object is a generated puzzle and contains the following keys:

  • “constrains”: the clues of the puzzle, every clue contain the type of the clue and one (x) or two (y) values.
  • “missing”: the values that are missing from the constrains/clues, normally this would be two. For example: “missing”:[“red”,”blend”].

    Missing values can be presented to user like this:

    • One of the houses is red,
    • Someone smokes blend.
    • or as a question: Who lives in red house and who smokes blend.
    • or in a graphical GUI like grids or something like that you can just present all values and no need to reference the missing values.
  • “solution”: the solution for this puzzle, the solution is on the format of type: [values], for example:

    {“houses”:[“yellow”,”blue”,”green”,”white”,”red”], “drinks”:[“water”,”milk”,”coffee”,”beer”,”tea”], …}

    In this example the people living in yellow house drink water.

Now that I have something working I will try to optimize the lib and generator, first I will try to optimize the algorithms but when that is done I would like to try to web-workers/threads to speed up things :) (that would be fun…)

Happy coding.