The Poor Man JavaScript Prolog… (Sudoku Optmization)

On the previews post I presented a implementation to solve Sudoku using some ideas from Prolog. On my test case I said that it takes ~26 seconds to solve and ~3 minutes to find all possible solutions.

In this post I will present a simple and efficient optimization that have a huge impact on the solver performance.

For example my test case takes now only ~0.2 seconds to solve and ~4 seconds to find all possible solutions.

The optimization is very simple, we want to reduce the number of fails and tries by
selecting a good candidate.

A good candidate would be a position with few possible numbers to try, meaning it would be the most restricted.
Example:

 1  2  3   4  5  6   7  8  9
[_, _, _] [3, _, _] [_, _, _] A 
[8, _, _] [_, _, _] [_, 2, _] B
[_, 7, _] [_, 1, _] [5, _, _] C
	
[4, _, _] [_, _, 5] [3, _, _] D
[_, 1, _] [_, 7, _] [_, _, 6] E
[_, _, 3] [2, _, _] [_, 8, _] F
	
[_, 6, _] [5, _, _] [_, _, 9] G
[_, _, 4] [_, _, _] [_, 3, _] H
[_, _, _] [_, _, 9] [7, _, _] I

Lets consider 9B not equal restrictions = [2, 5, 6, 8, 9],
so possible values would be [1, 3, 4, 7].

Lets now consider 8C not equal restrictions = [1, 2, 3, 5, 7, 8] so
possible values would be [4, 6, 9], so 8C is a better candidate then 9B.

We continue to check empty positions until we find the one with the higher number of not equal restrictions or the one with less possible values.

After having the best candidate we try possible values and we repeat the process until we find a solution or fail.

The code is here:

Posted in javascript, prolog | Leave a comment

The Poor Man JavaScript Prolog…

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&lt;9; i+=3) {
		for (var j=0; j&lt;9; j+=3) {
			distinct (grid, i, j, 3, 3);
		}
	}

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

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

sudokuConstrains(grid);

In the code above I say that rows, columns and 3×3 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.

All code and a zebra solution can be found here:

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 :D

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

Posted in Uncategorized | Leave a comment