# Jodici solver: Python vs Prolog

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).
A 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,_,_,_,_,_
```

```#!/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])

f = open(f, 'r')
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

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

## One thought on “Jodici solver: Python vs Prolog”

1. An exciting article about solving Jodici – congratulations!
Jodici is available on the iOS app store now (also in English).
Have fun with solving Jodici!

With best wishes
Herbert Jodlbauer (inventor of Jodici)