Perhaps the major difference between the Functional and Imperative paradigms in the minds of most programmers is that functional programming is hard and imperative programming less hard. With functional programming we are constrained by having to replace iteration, for and while in Python, with either recursion or the use of higher order functions like map, reduce, filter etc. which basically handle the recursion for us.
Another constraint enforced in most functional languages is that variables may be assigned only once at a given level of recursion. However, once iteration is gone, this becomes a non-issue.
We are going to write a small program in two ways, iterative and functional, with the same set of functions. Both will produce the same result. In fact, the iterative and functional versions of the functions themselves may be interchanged. The idea is to see the transition from one paradigm to the other as pretty natural and intuitive.
The Eight Queens puzzle is a nice example of essentially using a tree search for solutions to a constraint problem.
Here is an example of a solution to the puzzle.
. . Q . . . . .
. . . . . Q . .
. . . Q . . . .
. Q . . . . . .
. . . . . . . Q
. . . . Q . . .
. . . . . . Q .
Q . . . . . . .The dots represent empty squares on a standard 8 by 8 chessboard. The Q's are where the 8 queens are placed. Every row, column and diagonal has exactly one queen. Another way of putting it is that none of the eight queens is in danger of imminent capture by another queen.
In this project we'll represent solutions to the puzzle using an eight character string. In the above solution the representative string is '36428571'. It means that, starting from the top, the first row contains its queen in column 3, the second row in column 6 and so on. For a full solution the representative string has a length of 8 and, of course, contains each of the digits 1-8 exactly once.
It turns out that there are exactly 92 solutions that our programs will generate. And on my laptop running Ubuntu all the solutions are found in under 5 milliseconds. The 92 solutions contain many that are essentially duplicates. A solution may be flipped vertially or horizontally; or around either diagonal; or rotated 90, 180, or 270 degrees.
Original Solution Flipped Vertically Then Horizontally
. . Q . . . . . Q . . . . . . . . . . . . . . Q
. . . . . Q . . . . . . . . Q . . Q . . . . . .
. . . Q . . . . . . . . Q . . . . . . Q . . . .
. Q . . . . . . . . . . . . . Q Q . . . . . . .
. . . . . . . Q . Q . . . . . . . . . . . . Q .
. . . . Q . . . . . . Q . . . . . . . . Q . . .
. . . . . . Q . . . . . . Q . . . . Q . . . . .
Q . . . . . . . . . Q . . . . . . . . . . Q . .The two flips above are equivalent to rotating the board 180 degrees.
Our code will generate solutions row by row from top to bottom. Partial (incomplete) solutions then may generate additional solutions containing one additional row. Here is an example of a 4 row partial solution that can generate 2 further 5 row partials.
Board '6471' ==> '64713' or '64718'
. . . . . Q . . . . . . . Q . . . . . . . Q . .
. . . Q . . . . . . . Q . . . . . . . Q . . . .
. . . . . . Q . . . . . . . Q . . . . . . . Q .
Q . . . . . . . Q . . . . . . . Q . . . . . . .
. . . . . . . . . . Q . . . . . . . . . . . . Q
. . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . .Even the empty string is a partial solution and generates 8 further solutions with a queen in each column of row one: ['1','2','3','4','5','6','7','8'].
The meat of the program consists of taking a partial solution, say one with the top 4 rows filled in, to generate one or more with a 5th row. If there are none the partial solution is abandoned. We proceed with other partial solutions until the ones with all eight rows are produced.
Here are links to the code for both the imperative and functional versions.
First let's look at the function that nicely formats a partial solution string into a chess board that's much easier on our (human) eyes. Here is the code for both modes.
# imperative
16 def printBoard(partial) :
17 for digit in partial :
18 col = int(digit)
19 lin = ". "*(col-1) + "Q " + ". "*(SIZE-col)
20 print(lin)In the imperative code on the left it's fairly easy to see what's going on. For each row of the board that contains a queen, the for loop sets col to each digit in the partial board and a line is constructed with the Q in the appropriate column and with '.'s in the others.
# functional
15 def printBoard(partial) :
16 if partial :
17 col = int(partial[0])
18 lin = ". "*(col-1) + "Q " + ". "*(SIZE-col)
19 print(lin)
20 printBoard(partial[1:])
21The functional version does exactly the same thing, although a bit differently. The first digit from the (partial) solution determines the column. The line is created as before and then printBoard is called recursively with the remaining digits. When there are no more, the if in line 2 fails and the recursion stops. Here's a sample run of each (though not solutions).
>>> import queens_func
>>> queens_func.printBoard('12345678')
Q . . . . . . .
. Q . . . . . .
. . Q . . . . .
. . . Q . . . .
. . . . Q . . .
. . . . . Q . .
. . . . . . Q .
. . . . . . . Q
>>> import queens_imper
>>> queens_imper.printBoard('87654321')
. . . . . . . Q
. . . . . . Q .
. . . . . Q . .
. . . . Q . . .
. . . Q . . . .
. . Q . . . . .
. Q . . . . . .
Q . . . . . . .
>>>The central piece of the program decides if a queen may be placed on a given square (row and column) in harmony with all the other queens that have been placed before. In the diagram below, we work from the top down and then left to right. The '?' is where we are considering the placement of a queen that would extend our partial solution from 4 rows to 5. Every square with an x must be checked to see if it is empty or has been assigned to an earlier queen. A new queen may replace the ? only if all x squares are empty.
Q . x . . . x .
. . x Q . x . .
x Q x . x . . .
. x x x Q . . .
. . ? . . . . .This is done in a single function checkPlacement which takes two parameters, a partial solution (here '1425') and a column number (here 3). It returns True if placement is possible. Here is the imperative version.
# imperative
1 def checkPlacement (partial, col) :
2 row = len(partial) # row we're adding
3 if partial :
4 spread = 1
5 for prow in range(row-1,-1,-1) : # previous rows
6 if int(partial[prow]) in (col,col-spread,col+spread):
7 return False
8 spread += 1
9 return TrueThe for loop works from the lowest good (line 5) row up to the top, checking if there is a queen in any of the three x columns (line 6). partial[prow] contains the column where the queen in row prow is found. col is the column of our ?. And col, col-spread, col+spread are where the three x's are. If any are occupied we're out of luck for placing a queen at '?' Notice that spread grows as we go up, tracking the diagonals. Of course, in the above example, col-spread will be off the board in rows 1 and 2 but that's not a problem since we're not indexing on these values. They are always out the range (1-8). Line 6 is a bit tricky though. You may want to spend a bit of time with it.
For comparision, here is the functional version.
# functional
1 def checkPlacement (partial, col, spread=1) :
2 if not partial : return True
3 else :
4 if int(partial[-1]) in (col,col-spread,col+spread):
5 return False
6 else :
7 return checkPlacement(partial[:-1], col, spread+1)It's actually a bit shorter. The use of recursion is similar to the printBoard function. Notice how we are able to use the Python parameter default feature to handle both the initial and subsequent settings for spread (line 1 and 7).
Here, we'll play around with this. We have our four row partial solution and want to test queen placement for row 5 in columns 6 and 3.
>>> import queens_imper
>>> import queens_func
>>>
>>> queens_imper.printBoard('1425')
Q . . . . . . .
. . . Q . . . .
. Q . . . . . .
. . . . Q . . .
>>> queens_imper.checkPlacement('1425',3)
True
>>> queens_imper.checkPlacement('1425',6)
False
>>> queens_func.checkPlacement('1425',3)
True
>>> queens_func.checkPlacement('1425',6)
False
>>>It's now a fairly short step to generating solutions. In the imperative version below,the program keeps a queue partials that holds all of the partial solutions found. Once a partial solution becomes a full solution, it is printed and discarded (line 28). Otherwise, the columns in the empty row are each checked (line 31) and if OK a new partial solution is created and added to the queue (line 32). Here is the complete function.
22 def findSolutions() :
23 partials = [""] # empty board
24 while partials :
25 partial = partials.pop(0)
26 if len(partial) >= SIZE :
27 solution = partial
28 print(partial) # a solution
29 else :
30 for col in range(1,SIZE+1) :
31 if checkPlacement (partial, col) :
32 partials.append(partial+str(col))
33Here is a sample run
$ python queens_imper.py
15863724
16837425
17468253
17582463
24683175
25713864
(many more)
74286135
75316824
82417536
82531746
83162574
84136275
Done. Took 3.6 millisecondsThe program took 3.6 milliseconds to find the 92 solutions. There is a nice order in the display and if you look closely you can find solutions are mirror images of each other. Incidentally 2057 partial solutions were queued for later processing. All but 92 met dead ends.
We could take the above code for findSolutions and turn it into two recursive functions that would replace the while loop starting at line 3 and the for loop at line 9. But I would like to do something quite a bit more interesting.
Python has some built-in functions for list processing. Let's look at the four functions we'll use. The first 3 take a function and a list.
The function map applies the function (with one parameter) to each element of the list and returns a new list with the results. The original list is unchanged. The function may be either defined with def or a lamba expression. Here's two examples.
>>> map(lambda x: x+5, [1,2,3,4,5])
[6, 7, 8, 9, 10]
>>> map(lambda x: [x+5], [1,2,3,4,5])
[[6], [7], [8], [9], [10]]
>>>The function reduce takes a function with two parameters and applies between the list elements to create a single value. We'll use def to define the function instead of lambda
>>> def plus(x,y) : return x+y
>>> reduce (plus, [1,2,3,4,5])
15
>>> # when lists are "added" they are concatenated
>>> reduce (plus, [[2],[3],[4]])
[2, 3, 4]One thing to note. In Python 2 reduce is a built-in function but in Python 3 we must import reduce from functools like this
from functools import reduceThe function filter takes a function of one argument and applys it to each element dropping those that evaluate to false (False, None, [], ""). The following filters out the odd numbers in the list:
>>> # remove non-even numbers
>>> filter (lambda x: x%2==0, [1,2,3,4,5,6])
[2, 4, 6]Finally, the function zip works like a zipper. It takes two list and returns a list of tuples, marrying the elements together. An example is sufficient
>>> zip([1,2,3,4],['one','two','three','four'])
[(1, 'one'), (2, 'two'), (3, 'three'), (4, 'four')]The function findSolutions in queens_func.py will use a helper function expandSolution. Let's walk through what will be happening there. The string '1425' represents a partial solution that we'll want to expand
>>> pairs = zip(['1425']*8, range(1,9))
>>> pairs
[('1425', 1), ('1425', 2), ('1425', 3), ('1425', 4),
('1425', 5), ('1425', 6), ('1425', 7), ('1425', 8)]
>>> ok = filter(lambda p: queens_func.checkPlacement(p[0],p[1]), pairs)
>>> ok
[('1425', 3), ('1425', 8)]
>>> map (lambda p: "%s%d"%p, ok)
['14253', '14258']
>>> queens_func.expandSolution('1425') # wraps the above together
['14253', '14258']Here is the code for expandSolution.
29 def expandSolution(partial) :
30 if len(partial) >= SIZE :
31 print(partial) # a solution
32 return []
33 else :
34 pairs = list(zip([partial]*SIZE, range(1,SIZE+1)))
35 pairs = list(filter(lambda p: checkPlacement(p[0],p[1]), pairs))
36 pairs = list(map (lambda p: "%s%d"%p, pairs))
37 return pairs
38The function basically replaces the if/else in lines 10-12 in the iterative version. The earlier for loop is replaced by the higher-order calls from zip/filter/map. The interactive dialog just above shows how a partial solution '1425' is transformed into its successor list ['14253','14258']. The lambda expression in line 36 creates a string '12345' from ('1234',5) using the basic string formatting operator.
Our functional findSolutions code is fairly simple and basically replaces the while loop in the iterative version:
1 def findSolutions(partials=[""]) :
2 if partials :
3 partials = map(expandSolution, partials)
4 partials = reduce(lambda x,y: x+y, partials)
5 findSolutions(partials)
6 returninitially, partials is the list [""] map (line 3) will change it to
[ ["1"], ["2"], ["3"], ["4"], ["5"], ["6"], ["7"], ["8"] ]and the reduce (line 4) will "add" (merge) this lists together to make
["1", "2", "3", "4", "5", "6", "7", "8"]giving us a good start on generating (partial) solutions (from our perspective) in parallel.
Running the program gives us the same output as the imperative version
$ python queens_func.py
15863724
16837425
17468253
17582463
24683175
25713864
25741863
(many more)
74286135
75316824
82417536
82531746
83162574
84136275
Done. Took 4.5 millisecondsNoq the program takes about 4.5 milliseconds to run. I have not looked into this carefully but I suspect this is the overhead of concatenating the inner lists to restore the flat structure expected in partials. Each "+" operation creates a new list and once the program is underway, these become fairly long. In the iterative version the list append method is much more efficient.
I got interested in the eight queens puzzle several years ago from Bruce Tate's book "Seven languages in Seven Weeks". Prolog was one of the seven and Bruce used the eight queens puzzle as an example of its strengths. It's interesting. Basically just the rules of the puzzle are described in Prolog and it works out the "program".
If we look at the possible ways we can place eight queens on the board with the only constraint being that only one queen may occupy a given square we get
>>> 64*63*62*61*60*59*58*57*56
9993927307714560Another way to express this is "64!/55!" where "!" indicates factorial (and has precedence over the division). 9,993,927,307,714,560 is a big number and the computation would basically run forever. Bruce tweaked the program to jumpstart the search by adding a one queen per row condition. But it still took about 3 minutes to find all 92 solutions. Well over 1000 times as long as the two programs above. Why?
In our programs we do a breadth first tree search, but by generating partial solutions that can be eliminated along with all their descendents, we dramatically prune the tree as we go. This is similar to the knapsack problem discussed in the Dynamic Programming project.
There is one more program in the project. You can test the really short and really speedy version which runs about 10 times faster the either of the other two.
I like the 8 queens program and when I've poked around with other languages I like to port it over just to practice the language. So far I've done ports to C, Erlang, elixir, go and lua.
You can download the zip file for Queens here.
If you have comments or suggestions You can email me at mail me
Copyright © 2016-2021 Chris Meyers and Fred Obermann
* * *