Archive

Posts Tagged ‘prolog’

Einstein Riddle/Zebra Puzzle in Prolog

einsteinIn this post we solve another logic puzzle deriving rules from the puzzle and stating them in Prolog. And this time it is a rather famous puzzle one: the Zebra puzzle (also called Einstein riddle/puzzle).

The puzzle

The setting is as follows: there is a group of 5 people. Each person lives in exactly one house, has exactly one nationality and exactly one pet, drinks exactly one drink and smokes exactly one brand of cigarettes. Different goals are possible: a famous one is “who drinks water and who owns the zebra”. But one could instead also define the goal to derive for all houses and people: who lives is which house, has which nationality and which pet, drinks which drink and smokes which brand of cigarettes – given the fact, that each of these attributes is unique among the people in our group. This is the question we are going to answer. The following hints are provided (from Wikipedia):

  1.     There are five houses.
  2.     The Englishman lives in the red house.
  3.     The Spaniard owns the dog.
  4.     Coffee is drunk in the green house.
  5.     The Ukrainian drinks tea.
  6.     The green house is immediately to the right of the ivory house.
  7.     The Old Gold smoker owns snails.
  8.     Kools are smoked in the yellow house.
  9.     Milk is drunk in the middle house.
  10.     The Norwegian lives in the first house.
  11.     The man who smokes Chesterfields lives in the house next to the man with the fox.
  12.     Kools are smoked in the house next to the house where the horse is kept.
  13.     The Lucky Strike smoker drinks orange juice.
  14.     The Japanese smokes Parliaments.
  15.     The Norwegian lives next to the blue house.

Puzzle solution in Prolog

We now need to write the knowledge from above as Prolog rules and ask for a solution fulfilling these rules:

% ####################################################################
% Zebra puzzle solver. A house is a list with 6 attributes:
% 1. Color
% 2. Nationality
% 3. Drink
% 4. Cigarettes
% 5. Pet
% 6. The housenumber (fixed by hand to avoid redundant solutions)
%
% Steps to obtain the solution:
%
% 1) Read definition to prolog:
%   ['zebra_puzzle.pl'].
%
% 2) Ask for solutions:
%   solve(H1,H2,H3,H4,H5).
%
% Rainhard Findling
% 09/2015
% ####################################################################

all_members([H],L2) :- member(H,L2).
all_members([H|T],L2) :- member(H,L2), all_members(T, L2).

% ####################################################################
% RULES
% ####################################################################

% rule 1 (5 houses) is implicit for our implementation

rule2(H1,H2,H3,H4,H5) :-
    member(H, [H1,H2,H3,H4,H5]),
    H = [red,england,_,_,_,_].

rule3(H1,H2,H3,H4,H5) :-
    member(H, [H1,H2,H3,H4,H5]),
    H = [_,spain,_,_,dog,_].

rule4(H1,H2,H3,H4,H5) :-
    member(H, [H1,H2,H3,H4,H5]),
    H = [green,_,coffee,_,_,_].

rule5(H1,H2,H3,H4,H5) :-
    member(H, [H1,H2,H3,H4,H5]),
    H = [_,ukraine,tea,_,_,_].

rule6(H1,H2,H3,H4,H5) :-
    member(HL,[H1,H2,H3,H4,H5]),
    member(HR,[H1,H2,H3,H4,H5]),
    HL = [white,_,_,_,_,NrL],
    HR = [green,_,_,_,_,NrR],
    NrR-NrL =:= 1.

rule7(H1,H2,H3,H4,H5) :-
    member(H, [H1,H2,H3,H4,H5]),
    H = [_,_,_,altemgold,snails,_].

rule8(H1,H2,H3,H4,H5) :-
    member(H, [H1,H2,H3,H4,H5]),
    H = [yellow,_,_,kools,_,_].

rule9(_,_,H3,_,_) :-
    H3 = [_,_,milk,_,_,3].

rule10(H1,_,_,_,_) :-
    H1 = [_,norway,_,_,_,1].

rule11(H1,H2,H3,H4,H5) :-
    member(HL,[H1,H2,H3,H4,H5]),
    member(HR,[H1,H2,H3,H4,H5]),
    HL = [_,_,_,chesterfield,_,NrL],
    HR = [_,_,_,_,fox,NrR],
    abs(NrL-NrR,1).

rule12(H1,H2,H3,H4,H5) :-
    member(HL,[H1,H2,H3,H4,H5]),
    member(HR,[H1,H2,H3,H4,H5]),
    HL = [_,_,_,kools,_,NrL],
    HR = [_,_,_,_,horse,NrR],
    abs(NrL-NrR,1).

rule13(H1,H2,H3,H4,H5) :-
    member(H, [H1,H2,H3,H4,H5]),
    H = [_,_,orange,luckystrike,_,_].

rule14(H1,H2,H3,H4,H5) :-
    member(H, [H1,H2,H3,H4,H5]),
    H = [_,japan,_,parliament,_,_].

rule15(H1,H2,H3,H4,H5) :-
    member(HL,[H1,H2,H3,H4,H5]),
    member(HR,[H1,H2,H3,H4,H5]),
    HL = [_,norway,_,_,_,NrL],
    HR = [blue,_,_,_,_,NrR],
    abs(NrL-NrR,1).

% ####################################################################
% solve the puzzle
% ####################################################################

solve(H1,H2,H3,H4,H5) :-
    % bind houses to position to avoid multiple solutions with switched variables
    H1 = [H1_col,H1_nat,H1_drink,H1_cig,H1_pet,1],
    H2 = [H2_col,H2_nat,H2_drink,H2_cig,H2_pet,2],
    H3 = [H3_col,H3_nat,H3_drink,H3_cig,H3_pet,3],
    H4 = [H4_col,H4_nat,H4_drink,H4_cig,H4_pet,4],
    H5 = [H5_col,H5_nat,H5_drink,H5_cig,H5_pet,5],
    % the rules
    rule2(H1,H2,H3,H4,H5),
    rule3(H1,H2,H3,H4,H5),
    rule4(H1,H2,H3,H4,H5),
    rule5(H1,H2,H3,H4,H5),
    rule6(H1,H2,H3,H4,H5),
    rule7(H1,H2,H3,H4,H5),
    rule8(H1,H2,H3,H4,H5),
    rule9(H1,H2,H3,H4,H5),
    rule10(H1,H2,H3,H4,H5),
    rule12(H1,H2,H3,H4,H5),
    rule13(H1,H2,H3,H4,H5),
    rule14(H1,H2,H3,H4,H5),
    rule15(H1,H2,H3,H4,H5),
    % for all variable ensure that all values exist
    all_members([white, green, red, blue, yellow], [H1_col,H2_col,H3_col,H4_col,H5_col]),
    all_members([spain, japan, england, ukraine, norway], [H1_nat,H2_nat,H3_nat,H4_nat,H5_nat]),
    all_members([orange, coffee, milk, tea, water], [H1_drink,H2_drink,H3_drink,H4_drink,H5_drink]),
    all_members([luckystrike, parliament, altemgold, chesterfield, kools], [H1_cig,H2_cig,H3_cig,H4_cig,H5_cig]),
    all_members([dog, zebra, snails, horse, fox], [H1_pet,H2_pet,H3_pet,H4_pet,H5_pet]).

If executed, two possible solutions are printed:

['zebra_puzzle.pl'].
solve(H1,H2,H3,H4,H5).

H1 = [yellow, norway, water, kools, zebra, 1],
H2 = [blue, ukraine, tea, chesterfield, horse, 2],
H3 = [red, england, milk, altemgold, snails, 3],
H4 = [white, spain, orange, luckystrike, dog, 4],
H5 = [green, japan, coffee, parliament, fox, 5] ;

H1 = [yellow, norway, water, kools, fox, 1],
H2 = [blue, ukraine, tea, chesterfield, horse, 2],
H3 = [red, england, milk, altemgold, snails, 3],
H4 = [white, spain, orange, luckystrike, dog, 4],
H5 = [green, japan, coffee, parliament, zebra, 5] ;

That’s it, puzzle solved! 😉

Solving Logic Puzzles in Prolog: Puzzle 3 of 3

December 27, 2015 Leave a comment

In this post we solve another small logic puzzle in Prolog, similar to the previous two logic puzzles (these are available here and here).

The puzzle

There are four researchers: Ainsley, Madeline, Sophie and Theodore. The goal is to find out their sports competition discipline, birth year and research interests (while knowing that each of the mentioned attributes is different amongst them). In order so solve the puzzle, a couple of hints is provided from which the solution can be derived:

  1. The competition for Theodore or Ainsley is javelin.
  2. The researcher interested in hurricane research has relay as sports subject.
  3. Sophie is not the researcher who has relay as sports subject.
  4. Either the researcher who has longjump as sports subject or Theodore was born in 1933 – the other one was born in 1921.
  5. The researcher with relay as sports subject was born before Theodore.
  6. The researcher interested in wildfires was born after the researcher doing longjumps for sports.
  7. Neither Sophie nor Ainsley are researching wildfires.
  8. The researcher interested in earthquakes has either hurdle or javelin as sports interest.
  9. The researcher interested in earthquakes was born in 1933.
  10. Madeline was not born in 1921.

Solving the puzzle in Prolog

In our Prolog implementation we ask for a solution that a) ensures that all sports subjects, research interests and birth years exist once and b) fulfills the rules mentioned above:

% ####################################################################
% Logic puzzle solver.
%
% Read definition to prolog:
%   ['puzzle.pl'].
%
% 2) Ask for solutions:
%   solve(Ainsley, Madeline, Sophie, Theodore).
%
% Rainhard Findling
% 10/2015
% ####################################################################
all_members([H],L2) :- member(H,L2).
all_members([H|T],L2) :- member(H,L2), all_members(T, L2).

and([H]) :- H.
and([H|T]) :- H, and(T).
or([H]) :- H,!.
or([H|_]) :- H,!.
or([_|T]) :- or(T).

solve(Ainsley, Madeline, Sophie, Theodore) :-
    All = [Ainsley, Madeline, Sophie, Theodore],
    Ainsley = [Ainsley_Year, Ainsley_Competition, Ainsley_Disaster],
    Madeline = [Madeline_Year, Madeline_Competition, Madeline_Disaster],
    Sophie = [Sophie_Year, Sophie_Competition, Sophie_Disaster],
    Theodore = [Theodore_Year, Theodore_Competition, Theodore_Disaster],
    % we know what all variable must be
    all_members([1920, 1921, 1933, 1973], [Ainsley_Year, Madeline_Year, Sophie_Year, Theodore_Year]),
    all_members([hurdle, relay, javelin, longjump], [Ainsley_Competition, Madeline_Competition, Sophie_Competition, Theodore_Competition]),
    all_members([earthquakes, hurricanes, tornados, wildfires], [Ainsley_Disaster, Madeline_Disaster, Sophie_Disaster, Theodore_Disaster]),
    % c1
    or([Ainsley_Competition = javelin, Theodore_Competition = javelin]),
    % c2
    member([_, relay, hurricanes], All),
    % c3
    not(Sophie_Competition = relay),
    % c4
    member([C4_Year, longjump, _], All),
    or([and([Theodore_Year = 1921, C4_Year = 1933]), and([Theodore_Year = 1933, C4_Year = 1921])]),
    % c5
    member([C5_Year, relay, _], All),
    Theodore_Year > C5_Year,
    % c6
    member([C6_1_Year, longjump, _], All),
    member([C6_2_Year, _, wildfires], All),
    C6_1_Year < C6_2_Year,
    % c7
    not(Sophie_Disaster = wildfires),
    not(Ainsley_Disaster = wildfires),
    % c8
    member([_, C8_competition, earthquakes], All),
    not(C8_competition = hurdle),
    not(C8_competition = javelin),
    % c9
    member([1933, _, earthquakes], All),
    % c10
    not(Madeline_Year = 1921).

Using this implementation, if we ask for a solution, the single possible solution is presented:

['puzzle.prolog'].
% puzzle.prolog compiled 0.00 sec, 13 clauses
true.

?- solve(Ainsley, Madeline, Sophie, Theodore).
Ainsley = [1920, relay, hurricanes],
Madeline = [1973, hurdle, wildfires],
Sophie = [1933, longjump, earthquakes],
Theodore = [1921, javelin, tornados] ;

Solving Logic Puzzles in Prolog: Puzzle 2 of 3

November 29, 2015 1 comment

This post is about solving the 2nd of 3 small logic puzzles in Prolog. The previous post is available here.

The puzzle

Eilen, Ada, Verena and Jenny participated in a painting competition. Find out who painted which subject and who took which place in the competition, using the hints provided. Hints:

    1. Eilen painted a constable and was not last in the competition
    2. Jenny took the third place
    3. The person painting the Monet took the first place
    4. Ada beat the person painting a talyor, and the person painting a Van Gogh beat Vera

Solving the puzzle in Prolog

We just translate the hints into rules that ensure that a) places 1-4 and all mentioned painting subjects exist in our solution and b) the mentioned hints are fulfilled:

% ####################################################################
% Logic puzzle solver.
%
% Read definition to prolog:
% ['puzzle.pl'].
%
% 2) Ask for solutions:
% solve(Eilen, Ada, Vera, Jenny).
%
% Rainhard Findling
% 10/2015
% ####################################################################
all_members([H],L2) :- member(H,L2).
all_members([H|T],L2) :- member(H,L2), all_members(T, L2).

solve(Eilen, Ada, Vera, Jenny) :-
% 4 members
All = [Eilen, Ada, Vera, Jenny],
Eilen = [Eilen_place, Eilen_subject],
Ada = [Ada_place, Ada_subject],
Vera = [Vera_place, Vera_subject],
Jenny = [Jenny_place, Jenny_subject],
% we know max place is 4th
all_members([1,2,3,4], [Eilen_place, Ada_place, Vera_place, Jenny_place]),
% we know existing paintings
all_members([constable,taylor,fangogh,monet], [Eilen_subject, Ada_subject, Vera_subject, Jenny_subject]),
% #3 1st was monet
member([1, monet], All),
% #2 Jenny got third
member([3, Jenny_subject], All),
% #1 Eilen painted a constable and was not last
member([Eilen_place, constable], All),
4 > Eilen_place,
% #4 ada beat the taylor painter...
member([Ada_place, Ada_subject], All),
member([H2_taylor_place, taylor], All),
Ada_place < H2_taylor_place, 
% #4 ...and the van gogh painter beat vera member([H4_fangogh_place, fangogh], All), member([Vera_place, Vera_subject], All), Vera_place > H4_fangogh_place.

If we ask for a solution, the single valid solution is presented:

?- solve(Eilen, Ada, Vera, Jenny).
Eilen = [2, constable],
Ada = [1, monet],
Vera = [4, taylor],
Jenny = [3, fangogh] ;

And again, that’s it – problem solved!

Solving Logic Puzzles in Prolog: Puzzle 1 of 3

October 31, 2015 6 comments

Recently I played around with Prolog again to solve 3 small logic puzzles. This post is about solving the first puzzle. This first puzzle consists of 2 individual puzzles that follow the exact same internal structure, so can be solved the exact same way of stating rules in Prolog (just with different content).

The small puzzle: problem and question

There are 4 students: Carrie, Erma, Ora und Tracy. Each has one scholarship and one major subject they study. The goal is to find out which student has which scholarship and studies which subject (with all scholarships and majors being different from each other) from the hints provided. The available scholarships are: 25000, 30000, 35000 and 40000 USD. The available majors are: Astronomy, English, Philosophy, Physics. The following hints are given to solve the problem:

  1. The student who studies Astronomy gets a smaller scholarship than Ora.
  2. Ora is either the one who studies English or the one who studies Philosophy.
  3. Erna has a 10000 USD bigger scholarship than Carrie.
  4. Tracy has a bigger scholarship than the student that studies English.

The small puzzle: the Prolog solution

One way of solving this puzzle in Prolog to ask for a solution (which in our example consists of the 4 students and their associated attributes) that fulfills the rules that we can derive from the 4 hints from above. This is actually pretty short and easy in Prolog syntax:

% ####################################################################
% Logic puzzle solver.
%
% Read definition to prolog:
%   ['puzzle.pl'].
%
% 2) Ask for solutions:
%   solve(Carrie,Erma,Ora,Tracy).
%
% Rainhard Findling
% 10/2015
% ####################################################################

all_members([H],L2) :- member(H,L2).
all_members([H|T],L2) :- member(H,L2), all_members(T, L2).

or([H]) :- H,!.
or([H|_]) :- H,!.
or([_|T]) :- or(T).

solve(Carrie,Erma,Ora,Tracy) :-
% all students
Carrie = [Carrie_scholarship, Carrie_major],
Erma = [Erma_scholarship, Erma_major],
Ora = [Ora_scholarship, Ora_major],
Tracy = [Tracy_scholarship, Tracy_major],
% grouping
All = [Carrie,Erma,Ora,Tracy],
% ensure all values exist once
all_members([25, 30, 35, 40], [Carrie_scholarship, Erma_scholarship, Ora_scholarship, Tracy_scholarship]),
all_members([astronomy, english, philosophy, physics], [Carrie_major, Erma_major, Ora_major, Tracy_major]),
% clue 1
member([C1_scholarship,astronomy], All),
Ora_scholarship > C1_scholarship,
% clue 2
or([Ora_major = english, Ora_major = philosophy]),
% clue 3
member([C3_scholarship, physics], All),
C3_scholarship - Carrie_scholarship =:= 5,
% clue 4
Erma_scholarship - Carrie_scholarship =:= 10,
% clue 5
member([C5_scholarship, english], All),
Tracy_scholarship > C5_scholarship.

If we ask for the solution, the single possible solution is presented:

?- solve(Carrie,Erma,Ora,Tracy).
Carrie = [25, english],
Erma = [35, astronomy],
Ora = [40, philosophy],
Tracy = [30, physics] ;

The slightly bigger puzzle: problem and question

There are 5 car renting contracts. Each has a duration, a pickup location, a car brand and a customer associated to it. The goal is to find out for all contracts, what the customer, duration, car brand and pickup location is (again given the fact that each attribute is unique amongst the contracts). The pickup locations are: Brownfield, Durham, Iowa Falls, Los Altos and Redding. The car brands are: Dodge, Fiat, Hyundai, Jeep and Nissan. The contract duration are 2, 3, 4, 5 and 6 days. And the customer names are Freda, Opal, Penny, Sarah and Vicky. The following hints are given to solve the problem:

  1. The contracts of Vicky, the one with pickup location in Los Altos, the one with pickup location in Durham and the one with the Fiat are all different contracts.
  2. The contract with the Jeep is not in Iowa Falls.
  3. The contract of Vicky and the one with the Nissan are picked up in either Los Altos or Redding.
  4. Penny’s contract is not for 6 days.
  5. The contract in Iowa Falls is for 5 days.
  6. The contract with the Durham is 3 days longer than the contract of Opal.
  7. Of the contract with Nissan and the 2 day contract, one is picked up in Redding and the other is Freda’s contract.
  8. The contract with the Jeep is not for 6 days.
  9. The contract of Opal is 1 day longer than the one with the Hyundai.

The slightly bigger puzzle: the Prolog solution

Again, we can define a solution to fulfill the stated rules:

% ####################################################################
% Logic puzzle solver.
%
% Read definition to prolog:
%   ['puzzle.pl'].
%
% 2) Ask for solutions:
%   solve(Freda, Opal, Penny, Sarah, Vicky).
%
% Rainhard Findling
% 10/2015
% ####################################################################

all_members([H],L2) :- member(H,L2).
all_members([H|T],L2) :- member(H,L2), all_members(T, L2).

all_not([H]) :- not(H).
all_not([H|T]) :- not(H), all_not(T).

all_not_members([H],L2) :- not(member(H,L2)).
all_not_members([H|T],L2) :- not(member(H,L2)), all_not_members(T, L2).

and([H]) :- H.
and([H|T]) :- H, and(T).
or([H]) :- H,!.
or([H|_]) :- H,!.
or([_|T]) :- or(T).

solve(Freda, Opal, Penny, Sarah, Vicky) :-
    % all runners
    Freda = [Freda_car, Freda_location, Freda_days],
    Opal = [Opal_car, Opal_location, Opal_days],
    Penny = [Penny_car, Penny_location, Penny_days],
    Sarah = [Sarah_car, Sarah_location, Sarah_days],
    Vicky = [Vicky_car, Vicky_location, Vicky_days],
    % grouping
    All = [Freda, Opal, Penny, Sarah, Vicky],
    % ensure all values exist once
    all_members([dodge, fiat, hyundai, jeep, nissan], [Freda_car, Opal_car, Penny_car, Sarah_car, Vicky_car]),
    all_members([brownfield, durham, iowafalls, losaltos, redding], [Freda_location, Opal_location, Penny_location, Sarah_location, Vicky_location]),
    all_members([2,3,4,5,6], [Freda_days, Opal_days, Penny_days, Sarah_days, Vicky_days]),
    % clues from easy (fast) to hard (slow)
    % clue 5
    member([_,iowafalls,5], All),
    % clue 9
    member([hyundai,_,C9_days], All),
    Opal_days - C9_days =:= 1,
    % clue 6
    member([_,durham,C6_days], All),
    C6_days - Opal_days =:= 3,
    % clue 4
    not(Penny_days = 6),
    % clue 2
    member([C2_car,iowafalls,_], All),
    not(C2_car = jeep),
    % clue 8
    member([C8_car,_,6], All),
    not(C8_car = jeep),
    % clue 3
    member([nissan,C3_location,_], All),
    or([and([C3_location = losaltos, Vicky_location = redding]), and([C3_location = redding, Vicky_location = losaltos])]),
    % clue 7
    member([nissan, C7_1_location,_], All),
    member([_,C7_2_location, 2], All),
    or([and([Freda_location = C7_1_location, C7_2_location = redding]), and([Freda_location = C7_2_location, C7_1_location = redding])]),
    % clue 1
    member([C1_1_car,losaltos,_], All),
    member([C1_2_car,durham,_], All),
    member([fiat,C1_3_location,_], All),
    all_not_members([C1_1_car, C1_2_car, Vicky_car],[fiat]), %car
    all_not_members([C1_3_location, Vicky_location],[losaltos, durham]). %location

… and ask for it, which again presents the single solution:

?- solve(Freda, Opal, Penny, Sarah, Vicky).
Freda = [nissan, losaltos, 4],
Opal = [jeep, brownfield, 3],
Penny = [fiat, iowafalls, 5],
Sarah = [dodge, durham, 6],
Vicky = [hyundai, redding, 2] ;

Jodici solver: Python vs Prolog

November 8, 2014 1 comment
In the equation puzzle solver and the flower disk rotation puzzle we took a look at differences of solving problems in both Python and Prolog. In this followup post we look at Python vs Prolog again, but deal with a different problem: a Jodici solver.

Jodici

Jodici is a fun and intuitive number placement puzzle from Austria (sadly, there is only a homepage in German language available by 10/2014). Jodici is comparable to Sudoku by filling numbers into a gamefield so that certain rules are satisfied. Jodici differs from Sudoku by a) including calculation by addition and b) spanning a noteworthy smaller solution space (hence it’s easier to solve using brute force).
Jodici exampleA Jodici gamefield consists of a circle which a) contains 3 nested rings and b) is divided into 6 cake-piece-like sectors. Each intersection of sector and ring is a field – therefore each Jodici  gamfield contains 3×6=18 such fields in total. As with Sudoku, the goal is to fill in all numbers, while satisfying certain rules: each field must contain an integer [1,9], with each such integer being used twice in total. Further, each sector sums up to 15 and each ring to 30.

Jodici solver (brute force)

Given the maximum of 18 initially empty fields (which of course defeats the purpose, but can be used as upper limit of effort required to solve Jodici), the solution space is 9^18 (corresponds to 1.5*10^17 solutions and ~57bit entropy). Given a more typical setup of 6 initially filled fields (6 initially known numbers), the solution space is reduced to 9^12 (corresponds to 2.8*10^11 solutions and ~38bit entropy). This solution space could be brute forced even without using heuristics or branch cutting during search (at the cost of arguable runtime). But as for the previous equation puzzle solving problem, branch cutting can be used to notably reduce search space and therefore runtime (we’re not making use of order-of-variables-heuristics as we did for the equation puzzle solver for reasons of simplicity, although this would of course further speed up search).

Python approach

With Python we at first state the Jodici gamefield representation as a 6×3 array. For reasons of easiness empty fields are represented by the number 0 (does not influence the sums we’re going to calculate later). For brute forcing the game, we then implement a depth first search with branch cutting. Branch cutting is caused by doing validity check after each added number, and aborting further search with the current configuration if this configuration turned out to be invalid already. The validity check consists of several rules, which all must be satisfied for the gamefield to (still) be valid:
  1. each number must at maximum be used twice
  2. each ring must sum to < 30 if it’s not fully filled yet, and sum to 30 if it’s already fully filled
  3. each sector must sum to < 15 if it’s not fully filled yet and sum to 15 if it’s already fully filled.

Finally, for ease of use, the gamefield initially gets loaded from a .csv file like the one shown below (which corresponds to the Jodici sample from above):

3,7,_,_,_,_
_,_,1,5,9,_
6,_,_,_,_,_

Loading the gamefield and solving the game:

#!/usr/local/bin/python2.7
# Rainhard Findling
# 11/2014
# 
import copy
import csv

# generate gamefield
field = []
for i in range(6):
  field.append([0, 0, 0])

def load_gamefield(f):
    print('loading gamefield...')
    f = open(f, 'r')
    reader = csv.reader(f)
    rows = [row for row in reader]
    field = []
    for inner in range(6):
        # reorder to "cake pieces" and replace '_' with 0
        field.append([int(rows[outer][inner]) if rows[outer][inner] != '_' else 0 for outer in range(3)])
    return field

# load gamefield
field = load_gamefield('gamefields/1.csv')
print field

print('searching for solution...')

def field_valid(suc):
    """check if field is valid. valid != solved, field must be filled and valid to be solved."""
    valid = True
    # all sectors <= 15 or == 15 if they are already set
    for i in range(6):
        if sum(suc[i]) > 15 or not 0 in suc[i] and sum(suc[i]) != 15:
            return False
    # all circles <= 30 or == 30 if they are already set
    for inner in range(3):
        circ = [suc[x][inner] for x in range(6)]
        if sum(circ) > 30 or not 0 in circ and sum(circ) != 30:
            return False 
    # each nr used twice at max
    for nr in range(1,10):
        if(sum([row.count(nr) for row in suc]) > 2):
            return False
    return True

def field_filled(suc):
    """check if field is fully filled. filled != solved, field must be filled and valid to be solved."""
    if(sum(0 in tmp for tmp in suc) == 0):
        return True
    return False

# list of fields to try
l = [field]
# bruteforce (depth first) all 0 positions
while(len(l) > 0):
  cur_field = l.pop(0)
  # find position to fill in
  found = False
  for s in range(6):
    for f in range(3):
      if cur_field[s][f] == 0:
        found = True
        for nr in reversed(range(1,10)):
          # creade successor
          suc = copy.deepcopy(cur_field)
          suc[s][f] = nr
          # check if successor is valid
          if not field_valid(suc):
              continue
          # if successor is not filled add to list
          if not field_filled(suc):
            l.insert(0, suc)
          elif field_valid(suc):
                # we found solution
                print 'solution:', suc
      if found:
        break
    if found:
      break

print 'done.' 

The python implementation finds the (single possible) solution:

loading gamefield...
[[3, 0, 6], [7, 0, 0], [0, 1, 0], [0, 5, 0], [0, 9, 0], [0, 0, 0]]
searching for solution...
solution: [[3, 6, 6], [7, 1, 7], [5, 1, 9], [8, 5, 2], [4, 9, 2], [3, 8, 4]]
done.

Prolog approach

In contrast to the Python implementation, with the Prolog implementation we even leave out branch cutting during search (we would simply need to state rules in specific orders to cause branch cutting). In our knowledge database we state some rules: one for the valid number range, two for valid rows and sectors, another for counting frequency of an element in a list, and a last one for a valid Jodici gamefield. The last rule defines how many variables we’re searching for (correspond to the fields in a Jodici) and checks for correct sector and ring sums, as well as for each number being used twice exactly.

% Rainhard Findling 
% 11/2014
% Written to run in swipl
% 
% 1. load using ['jodici.pl'].
% 2. try a jodici using gamefield, e.g.
% 
%  R1=[3,7,_,_,_,_],R2=[_,_,1,5,9,_],R3=[6,_,_,_,_,_],gamefield([R1,R2,R3]).
% 
% define which numbers are allowed and what rows and circles have to look like to be valid
nr(X) :- between(1,9,X). % member(X,[1,2,3,4,5,6,7,8,9]).
row(A,B,C) :- nr(A), nr(B), nr(C), sum_list([A,B,C],15).
circle(A,B,C,D,E,F) :- nr(A), nr(B), nr(C), nr(D), nr(E), nr(F), sum_list([A,B,C,D,E,F],30).

% count nr of occurences of X in list
count([],_,0).
count([X|T],X,Y) :- count(T,X,Z), Y is 1+Z.
count([H|T],X,Y) :- H\=X, count(T,X,Y).

% definition of valid gamefield
gamefield([R1,R2,R3]) :-
    % check: correct nr of elements in gamefield
    R1=[X11,X21,X31,X41,X51,X61],
    R2=[X12,X22,X32,X42,X52,X62],
    R3=[X13,X23,X33,X43,X53,X63],
    append(R1,R2,Tmp),
    append(Tmp,R3,All),
    % check: correct rows
    row(X11,X12,X13),
    row(X21,X22,X23),
    row(X31,X32,X33),
    row(X41,X42,X43),
    row(X51,X52,X53),
    row(X61,X62,X63),
    % check: correct circles
    circle(X11,X21,X31,X41,X51,X61),
    circle(X12,X22,X32,X42,X52,X62),
    circle(X13,X23,X33,X43,X53,X63),
    % check: each nr used twice
    count(All, 1, 2),
    count(All, 2, 2),
    count(All, 3, 2),
    count(All, 4, 2),
    count(All, 5, 2),
    count(All, 6, 2),
    count(All, 7, 2),
    count(All, 8, 2),
    count(All, 9, 2).

After loading this knowledge database, we can ask for solutions to a given Jodici (like for the Jodici example from above) and Prolog presents us the same, single possible solution:

?- R1=[3,7,_,_,_,_],R2=[_,_,1,5,9,_],R3=[6,_,_,_,_,_],gamefield([R1,R2,R3]).
R1 = [3, 7, 5, 8, 4, 3],
R2 = [6, 1, 1, 5, 9, 8],
R3 = [6, 7, 9, 2, 2, 4] ;
false.

Conclusion

With Python, we specify the gamefield representation, search algorithm, validity checks and order of operations for speedup (the last one is optional). Similarly, with Prolog we specify the gamefield representation and validity checks – but leave out the search algorithm. Therefore, as for the equation puzzle solver, the main conceptual difference between implementations is that with Prolog, the search algorithm needs not be implemented explicitly, while with Python it must be stated explicitly.

Flower disk rotation puzzle solver: Python vs Prolog

November 2, 2014 2 comments

This post is a followup to the Equation puzzle solver: Python vs Prolog. We again compare Python and Prolog, but look at a different problem: a disk rotation puzzle.

The flower disk rotation puzzle

The flower disk rotation puzzle consists of 4 wooden, stacked disks. The disks are connected at their center via a pole, so that they can be rotated. Each disk contains holes that are arranged around the disk center in the form of a flower. The holes are uniformly spread, so that there is space for 12 holes – but each disk only has 9 of these 12 possible holes (the position of holes differ per disk). The remaining 3 areas are instead made of solid wood. The goal is to rotate the disks so that all holes are covered by at least one of the disks (as we have a total amount of 4*3=12 solid areas for a total of 12 holes, each solid area must cover exactly one hole).

For purpose of purchasing, this puzzle can be found online in appropriate stores, and there exist online descriptions looking at the “hardware” puzzle in more detail (e.g. here).

Solving the flower disk rotation puzzle

There exist 12 possible rotations per disk and 4 disks in total, which leads to a solution space of 12^4 (20.7K solutions and 14.3 bit entropy). But as one disk can be thought of being fixed (because rotation of the other disks is relative to this disk), the relevant solution space is 12^3 (1728 solutions and 10.8 bit entropy). As the solution space is so small, a solver using pure, uninformed brute force search is sufficient (even a breath first search will not cause memory troubles). When adding branch cutting to the search, the solution space gets even smaller: in fact so small, that even a human player can perform an exhaustive search. For our puzzle, branch cutting is done via skipping search building on top of an already invalid solution, e.g. when one hole is covered by more than one solid area.

Of course different “harware” versions of the puzzle exist (holes in the disks are arranged differently). However, the puzzle I purchased was special: when playing around with it I noticed I couldn’t come up with a solution, although the solution space is very small. My puzzle has the following disk setup (each disk is represented by one line, holes are represented by 0, solid areas by 1, and all disks are rotated randomly):

[0,0,0,0,0,1,0,1,0,0,1,0]
[1,0,0,1,0,0,0,0,0,0,0,1]
[0,1,0,0,0,0,0,1,0,1,0,0]
[0,0,0,1,0,0,1,0,0,0,0,1]

Why is that puzzle special? Later we’re going to see: it’s because it has no solution. My guess would be that the first/last disk (depending on the side of the puzzle you’re looking at) was flipped before it got attached to the other disks. When flipping the first/last disk, we later on see that the puzzle has exactly one solution:

[0,0,0,0,0,1,0,1,0,0,1,0]
[1,0,0,1,0,0,0,0,0,0,0,1]
[0,1,0,0,0,0,0,1,0,1,0,0]
[1,0,0,0,0,1,0,0,1,0,0,0]

Python approach

The Python script implements a breadth first search to explore the complete solution space. During search, the implementation counts the nodes in the search tree it visits. The final amount of nodes can be used to evaluate the implementation, as we know there are exactly 12^3 leave nodes (if we keep one of the disks fixed) and 12^0+12^1+12^2 branching nodes on the way (node counting is only implemented in Python and left out in Prolog). When commenting in the line in the script that sorts the “states list” by the state heuristic, the search becomes a best first search – which is implemented in a way that it effectively is a depth first search with branch cutting. If we do branch cutting we of course visit and count less nodes during search.

# Implementation of the flower disk rotation puzzle solver: 4 disks stacked on top of each other, each disk containing 12 fields (3 of them are solid and 9 are holes). The task is to rotate the disks so that all holes are covered by at least one layer of wood. As the disks contain 12 fields, and the sum of all solid fields on all disks is 12 too, each field will be coverd by a single solid field. This scripts solves for possible rotations so that all fields are covered. Solid disk fields are represented by 1, holes by 0.
# Besides searching for solutions this script counts the nodes visited in the search three for evaluation purposes
# 
# Rainhard Findling
# 2014/10
# 
class State():
    &amp;quot;&amp;quot;&amp;quot;represents a state in the state search tree&amp;quot;&amp;quot;&amp;quot;
    def __init__(self, gamefield, rotations=None):
        # sanity checks: gamefield not empty and all rows are of same length
        if(len(gamefield)==0):
            raise ValueError('gamefield empty.')
        l = len(gamefield[0])
        if(l == 0):
            raise ValueError('row length is 0.')
        for row in gamefield:
            if(len(row) != l):
                raise ValueError('rows differ in length.')
        self.gamefield = gamefield
        self.rotations = rotations
        self.heuristics_cache = None
        if(rotations!=None and (len(rotations) != len(gamefield))):
            raise ValueError('rotations and gamefield differ in length.')
        if(rotations==None):
            rotations = []
            for _ in gamefield:
                rotations+=[None]
            # fix first rotation to one to not get redundant solutions
            rotations[0] = 0
            self.__init__(gamefield, rotations)
        
    def shift(self, seq, n):
        n = n % len(seq)
        return seq[n:] + seq[:n]
        
    def __str__(self):
        s = '\n====================================\n'
        for row in self.gamefield:
            s+=str(row)
            s+='\n'
        s+='rotations='
        s+=str(self.rotations)
        s+='\n'
        rows = self.rows_rotated()
        for row in rows:
            s+=str(row)
            s+='\n'
        s+='\n===================================='
        return s
    
    def rows_rotated(self):
        &amp;quot;&amp;quot;&amp;quot;get rows = gamefield in the rotation caused by this state&amp;quot;&amp;quot;&amp;quot;
        rows = []
        for row_index in range(0, len(self.gamefield)):
            row = self.gamefield[row_index]
            rot = self.rotations[row_index]
            if rot == None:
                rot = 0
            rows+=[self.shift(row, rot)]
        return rows
        
    def __repr__(self):
        return self.__str__()
    
    def successors(self):
        &amp;quot;&amp;quot;&amp;quot;derive all successors of this state by shifting the next row to all possible positions. does not shift the first row, as this would be redundant&amp;quot;&amp;quot;&amp;quot;
        # get next row to shift
        row_index = -1
        for r in range(0, len(self.gamefield)):
            if self.rotations[r] == None:
                row_index = r
                break
        if row_index == -1:
            # no more rows to shift, return empty = no successors
            return []
        # generate all successors
        successors = []
        for rot in range(0,len(gamefield[row_index])):
            # generate new rotation set
            rotations = self.rotations[:]
            rotations[row_index] = rot
            suc = State(self.gamefield, rotations) 
            successors+=[suc]
        return successors
    
    def amount_covered(self, col_nr):
        &amp;quot;&amp;quot;&amp;quot;count how often a certain position is covered by the levels [0,N]. only takes into account levels that have been rotated already.&amp;quot;&amp;quot;&amp;quot;
        amount = 0
        rows = self.rows_rotated()
        for row_nr in range(0, len(rows)):
            # only count if this level has already been rotated
            if self.rotations[row_nr] != None:
                row = rows[row_nr]
                if row[col_nr] == 1:
                    amount += 1
        return amount
    
    def amount_opened_total(self):
        &amp;quot;&amp;quot;&amp;quot;amount of fields still openend with current lock position&amp;quot;&amp;quot;&amp;quot;
        amount = 0
        for col_nr in range(0,len(self.gamefield[0])):
            if self.amount_covered(col_nr) == 0:
                # this col does not contain a stopper
                amount += 1
        return amount
    
    def is_leave(self):
        &amp;quot;&amp;quot;&amp;quot;check if the position of all levels is set, so this is a leave state&amp;quot;&amp;quot;&amp;quot;
        for r in self.rotations:
            if r == None:
                return False
        return True
    
    def is_solved(self):
        &amp;quot;&amp;quot;&amp;quot;check if lock is closed so that all positions are covered&amp;quot;&amp;quot;&amp;quot;
        return self.amount_opened_total()==0
    
    def is_valid(self):
        &amp;quot;&amp;quot;&amp;quot;heuristics: check if a solution makes sense. e.g. if a part is covered by two levels the solution is invalid, no matter how much levels have already been aligned.&amp;quot;&amp;quot;&amp;quot;
        for col_nr in range(0, len(self.gamefield[0])):
            if self.amount_covered(col_nr) &amp;gt; 1:
                # at least one position is covered by multiple layers, solution must be invalid
                return False
        return True
    
    def heuristics(self):
        &amp;quot;&amp;quot;&amp;quot; heuristics of how good this solution is [-1,1], with the lowest value being the worst solution and the highest value being the best solution. neutral value = starting value = 0. value is cached after first calculation for performance reasons.&amp;quot;&amp;quot;&amp;quot;
        if self.heuristics_cache == None:
            # calculate and cache
            if not self.is_valid():
                # cannot be good as it is invalid
                return -1
            h = 0
            # the deeper the better
            h += (self.level() / len(self.gamefield))
            # cache and return
            self.heuristics_cache = h
        return self.heuristics_cache
    
    def level(self):
        &amp;quot;&amp;quot;&amp;quot;return the level a state is on. if no level is rotated yet, the level is 0, if 1 level is rotated, the level is 1. if all levels are rotated, the level is the amount of levels in total.&amp;quot;&amp;quot;&amp;quot;
        for row_nr in range(0, len(self.gamefield)):
            if self.rotations[row_nr] == None:
                return row_nr
        return len(self.gamefield)

## original gamefield : no solution
#gamefield = [[0,0,0,0,0,1,0,1,0,0,1,0],
             #[1,0,0,1,0,0,0,0,0,0,0,1],
             #[0,1,0,0,0,0,0,1,0,1,0,0],
             #[0,0,0,1,0,0,1,0,0,0,0,1]] 
# modified gamefield: has one solution
gamefield = [[0,0,0,0,0,1,0,1,0,0,1,0],
             [1,0,0,1,0,0,0,0,0,0,0,1],
             [0,1,0,0,0,0,0,1,0,1,0,0],
             [1,0,0,0,0,1,0,0,1,0,0,0]] 
# measure some stuff
histogram_amount = [0] * (len(gamefield[0]) + 1)
histogram_rotation = []
histogram_tried = [0] * (len(gamefield) + 1) 
for row in gamefield:
    histogram_rotation += [[0]*len(row)]
# do best first search
init_state = State(gamefield)
states = [init_state]
while len(states) &amp;gt; 0:
#     states.sort(key=lambda s:s.heuristics(), reverse=True) # sort states by heuristics. comment out to perform a breadth first instead of a best first search
    # process best solution
    s = states.pop(0)
    histogram_tried[s.level()] += 1
    # do measurements for leave nodes
    if s.is_leave():
        histogram_amount[s.amount_opened_total()] += 1
        rot = s.rotations
        for r_index in range(0, len(rot)):
            r = rot[r_index]
            histogram_rotation[r_index][r] += 1
    # check if this is a leave state - and if, if it solved the problem
    if s.is_leave() and s.is_solved():
        print 'found solution:'
        print s
#         break
    successors = s.successors()
    for suc in successors:
#         if suc.is_valid(): # only produce children of valid solutions. commend out to process full state tree and see statistics for all solutions
        states += [suc]
print 'done, histogram (tried solutions per level):', histogram_tried, ', total=', sum(histogram_tried)
print 'histogram (amount opened): ', histogram_amount
print 'histogram (rotations per row)', histogram_rotation

When we run the Python implementation with our initial disk setup we don’t find a solution:

done, histogram (tried solutions per level): [0, 1, 12, 144, 1728] , total= 1885
histogram (amount opened):  [0, 16, 126, 515, 672, 336, 61, 2, 0, 0, 0, 0, 0]
histogram (rotations per row) [[1728, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [144, 144, 144, 144, 144, 144, 144, 144, 144, 144, 144, 144], [144, 144, 144, 144, 144, 144, 144, 144, 144, 144, 144, 144], [144, 144, 144, 144, 144, 144, 144, 144, 144, 144, 144, 144]]

… but when we use the modified disk setup we find one solution:

found solution:

====================================
[0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0]
[1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1]
[0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0]
[1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0]
rotations=[0, 0, 5, 11]
[0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0]
[1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1]
[0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0]
[0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0]

====================================
done, histogram (tried solutions per level): [0, 1, 12, 144, 1728] , total= 1885
histogram (amount opened):  [1, 9, 146, 485, 697, 325, 63, 2, 0, 0, 0, 0, 0]
histogram (rotations per row) [[1728, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [144, 144, 144, 144, 144, 144, 144, 144, 144, 144, 144, 144], [144, 144, 144, 144, 144, 144, 144, 144, 144, 144, 144, 144], [144, 144, 144, 144, 144, 144, 144, 144, 144, 144, 144, 144]]

Prolog approach

With Prolog, we state what a valid solution – given 4 disks – needs to look like: a) the solution’s first disk will be equal to the initial first disk, all other of the solution’s disks will be rotated versions of the initial disks. b) each hole must be covered by one of the solution’s stacked 4 disks.

% Implementation of the flower disk rotation puzzle solver: 4 disks stacked on top of each other, each disk containing 12 fields (3 of them are solid and 9 are holes). The task is to rotate the disks so that all holes are covered by at least one layer of wood. As the disks contain 12 fields, and the sum of all solid fields on all disks is 12 too, each field will be coverd by a single solid field. This scripts solves for possible rotations so that all fields are covered. Solid disk fields are represented by 1, holes by 0.

% Rainhard Findling
% 10/2014
%
% sample call with no solution:
% solve([0,0,0,0,0,1,0,1,0,0,1,0],[1,0,0,1,0,0,0,0,0,0,0,1],[0,1,0,0,0,0,0,1,0,1,0,0],[0,0,0,1,0,0,1,0,0,0,0,1],R1,R2,R3,R4).
%
% sample call with one solution:
% solve([0,0,0,0,0,1,0,1,0,0,1,0],[1,0,0,1,0,0,0,0,0,0,0,1],[0,1,0,0,0,0,0,1,0,1,0,0],[1,0,0,0,0,1,0,0,1,0,0,0],R1,R2,R3,R4).
% 
solve(L1,L2,L3,L4,R1,R2,R3,R4) :-
  % solution needs to be a rotated version of the original levels (we're not interested in amount of rotation)
  L1=R1,
  rotate(L2,R2,_),
  rotate(L3,R3,_),
  rotate(L4,R4,_),
  % each field needs to be covered by at least one solid field of 1 of the 4 disks (exactly one &amp;quot;1&amp;quot; in our case)
  solid(R1,R2,R3,R4).

% check that each field is coverd by at least one solid part of a disk (exactly one in our case)
solid([],[],[],[]).
solid(H1,H2,H3,H4) :- count([H1,H2,H3,H4],1,1).
solid([H1|D1],[H2|D2],[H3|D3],[H4|D4]) :- solid(H1,H2,H3,H4),
					  solid(D1,D2,D3,D4).

% rotate(+List, +N, -RotatedList)
% True when RotatedList is List rotated N positions to the right
rotate(List, RotatedList, N) :-
    length(List, Length),      % length of list
    append(Front, Back, List), % split L
    length(Back, N),	       % create a list of variables of length N
    Length &amp;gt; N,		       % ensure we don't rotate more than necessary
    append(Back, Front, RotatedList).

% count how often an element occurs in a list
count([],_,0).
count([X|T],X,Y):- count(T,X,Z), Y is 1+Z.
count([X1|T],X,Z):- X1\=X,count(T,X,Z).

As for the Python implementation, the Prolog implementation cannot find a solution to the original disk setup:

?- solve([0,0,0,0,0,1,0,1,0,0,1,0],[1,0,0,1,0,0,0,0,0,0,0,1],[0,1,0,0,0,0,0,1,0,1,0,0],[0,0,0,1,0,0,1,0,0,0,0,1],R1,R2,R3,R4).
false.

… but for the modified disk setup, we find the same single solution as with python:

?- solve([0,0,0,0,0,1,0,1,0,0,1,0],[1,0,0,1,0,0,0,0,0,0,0,1],[0,1,0,0,0,0,0,1,0,1,0,0],[1,0,0,0,0,1,0,0,1,0,0,0],R1,R2,R3,R4).
R1 = [0, 0, 0, 0, 0, 1, 0, 1, 0|...],
R2 = [1, 0, 0, 1, 0, 0, 0, 0, 0|...],
R3 = [0, 0, 1, 0, 1, 0, 0, 0, 1|...],
R4 = [0, 1, 0, 0, 0, 0, 1, 0, 0|...] ;
false.

Conlcusion

As for the last problem, the problem can be solved using both Python and Prolog. And again, Prolog saves us from explicitly implementing the search algorithm, which we need to state explicitly in Python.

Equation puzzle solver: Python vs Prolog

October 25, 2014 2 comments

Recently some of my friends and colleagues asked me: how is the logic-declarative language Prolog (I’ve been playing around with it) comparable – or not comparable – to typical, more well known programming languages? This question made me curious how similar implementations in Prolog typically are to implementations in other, more well known programming languages. Hence, I decided to do some small, comparative AI toy problems (actually search problems) in Python and Prolog. The first is a very simple equation puzzle (this post), the second a flower disk rotation puzzle and the third a Jodici solver.

Python vs Prolog

Python is a well known and widely used programming language (and it’s not only used for scripting). Python supports object oriented as well as aspect oriented programming paradigms – and to some extent functional programming. So Python represents the “typical” programming  language, where  most programmers will be familiar with it’s concepts.

In contrast to Python, Prolog is a logic and declarative programming language, in which developers state facts and rules to derive new facts by logic inference and a recursive backtracking search. These paradigms are less widespread, therefore typically feel less familiar.

The equation puzzle

equation_puzzleOur equation puzzle (sometimes equation crossword puzzle, although many different forms of such puzzles exist) consists of 3 horizontal and 3 vertical equations. Each equation adds/multiplies 3 numbers between -9 and 99 to a single result number. The equations are arranged so that each such number is used in exactly two of these equations. Not all of these numbers are given at the start: only the top left number and the equation results are known. The now obvious task is to find all numbers for the still unset variables (the free fields marked in blue), so that all equations are correct. We’re going to solve that problem programmatically using search (plugging numbers into variables and checking if equations are still correct) and some heuristics/branch cutting for speedup.

Heuristics: plug into equation with least free variables

It’s easier to plug numbers into equations with less free variables (e.g. the top horizontal or leftmost vertical at the start, as they’re the only equations with two instead of three free variables) and checking affected equations for correctness immediately afterwards than to plug numbers into equations which more free variables. Why does this help? Because of branch cutting in our search tree: the sooner we find out that certain numbers won’t allow for a valid equation X correct, the sooner we can stop trying solutions that would have these numbers in equation X. Therefore we look at less solutions during search, which speeds up the search process.

Heuristics: plug into multiplication before addition

Given addition and multiplication as mathematical operations in the equations, it’s easier to first solve equations containing multiplications. Why does this help? Again to cut down the branching factor of the search tree. Equations involving multiplications have less valid solutions than equations only involving additions (given our number range). Again, the sooner we skip certain parts of the search tree, the faster the total search will become.

Given these two heuristics we’re going to use the following order for plugging numbers into variables and checking for validity of corresponding equations (for both the Python and the Prolog implementation):

  1. Plug number into variable: row 1, column 2
  2. Plug number into variable: row 1, column 3
  3. Evaluate equation: row 1
  4. Plug number into variable: row 2, column 3
  5. Plug number into variable: row 3, column 3
  6. Evaluate equation: column 3
  7. Plug number into variable: row 2, column 1
  8. Plug number into variable: row 2, column 2
  9. Evaluate equation: row 2
  10. Plug number into variable: row 3, column 1
  11. Evaluate equation: column 1
  12. Plug number into variable: row 3, column 2
  13. Evaluate equation: row 3
  14. Evaluate equation: column 2

The Python approach

We define a) the order of variables to plug numbers into and equations to evaluate and b) the starting condition (top left number, equations and their results). We then implement a search ourselves: in our case a depth first search. For fully searching the search tree, a breadth first search would do as well in our case – but assuming we only search for one solution if multiple solutions are possible, using a depth first search is the better idea (note that we’re actually using an informed search by hardcoding the order of variables/equations, which could be automated as well – then more informed algorithms like A* would do the job).

#!/usr/bin/python
#
# python demo: solving an arithmetic game with [-9,99] being allowed as unknowns in equations and 6 equations in total.
# Rainhard Findling
# 2014/10
# call using e.g.
#
# python arithmetic_game.py
#
rules = {
	 # order of when to fill variables and evaluate equations
	 'order': [(12,[]), (13,['row1']), (23, []), (33, ['col3']), (21, []), (22, ['row2']), (31, ['col1']), (32, ['col2','row3'])],
	 # known top left variable
	 'state' : {11:26},
	 # equations and their results
	 'row1' : lambda s:s[11] - s[12] * s[13] == -278,
	 'row2' : lambda s:s[21] * s[22] + s[23] == 216,
	 'row3' : lambda s:s[31] * s[32] + s[33] == 11,
	 'col1' : lambda s:s[11] + s[21] - s[31] == 36,
	 'col2' : lambda s:s[12] + s[22] + s[32] == 27,
	 'col3' : lambda s:s[13] * s[23] - s[33] == 245}

def state_str(s):
	"""graphical representation of solution."""
	st =   '----------------\n'
	st += '|%4d|%4d|%4d|' % (s[11],s[12],s[13])
	st += '\n----------------\n'
	st += '|%4d|%4d|%4d|' % (s[21],s[22],s[23])
	st += '\n----------------\n'
	st += '|%4d|%4d|%4d|' % (s[31],s[32],s[33])
	st += '\n----------------'
	return st

# do search
state_init = rules['state']
list_open = [state_init]
while len(list_open) > 0:
	state = list_open.pop(len(list_open) - 1) # depth first search
	#print 'expanding', str(state)
	# generate successors in given number range
	for nr in range(-9,99)[::-1]: # start with bigger numbers - will more likely cut branches with multiplications
		s = state.copy()
		for tup in rules['order']:
			if not tup[0] in s:
				# slot is still free, set nr there
				s[tup[0]] = nr
				valid = True
				for rule in tup[1]:
					if not rules[rule](s):
						valid = False
						break
				if not valid:
					break
				if len(s) == 9:
					# solved!
					print 'solution:\n', state_str(s)
				else:
					list_open += [s]
				break
print 'done.'

The Python script finds the (single possible) solution:

solution:
----------------
|  26|  19|  16|
----------------
|  25|   8|  16|
----------------
|  15|   0|  11|
----------------
done.

The Prolog approach

In contrast to the Python approach, Prolog uses a built-in recursive backtracking search internally, therefore saves us from implementing the search algorithm ourselves. This of course makes the script notably shorter. Anyway, the equations with their results and the variable known at the start has to be defined. As for the Python script, in Prolog the order of rules plays a major role (it’s how we do branch cutting in our case). Hence, we use the same ordering as for the Python script.

% prolog demo: solving an arithmetic game with [-9,99] being allowed as unknowns in equations and 6 equations in total.
% Rainhard Findling
% 2014/10
% call using e.g.
%
% ['my_database.pl'].
% gamefield(26,X12,X13,X21,X22,X23,X31,X32,X33,-278,216,11,36,27,245).
%
nr(X) :- between(-9,99,X).
gamefield(X11,X12,X13,X21,X22,X23,X31,X32,X33,R1,R2,R3,C1,C2,C3) :-
	nr(X12),
	nr(X13),
	R1 is X11 - X12 * X13,
	nr(X23),
	nr(X33),
	C3 is X13 * X23 - X33,
	nr(X21),
	nr(X22),
	R2 is X21 * X22 + X23,
	nr(X31),
	C1 is X11 + X21 - X31,
	nr(X32),
	R3 is X31 * X32 + X33,
	C2 is X12 + X22 + X32.

As for the Python script, the Prolog script also finds the single possible solution. The variable numbers refer to the grid indexes, e.g. X12 refers to the free variable in row 1, column 2.

?- gamefield(26,X12,X13,X21,X22,X23,X31,X32,X33,-278,216,11,36,27,245).
X12 = 19,
X13 = X23, X23 = 16,
X21 = 25,
X22 = 8,
X31 = 15,
X32 = 0,
X33 = 11 ;
false.

Conclusion

Besides using different programming paradigms, the main conceptual difference between implementations is that with the Python implementation the search is explicitly stated in code, while with the Prolog implementation search is a built-in feature. Search order (which action to do next) matters for both implementations. With both Python and Prolog, the order is stated explicitly (with Python as a list of actions, with Prolog as order or rules to evaluate) – which cause the same behaviour in the end.