## Jodici solver: Python vs Prolog

## Jodici

## Jodici solver (brute force)

## Python approach

- each number must at maximum be used twice
- each ring must sum to < 30 if it’s not fully filled yet, and sum to 30 if it’s already fully filled
- 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.

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)