Jumat, 25 April 2008

Puzzle Again ?

I've search in the internet about logical puzzles, most of them is very difficult to solve :)

But I found this one, maybe a little more alike to the first puzzle posted in this blog.



On the Shelf



Five children each have their favourite amongst the tinned foods stacked on

the bottom shelf of their mother's pantry. From the clues given below, can you

discover the contents and manufacturer's name on the label of each tin and say

whose preference it is?



Clues:

1) Danny's favourite is in a tin at one end of the shelf; it is not chicken

curry, which is not made by Williams.

2) The tin of Jones spaghetti stands next to Philip's choice, which is not

in an even-numbered tin.

3) Jenny's great love is baked beans; the tin containing them is further to

the left on the shelf than Clive's preference.

4) The ravioli is in the tin numbered 4 in the diagram.

5) Kate's favourite snack is made by Roberts.

6) The name 'Smiths' appears on the tin at the left-hand end of the shelf.



Children: Clive, Danny, Jenny, Kate, Philip.

Manufacturers: Bloggs, Jones, Roberts, Smiths, Williams.

Foods: baked beans, chicken curry, ravioli, spaghetti, tomato soup.



$$$

From the clues, we can define the scopes as :

Children(x)
x : {Clive,Danny,Jenny,Kate,Philip}

Manufacturers(x)
x : {Bloggs,Jones,Roberts,Smiths,Williams}

Tin(x)
x : {BakedBeans,ChickenCurry,Ravioli,Spaghetti,TomatoSoup}

and additional scope :

Number(x)
x: {1,2,3,4,5}

because it has 5 possible positions from left to right


We define the 1-1 relational scopes as :


Favourite(x,y)
x : {(Scope of Tin)} = {BakedBeans,ChickenCurry,Ravioli,Spaghetti,TomatoSoup}
y : {(Scope of Children)} = {Clive,Danny,Jenny,Kate,Philip}

Position(x,y)
x : {(Scope of Tin)} = {BakedBeans,ChickenCurry,Ravioli,Spaghetti,TomatoSoup}
y : {(Scope of Number)} = {1,2,3,4,5}

ProducedBy(x,y)

x : {(Scope of Tin)} = {BakedBeans,ChickenCurry,Ravioli,Spaghetti,TomatoSoup}
y : {(Scope of Manufacturer)} = {Bloggs,Jones,Roberts,Smiths,Williams}

And additional 1-1 relational scopes :

LessOne(x,y)
x : {(Scope of Number)} = {1,2,3,4,5}
y : {(Scope of Number)} = {1,2,3,4,5}

And additional many-to-many relational scopes :

Less(x,y)
x : {(Scope of Number)} = {1,2,3,4,5}
y : {(Scope of Number)} = {1,2,3,4,5}

We got the fact that :


ProducedBy(Spaghetti,Jones) => clue 2

Favourite(BakedBeans,Jeanny) => clue 3

Position(Ravioli,4) => clue 4

And additional facts :

LessOne(1,2)
LessOne(2,3)
LessOne(3,4)
LessOne(4,5)

False :


Favourite(ChickenCurry,Danny) => clue 1

ProducedBy(ChickenCurry,Williams) => clue 1



And the rules are :


Favourite(y,Danny) -> Position(y,1) v Position(y,5) => clue 1

StandsNext(Spaghetti,y) -> Favourite(y,Philip) => clue 2

Favourite(x,Philip) -> Position(y,1) v Position(y,3) v Position(y,5) => clue 2

LeftSide(BakedBeans,y) -> Favourite(y,Clive) => clue 3

Favourite(x,Kate) -> ProducedBy(x,Roberts) => clue 5

ProducedBy(x,Smith) -> Position(x,1) => clue 6


Additional Rules :

StandsNext -> RightSide(x,y) v LeftSide(x,y)
RightSide(x,y) -> Position(x,u) ^ Position(y,w) ^ LessOne(w,u)
LeftSide(x,y) -> Position(x,u) ^ Position(y,w) ^ Less(u,w)





Senin, 21 April 2008

Cutie




She's very cute, isn't she ?
I got the picture from my friend, but I don't know whose picture it is

Well, finally, after long working hours about 1 full months, my first running application for Einstein puzzle is ready to run!

Please try it and get it at :

http://www.geocities.com/anda198/PuzzleWorkout.zip


Please read the text files for more information, and if you need more, just send e-mail to khiong.khiong@gmail.com

Thanks !

Selasa, 15 April 2008

Scope

Warning : This posting may contains the spoiler of the quiz, read on your own risk ... :)

After we set the facts & rules, we must define the predicate, scope of each stament.
Predicate is a relation between an object to another.
Scope is the set of valid / possible values for the variables in a statement.

For example :

Position(x,y)

have the predicate Position and scope for x & y as :

x : set of possible countries : {Norwegian,Dane,Brit,German,Swede}
y : set of possible numbers : {1,2,3,4,5}

So, if we evaluate the statement :

Position(German,2)

It is a valid statement, but :

Position(France,7)

is not a valid statement (we can call it a negative statement, which value is FALSE)
because one or more values on the statement is not in the scope.

A true statement (fact) is also a valid statement.
But if a statement is valid does'nt mean it is a true statement.
For example, if we know that Norwegian house is the first house then

Position(Norwegian,1) => TRUE

If there is another statement says that German house is the first house then

Position(German,1)

The above statement is valid because the values is in the scope but we know it is not a fact, because the first position is already been filled by the Norwegian.

So :

Position(German,1) => FALSE

The predicate "Position" have a one-to-one relation, that means that one object can only related to one other object and cannot be related again to other object
So, if the Norwegian is placed #1 then the other countries cannot take the place

If the relation is not a one-to-one relation then some object can be related to more than one other object.

For example :

LivesNext(Brit,Dane) & LivesNext(Brit,German)

The Brit is lives next to Dane & the Brit is also lives next to German

$$$

Let's we see the list again :

Facts
LessOne(1,2)
LessOne(2,3)
LessOne(3,4)
LessOne(4,5)
HouseColor(Brit,Red)
Pet(Swede,Dogs)
Beverage(Dane,Tea)
Position(Norwegian,1)
Cigar(German,Prince)

Rules
LivesNext(x,y) -> LeftSide(x,y) v RightSide(x,y)
LeftSide(x,y) -> Position(x,v) ^ Position(y,z) ^ LessOne(v,z)
RightSide(x,y) -> Position(x,v) ^ Position(y,z) ^ LessOne(z,v)
HouseColor(x,Green) ^ HouseColor(y,White) -> LeftSide(x,y)
HouseColor(x,Green) -> Beverage(x,Coffee)
Cigar(x,PallMall) -> Pet(x,Bird)
HouseColor(x,Yellow) -> Cigar(x,Dunhill)
Position(x,3) -> Beverage(x,Milk)
Cigar(x,BlueMaster) -> Beverage(x,Beer)
Cigar(x,Blend) ^ Pet(y,Cat) -> LivesNext(x,y)
Pet(x,Horse) ^ Cigar(y,Dunhill) -> LivesNext(x,y)
HouseColor(x,Blue) -> LivesNext(x,Norwegian)
Cigar(x,Blend) ^ Beverage(y,Water) -> LivesNext(x,y)

so we can define the scope based from statements above &
the question (WHO KEEPS FISH? :)) :

Scope
LessOne(x,y)
1-1 Relation
x: {1,2,3,4}
y: {2,3,4,5}
HouseColor(x,y)
1-1 Relation
x: {Norwegian,Dane,Brit,German,Swede}
y: {Yellow,Blue,Red,Green,White}
Pet(x,y)
1-1 Relation
x: {Norwegian,Dane,Brit,German,Swede}
y: {Bird,Dog,Horse,Cat,Fish}
Beverage(x,y)
1-1 Relation
x: {Norwegian,Dane,Brit,German,Swede}
y: {Milk,Beer,Tea,Water,Coffee}
Position(x,y)
1-1 Relation
x: {Norwegian,Dane,Brit,German,Swede}
y: {1,2,3,4,5}
Cigar(x,y)
1-1 Relation
x: {Norwegian,Dane,Brit,German,Swede}
y: {PallMall,BlueMaster,Blend,Dunhill,Prince}
LivesNext(x,y)
x: {Norwegian,Dane,Brit,German,Swede}
y: {Norwegian,Dane,Brit,German,Swede}
LeftSide(x,y)
1-1 Relation
x: {Norwegian,Dane,Brit,German,Swede}
y: {Norwegian,Dane,Brit,German,Swede}
RightSide(x,y)
1-1 Relation
x: {Norwegian,Dane,Brit,German,Swede}
y: {Norwegian,Dane,Brit,German,Swede}

$$$

The scope is useful to check the validity of a rule & check the available values that is not yet used

When we have some facts and the 1-1 relation scope, then the available values is the set of scope exclude the values used in facts.

For example :

Position(Norwegian,1)
Position(Brit,3)
Position(German,4)
Position(Swede,5)

The scope is :

Position(x,y)
1-1 Relation
x: {Norwegian,Dane,Brit,German,Swede}
y: {1,2,3,4,5}

The available values is :

Position(x,y)
1-1 Relation
x: {Dane}
y: {2}

So we can get a new fact :

Position(Dane,2)

$$$

Maybe we are not always get available values with only one combination left, but we can make a solution with the help of some rules

For example :

Beverage(x,y) : (3 combination left)
1-1 Relation
x: {Norwegian,German,Swede}
y: {Beer,Water,Coffee}

Related Rules (Have a predicate "Beverage") : (2 Rules)

HouseColor(x,Green) -> Beverage(x,Coffee)
Cigar(x,BlueMaster) -> Beverage(x,Beer)

Related Facts : (Related in predicate to 2 Rules above)
HouseColor(Norwegian,Yellow)
Cigar(Norwegian,Dunhill)

We can conclude that :
Beverage(Norwegian,Coffee) => FALSE
Beverage(Norwegian,Beer) => FALSE

So, for x = Norwegian, then :

Beverage(Norwegian,y) :
1-1 Relation
y: {Beer,Water,Coffee}

Exclude the Coffee & Beer from the list of Beverage :

Beverage(Norwegian,y) :
1-1 Relation
y: {Water}

So, we got a solution :

Beverage(Norwegian,Water)

$$$

Selasa, 08 April 2008

Define the Puzzled

Good morning,

About the logical deduction of the Einstein Quiz I've said before, I got the inspiration from the a program called PROLOG (Which I learned it when I got the AI course from my undergraduate College, but I forget what is it's stands to :)) , which can make an answer given some facts & some rule, but it seems like when I try to give input of Einstein Quiz to Prolog, I don't now how to do it because it is so complicated. So I try to create a computer program that can do the deduction for this Quiz only. Maybe after I successfully developed the program, it can be solved to other Quiz maybe (only in my dream ... hahaha ..:) ) But it's still under the development ...

Before I develop the program, I wrote some logical deduction in a textfile, using logical syntax.
I started to develop the program from year 2002, but because of the business (it's busi-ness : kesibukan in Bahasa) as a programmer analyst, the project was suspended sometimes. At first, I developed the program using Visual Basic 6.0, but to continue follow the fastness changes of technology, currently I'm using Visual Basic .NET 2005 (but still out of date to now .. compared to the new Visual Basic .NET 2008 that just released lately :( )

So let's start to create a list of logical statements, from the Quiz statements.

The Brit lives in a red house.
The Swede keeps dogs as pets.
The Dane drinks tea.
The Norwegian lives in the first house.
The German smokes Prince.

The 5 statements above are facts (I called so) so we can write :

HouseColor(Brit,Red)
Pet(Swede,Dogs)
Beverage(Dane,Tea)
Position(Norwegian,1)
Cigar(German,Prince)

Note :
HouseColor(Brit,Red) is read in Englist : Brit has (a) house color of Red
Pet(Swede,Dogs) is read : Swede has pets of dogs, etc

The other statements is :

The green house is on the left of the white house.
The green house owner drinks coffee.
The person who smokes Pall Mall rears birds.
The owner of the yellow house smokes Dunhill.
The man living in the house right in the centre drinks milk.
The man who smokes Blend lives next to the one who keeps cats.
The man who keeps horses lives next to the man who smokes Dunhill.
The owner who smokes Blue Master drinks beer.
The Norwegian lives next to the blue house.
The man who smokes Blend has a neighbor who drinks water.

The 10 statements above I called "Rule" (maybe someone can give a better term to me)
and can be written as :

HouseColor(x,Green) ^ HouseColor(y,White) -> LeftSide(x,y)
HouseColor(x,Green) -> Beverage(x,Coffee)
Cigar(x,PallMall) -> Pet(x,Bird)
HouseColor(x,Yellow) -> Cigar(x,Dunhill)
Position(x,3) -> Beverage(x,Milk)
Cigar(x,BlueMaster) -> Beverage(x,Beer)
Cigar(x,Blend) ^ Pet(y,Cat) -> LivesNext(x,y)
Pet(x,Horse) ^ Cigar(y,Dunhill) -> LivesNext(x,y)
HouseColor(x,Blue) -> LivesNext(x,Norwegian)
Cigar(x,Blend) ^ Beverage(y,Water) -> LivesNext(x,y)

Note :
^ = AND logical operator
v = OR logical operator
-> = Conclude

About the statement :

The man living in the house right in the centre drinks milk.
Because there is 5 persons live in the neighborhood, so the center must be in position 3
(It's kinda cheating because I don't write it "as is", but it's helping to solve the problem :p)
So : Position(x,3) -> Beverage(x,Milk)

After that, we create (actually, it's not create, but "define") additional rules & facts :

Rules :
-------
LivesNext(x,y) -> LeftSide(x,y) v RightSide(x,y)
LeftSide(x,y) -> Position(x,v) ^ Position(y,z) ^ LessOne(v,z)
RightSide(x,y) -> Position(x,v) ^ Position(y,z) ^ LessOne(z,v)

Facts :
-------
LessOne(1,2)
LessOne(2,3)
LessOne(3,4)
LessOne(4,5)

Note :
------
LessOne(1,2) is read : 1 is less one of 2 because the difference of 2 to 1 (2-1) is one, right ?
The facts above I added because I want to make an position order from one house to the other

That' all folks! I will continue this in other time. Thanks for reading! And see you later ... :)

Puzzled

Hello all,

This is my first blog, and I would like to post the very interesting Quiz ever made,
the Einstein Quiz. Sorry if my English is not good because I actually just learn to make an English Blog. And I'm sorry if the content is not very much informative to you. I've read about this Quiz at year 2000 in Indonesian version and already solve it, but it's still interesting to resolve it again. But I don't believe that only 2% of the people in the world, maybe the other is just give up to continue solving the problem because so many rule to be checked.

I also interested to logical deduction of this quiz. About that I will post it in other posting ...

The Einstein Quiz
Einstein said that 98% of people in the world cannot solve the following puzzle. And Einstein was usually right (that's why he's Einstein.) Here is the Einstein Quiz:
Facts:
There are 5 houses in 5 different colors.
In each house lives a person with a different nationality.
These 5 owners drink a certain beverage, smoke a certain brand of cigar and keep a certain pet.
No owners have the same pet, smoke the same brand of cigar or drink the same drink.
Hints:
The Brit lives in a red house.
The Swede keeps dogs as pets.
The Dane drinks tea.
The green house is on the left of the white house.
The green house owner drinks coffee.
The person who smokes Pall Mall rears birds.
The owner of the yellow house smokes Dunhill.
The man living in the house right in the centre drinks milk.
The Norwegian lives in the first house.
The man who smokes Blend lives next to the one who keeps cats.
The man who keeps horses lives next to the man who smokes Dunhill.
The owner who smokes Blue Master drinks beer.
The German smokes Prince.
The Norwegian lives next to the blue house.
The man who smokes Blend has a neighbor who drinks water.
Question:
Can you determine WHO KEEPS FISH?

Note : This Quiz is copied from the website http://www.amazeingart.com/fun/einstein-quiz.html