Monthly Archives: May 2014

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

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

“”Zebra/Einstein puzzle is basically a constraint problem, where you have to find a unique solution that satisfy all constraints.
Its fun and can be easily solved on paper.””

I think my zebra puzzle generator is now making some interesting puzzles, so I decided to
post one of them, I tried make the generated text more natural, but my English is not very good and I don’t want to change it too much or I might change the meaning of constrains…
so here it goes:

  • The norwegian lives next to the person that smokes dunhill
  • The swede lives immediately to the left of the house with a horse.
  • The white house is in the middle.
  • The in the middle house they drink beer.
  • The person that drinks coffee lives immediately to the left of the house with a zebra.
  • The person that has cats lives immediately to the left of the house with a dog.
  • The red house is next to the house where they drink milk.
  • They have birds in the blue house.
  • The person who smokes blend lives immediately to the left of the house with cats.
  • They have a zebra in the green house.
  • The english lives immediately to the left of the house where they smoke pallmall.
  • The person that smokes bluemaster lives in the middle.
  • The german lives next to the house where they drink water.
  • The person that smokes pallmall lives immediately to the left of the house where they smoke blend.
  • The dane lives in the middle.
  • The person that drinks tea is next to the house where they drink coffee.

Who lives in the yellow house and who smokes prince?

Code…

Now I just need to clean up a bit my code and soon I probably make a release on github.

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

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

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

“”Zebra/Einstein puzzle is basically a constraint problem, where you have to find a unique solution that satisfy all constraints.
Its fun and can be easily solved on paper.””

I tried some ideias from my last post to generate some zebra puzzles, and I got some results:
I think the puzzles are still to easy, but I will post some here hopping they are at least fun :) [Let me know in the comments]…

Ah, to solve the puzzles you must assume that there is:

  • there is five houses : yellow, blue, red, green, white
  • there is five drinks : water, tea, milk, coffee, beer
  • there is five people : norwegian, dane, english, german, swede
  • there is five smokes : dunhill, blend, pallmall, prince, bluemaster
  • there is five animals: cats, horse, birds, zebra, dog

Puzzle 1

The milk is in the middle.
The milk is immediately to the left of norwegian
The milk is immediately to the left of tea
The beer is immediately to the left of horse
The horse is immediately to the left of dog
The green is immediately to the left of beer
The red is immediately to the left of green
The red is next to water
The white is immediately to the left of horse
The blue is immediately to the left of pallmall
The white is same position as german
The white is same position as dunhill
The english is next to swede
The beer is immediately to the left of prince
The water is immediately to the left of cats
The english is immediately to the left of bluemaster
The birds is next to english

Puzzle 2

The coffee is in the middle.
The coffee is immediately to the left of norwegian
The coffee is immediately to the left of milk
The beer is immediately to the left of dog
The dog is immediately to the left of birds
The yellow is immediately to the left of beer
The white is immediately to the left of yellow
The white is next to water
The green is immediately to the left of dog
The red is immediately to the left of prince
The green is same position as english
The green is same position as blend
The german is next to dane
The beer is immediately to the left of bluemaster
The water is immediately to the left of horse
The german is immediately to the left of pallmall
The zebra is next to german

Puzzle 3

The milk is immediately to the left of dunhill
The beer is immediately to the left of water
The german is next to zebra
The white is immediately to the left of milk
The beer is in the middle.
The yellow is immediately to the left of horse
The milk is immediately to the left of horse
The beer is immediately to the left of swede
The yellow is same position as english
The yellow is same position as prince
The horse is immediately to the left of cats
The coffee is immediately to the left of dog
The dane is next to german
The german is immediately to the left of bluemaster
The blue is immediately to the left of white
The green is immediately to the left of blend
The coffee is next to blue

The Algorithm

I am using a very naive algorithm and it takes almost 16 minutes to generate a puzzle, I still need to try other things before posting the code.

So the algorithm goes something like this:

  1. Generate a random solution,
  2. Generate a list of all possible constrains,
  3. Search for the constrain that can reduce possibilities to a maximum,
  4. Save that constrain and try the remaining constrains: using previews method,
  5. Apply saved constrains before try new constrains,
  6. Keep doing this until a solution is found, the saved constrains are the result.

Things that I think it would improve the result:

  • Apply saved constrains every time a new constrain is successfully applied, so that all deduction are taken in to account,
  • When constrains have same weight choose random,
  • When random selecting constrains with same weight favour the type of constrains with less occurrences in the result,
  • Suffle result, because constrains are tried by order there is a chance that puzzles look alike.

Right now I am not very concerned with the time that takes to generate the puzzle and more concerned with generating nice puzzles to play.

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

The Poor Man JavaScript Prolog: Generate zebra puzzle!

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.

“”Zebra/Einstein puzzle is basically a constraint problem, where you have to find a unique solution that satisfy all constraints.
Its fun and can be easily solved on paper.””

On my previews post “The Poor Man JavaScript Prolog: solving zebra puzzle!” I solved zebra puzzle in JS, but the fun part is to generate the zebra puzzles alikes.

Generating a puzzle is more challeging than just solving it because you need to anwser a important question: how can I generate a fun or hard puzzle that people will enjoy playing?

Using some ideas of the solver from my previews post I constructed a program to generate zebra puzzles but while it generates correct puzzles (with a unique solution) they tend to be too easy with lots of redundant constrains.

How it works?

First I generate a random solution like this:

var colors  = [v({value:"yellow"})    , v({value:"blue"})   , v({value:"red"})     , v({value:"green"})  , v({value:"white"})];
var drinks  = [v({value:"water"})     , v({value:"tea"})    , v({value:"milk"})    , v({value:"coffee"}) , v({value:"beer"})];
var people  = [v({value:"norwegian"}) , v({value:"dane"})   , v({value:"english"}) , v({value:"german"}) , v({value:"swede"})];
var smokes  = [v({value:"dunhill"})   , v({value:"blend"})  , v({value:"pallmall"}), v({value:"prince"}) , v({value:"bluemaster"})];
var animals = [v({value:"cats"})      , v({value:"horse"})  , v({value:"birds"})   , v({value:"zebra"})  , v({value:"dog"})];

var _solution = {
        houses: shuffle(colors),
	drinks: shuffle(drinks),
	people: shuffle(people),
	smokes: shuffle(smokes),
	animal: shuffle(animals)
};

Basically I generate grid with values in random position, example:

houses: yellow green red blue white 
drinks: tea water beer milk coffee 
people: swede norwegian english dane german 
smokes: prince bluemaster blend pallmall dunhill 
animal: zebra birds cats horse dog 

Next I generate a list with all possible constrains, my program uses 4 types of constrains:

  1. X is immediately to the left of Y,
  2. X is next to Y,
  3. X is at same position as Y.
  4. X is at the middle.

So from my previews example I would generate a list more or less like this:

[left_of(yellow, green), left_of(yellow, birds), ... left_of(blue, white), ... middle(birds) ...] 

Now the difficult part is to select from the constrains set a subset that generates a unique solution and at the same time is difficult, my program for now is just concerned with generating a unique solution, so the implementation is very simple:

  1. Generate the Set of all possible constrains, lets call it C,
  2. Order C in a random order (suffle(C)),
  3. Solve the puzzle by trying constrains in C by order, if constrain when applied doesn’t have any effect just ignore it otherwise save it on result list,
  4. Repeat step 2, until solution is found.

So the solving function looks like this:

function paths (state, constrains, res) {
	res = res || [];
	var change = false;
	
	constrains.forEach(function (c) {
            if (c.constrain(c.x, c.y, state)) {
               if (res.indexOf(c) === -1) {
	          res.push(c);
	       }
	       tryValues(state);
               change = true;
            }
	});
	
	change && paths(state, shuffle(constrains), res);

	return res;
};

function tryValues (state) {
	var change = false;
	for (var t in state) {
		state[t].forEach (function (v) {
			v.tryValues();
		});
	}
};

The try values is one of the new features added to variables, it checks for possible values of the variable by running all variable constrains, for example:

lets say that I have five houses a, b, c, d and e.
The variables a and e have this possible values [yellow, green],
and b, c, d have this possible values: [yellow, blue, red, white, green]

Since a, b, c, d and e must have distinct values we can assume that b, c, d possible values
are in fact: [blue, red, white].

The tryValues works by applying all possible values to a variable and it does this to all variable constrains, when all constrains are successfully unified with a value then the value is ok else its not a possible value.

from the above example lets try:

  1. b=yellow
  2. a=green
  3. Since e cant be the same as b and a, then possible values for e=[], so b can’t be yellow.

The tryValues is a very expensive function. So if I just want to solve the zebra puzzle I put this function after all constrains are executed because tryValues would be executed with much more constrains so less values to try. But to generate the puzzle I want my program to find the solution by using less constrains, so I always run it immediately after a successful constrain to make sure that all deduction are made before try other constrain.

Generated solutions

Here is an example of a generated solution:

=== constrains === 
Total: 32
The dane is in the middle.
The water is immediately to the left english
The zebra is immediately to the left birds
The red is immediately to the left dane
The beer is same position as english
The pallmall is immediately to the left dunhill
The blend is in the middle.
The dane is immediately to the left german
The tea is immediately to the left water
The red is next to horse
The red is same position as cats
The blue is immediately to the left dunhill
The green is immediately to the left beer
The pallmall is immediately to the left dog
The blend is immediately to the left pallmall
The red is immediately to the left horse
The milk is in the middle.
The milk is immediately to the left dunhill
The english is immediately to the left horse
The beer is immediately to the left pallmall
The water is same position as birds
The blue is same position as dane
The norwegian is immediately to the left cats
The water is immediately to the left blend
The english is same position as blend
The blue is same position as horse
The cats is next to water
The water is same position as bluemaster
The green is next to english
The green is immediately to the left english
The yellow is next to norwegian
The red is next to dane

== Solution ==
houses: yellow green red blue white 
drinks: tea water beer milk coffee 
people: swede norwegian english dane german 
smokes: prince bluemaster blend pallmall dunhill 
animal: zebra birds cats horse dog 

The first problem is the redundant constrains, for example:

  1. “The green house is next to english”
  2. “The green house is immediately to the left english”

The second constrain make the first one useless since
“next to” is like this: “green english” or “english green”
and “left to” is like this: “green english”

This is one of the obvious, but there are others more subtle…

Other problems are related to the question:

How to generate fun or hard to solve puzzles?

I am still figuring out this part.

But heres what I think:

  • The result should have a max limit of allowed constrains, for the following reasons:
    1. A big list of constrains may not be very appealing to people,
    2. After a certain number of constrain any added constrain is probably redundant,
    3. It reduces significantly the search space.
  • Would size be a factor to a difficult level?
    • Less constrains make me think that there is more deduction’s involved,
      but not sure if this is true, but searching for the min solution seems a good idea.

    Update:

  • Constrain variety, from the point of view of a “player” it might be more pleasant to read from a constrain list that as more variety. This is probably does kind of parameters that could be used to untie decisions.

So considering the above parameters I think what I need to do is just make a strategy to sort constrains so the “better” ones are tried first.

I also need to check how to avoid redundancy.

Thats it, please leave your ideas on the comments, I searched for an algorithm to do this but cant find any…

Happy codding ;).

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