Home > Artificial Intelligence > Equation puzzle solver: Python vs Prolog

Equation puzzle solver: Python vs Prolog

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.

  1. No comments yet.
  1. November 2, 2014 at 10:11
  2. November 8, 2014 at 10:38

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: