Home > Artificial Intelligence > Jodici solver: Python vs Prolog

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

  1. January 7, 2015 at 11:18

    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)

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: