Zebra puzzle
Elliot Smith
zebra puzzle, or for solving general 'logic puzzles'?
Personal replies preferred: E.Smith...@cs.bham.ac.uk
Thanks.
Elliot Smith
Jean-Francois Puget
Constraint (Logic) Programming (CLP) is a very nice way to solve such problems.
I give below the Ilog Solver code needed to solve the zebra problem.
Ilog Solver is a C++ contraint programming library, that implements Constraint
Logic Programming concepts. If you want to know more about this library,
some scientific papers are available on our web server:
http://www.ilog.fr
select Solver in the product section, then select papers.
More general information about CLP is discussed in the
comp.constraints newsgroup.
// -------------------------------------------------------------- -*- C++ -*-
// File: zebra.cc
// --------------------------------------------------------------------------
#include <iostream.h>
#include <ilsolver/ctint.h>
void NextTo (const IlcIntExp v1, const IlcIntExp v2) {
// v2 - v1 is either -1 or 1
IlcTell(IlcAbs(v2-v1) == 1);
}
main (){
IlcInit();
IlcIntVar england (0,4), spain(0,4), japan(0,4), italy(0,4), norway(0,4);
IlcIntVar dog(0,4), zebra(0,4), fox(0,4), snails(0,4), horse(0,4);
IlcIntVar juice(0,4), water(0,4), tea(0,4), coffee(0,4), milk(0,4);
IlcIntVar painter(0,4), diplomat(0,4), violonist(0,4), doctor(0,4), sculptor(0,4);
IlcIntVar green(0,4), red(0,4), yellow(0,4), blue(0,4), white(0,4);
IlcIntExpArray allvars(25,
england, spain, japan, italy, norway,
dog, zebra, fox, snails, horse,
juice, water, tea, coffee, milk,
painter, diplomat, violonist, doctor, sculptor,
green, red, yellow, blue, white);
IlcTell(IlcAllDiff(allvars.extract(0, 5))); // england, spain, japan, italy, norway
IlcTell(IlcAllDiff(allvars.extract(5, 5))); // dog, zebra, fox, snails, horse
IlcTell(IlcAllDiff(allvars.extract(10, 5))); // juice, water, tea, coffee, milk
IlcTell(IlcAllDiff(allvars.extract(15, 5))); // painter, diplomat, violonist, doctor, sculptor
IlcTell(IlcAllDiff(allvars.extract(20, 5))); // green, red, yellow, blue, white
IlcTell(red == england);
IlcTell(spain == dog);
IlcTell(japan == painter);
IlcTell(italy == tea);
IlcTell(green == coffee);
IlcTell(sculptor == snails);
IlcTell(diplomat == yellow);
IlcTell(violonist == juice);
IlcTell(milk == 2);
IlcTell(norway == 0);
IlcTell(green == white + 1);
NextTo(norway, blue);
NextTo(fox, doctor);
NextTo(horse, diplomat);
IlcSolve (IlcGenerate(allvars));
cout << "Zebra is in house: " << zebra.getValue() << endl;
IlcEnd();
return 0;
}
--
Jean-Francois Puget net : pu...@ilog.fr
ILOG S.A. url : http://www.ilog.fr
2 Avenue Gallieni - BP 85 tel : +33 1 46 63 66 66
F-94253 Gentilly Cedex FRANCE fax : +33 1 46 63 15 82
Peter Ludemann
Elliot Smith <E.Smith...@cs.bham.ac.uk> wrote:
>Can anyone give me an idea of where to find code for solving the
>zebra puzzle, or for solving general 'logic puzzles'?
I have made a small collection of zebra puzzle solutions in Prolog
and Life: ftp://ftp.netcom.com/pub/lu/ludemann/zebra.tar.gz.
--
Peter Ludemann lude...@netcom.com
{wuertz
Another system with constraint solving capabilities is Oz. It provides for
encapsulated search and finite domain constraints. The finite domain system
is fully integrated in the higher-order concurrent setting of Oz.
Oz provides for records used for representing the data set. The Oz code for solving
the zebra problem is enclosed.
For more information on Oz and related research
check the following web server: http://ps-www.dfki.uni-sb.de/oz/
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% zebra.oz
declare
proc {Zebra Sol}
%% In 5 houses live people from different nations with
%% different professions...
!Sol = zebra(england: England
spain: Spain
japan: Japan
italy: Italy
norway: Norway
green: Green
red: Red
yellow: Yellow
blue: Blue
white: White
painter: Painter
diplomat: Diplomat
violinist: Violinist
doctor: Doctor
sculptor: Sculptor
dog: Dog
zebra: Zebra
fox: Fox
snail: Snail
horse: Horse
juice: Juice
water: Water
tea: Tea
coffee: Coffee
milk: Milk)
Ds = {Record.toList Sol}
in
Ds ::: 1#5
England = Red
Spain = Dog
Japan = Painter
Italy = Tea
Norway = 1
Milk = 3
Violinist = Juice
Green = Coffee
Sculptor = Snail
Diplomat = Yellow
Green =: White + 1
OR Norway =: Blue - 1 [] Norway =: Blue + 1 RO
OR Fox =: Doctor - 1 [] Fox =: Doctor + 1 RO
OR Snail =: Diplomat - 1 [] Snail =: Diplomat + 1 RO
{FD.allDifferent [England Spain Japan Italy Norway]}
{FD.allDifferent [Green Red Yellow Blue White]}
{FD.allDifferent [Painter Diplomat Violinist Doctor Sculptor]}
{FD.allDifferent [Dog Zebra Fox Snail Horse]}
{FD.allDifferent [Juice Water Tea Coffee Milk]}
{FD.enums Ds}
end
in
{Search query(Zebra)}
{Search next}
% End of zebra.oz
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-------------------------------------------------------------------------------
Tobias Mueller | tel: +49 681 302-5261
Programming Systems Lab | fax: +49 681 302-5341
DFKI, Stuhlsatzenhausweg 3 | net: tmue...@dfki.uni-sb.de
D-66123 Saarbruecken, Germany | url: http://ps-www.dfki.uni-sb.de/~tmueller/
-------------------------------------------------------------------------------