Monthly Archives: March 2014

The Poor Man JavaScript Prolog…

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

Update: This post is outdated and you can now find this project at github zebrajs.

I have been playing a fun game based on Zebra/Einstein puzzle.

So my first idea was to do a puzzle generator, and I started to think that Prolog would be a nice tool for the job, but since I like JavaScript much more, I ended up doing other exercise: basically I wanted to get the features that I like in Prolog in JavaScript with a nice JavaScript flavor.

One of the features that I like in Prolog is variable unification and also backtracking, I actually tried a lot of ways to store “facts”, backtracking and other stuff, but
in the end it just puts a complex and restrictive layer to the code.

So I just implemented a Variable Object/Class that does two important things:

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

As a test I implemented a Sudoku solver:

First I setup my test case, I found this one on the Internet, they say its one of the most hard Sudokus ever made and I believe them it takes ~26 seconds to solve and ~3 minutes to find all possible solutions, in this case it found only one solution.

var grid = [
  // 1    2    3    4    5    6    7    8    9
  [v(), v(), v(5), v(3), v(), v(), v(), v(), v()], // 1
  [v(8), v(), v(), v(), v(), v(), v(), v(2), v()], // 2
  [v(), v(7), v(), v(), v(1), v(), v(5), v(), v()], // 3
	
  [v(4), v(), v(), v(), v(), v(5), v(3), v(), v()], // 4
  [v(), v(1), v(), v(), v(7), v(), v(), v(), v(6)], // 5
  [v(), v(), v(3), v(2), v(), v(), v(), v(8), v()], // 6
	
  [v(), v(6), v(), v(5), v(), v(), v(), v(), v(9)], // 7
  [v(), v(), v(4), v(), v(), v(), v(), v(3), v()], // 8
  [v(), v(), v() , v(), v(), v(9), v(7), v(), v()], // 9
];

Now I must initialize the grid constrains, with some help functions:

function distinct (grid, sx, sy, ex, ey) {
	ex += sx;
	ey += sy;

	for (var x=sx; x < ex; x++) {
		for (var y=sy; y < ey; y++) {
			for (var x1=sx; x1 < ex; x1++) {
				for (var y1=sy; y1 < ey; y1++) {
					if (!((x===x1) && (y===y1))) {
						grid[x][y].not_unify(grid[x1][y1]);
					}
				}
			}
		}
	}
};

function sudokuConstrains (grid) {
	// squares
	for (var i=0; i<9; i+=3) {
		for (var j=0; j<9; j+=3) {
			distinct (grid, i, j, 3, 3);
		}
	}

	// rows
	for (var i=0; i<9; i++) {
		distinct (grid, 0, i, 9, 1);
	}

	// col
	for (var i=0; i<9; i++) {
		distinct (grid, i, 0, 1, 9);
	}
	
	return grid;
}

sudokuConstrains(grid);

In the code above I say that rows, columns and 3x3 squares have distinct values, I use
the not_unify variable method to do this.

Next I wrote a function to try all possible values, if a value fail to unify then the function returns and try other value, a kind of lame backtracking system, every time the function tries a unification the affected variables are saved and then restored. If a result is found a callback function is called with the resulting grid:

function it (grid, i, j, callback) {
	if (i === grid.length) {
		callback(grid);
	}
	else {
		if (grid[i][j].getValue() !== undefined) {
			if (j === grid[i].length-1) {
				it(grid, i+1, 0, callback);
			}
			else {
				it(grid, i, j+1, callback);
			}
		}
		else {		
		   [v(1), v(2), v(3), v(4), v(5), v(6), v(7), v(8), v(9)]
                     .forEach(function (v) {
				grid[i][j].save();
				if (grid[i][j].unify(v)) {
					if (j === grid[i].length-1) {
						it(grid, i+1, 0, callback);
					}
					else {
						it(grid, i, j+1, callback);
					}
				}
				
				grid[i][j].load();
			});
		}
	}
};

Now I just need to call it:

it (grid, 0, 0, print);

Print is the callback function, to print the results.

The zebra solution has a small problem it prints the correct solution but prints it
many times :( … But it only takes ~0.6 seconds to solve 😀

Variables

The variables use a very simple algorithm:

  • All variables have two arrays, one for unifiable variables and other to not unifiable variables
  • Unification is successful if:
    • Variable/value is not in the not unifiable array (recursive),
    • At least one of the variables to be unified is not initialized or both variables have same value.
    • If unification is successful the variable is inserted in unifiable array.
  • Not Unification is successful if:
    • Variable/value is not in the unifiable array (recursive),
    • At least one of the variables to be not unified is not initialized or variables have different value.
    • If not unification is successful the variable is inserted in not unifiable array.

Thats all 😉 Happy codding…

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