Pictorial Representation of the Eight Queens Problem Solution Set of all 92 answers

Never Get Out of the Boat

Being a brief look at
Logical Programming in Python

As motivated by
The Family Tree
&
Eight Queens Problem


Never Get Out of the Boat

Being right up there with:
I love the smell of napalm in the morning, and
If I say this code is safe to ship, this is code is safe to ship.


So, Never get out of the boat: first, it's from Apocalypse Now (a great movie); and second, it's become a major cornerstone of my programming philosophy: to wit, Never Get Out of the Boat: i.e. I should never leave the Python programming environment as Python can do everything (I want to do) faster and easier than the alternatives, so there is no need for me, myself, and I to ever jump ship. Choose a horse, run with it, I'll meet you at the finish line. I think I'll get there faster using Python; but then, individual results may vary.

Logical Programming

You don't say much, do you?
Usually followed a few hours later by:
Don't you ever shut up?


I've got an active mind. I hear about things: imperative programming, procedural programming, functional programming, logical programming... wait, what was that last one?

So, I looked into it.
Logical Programming is ProLog... or so I will say.
But I didn't want to get out of the boat, learn a new language, so I looked at the available Python Libraries: pyDataLog, Pyke, and probably a few others. But these still required getting out of the boat, but in a much worse way, they required 'Blob Text'.

Wondering what 'Blob Text' is?
This is Blob Text:

answer = solution.provider("CONTROL text GOES <here> mode=UNSAFE")

"CONTROL text GOES <here> mode=UNSAFE" will have to be debugged by hand, your IDE (or at least, my IDE) will be of no use. I tried a simple 'Hello World' Factorial Function using pyDataLog and it took me five minutes to debug a single uncapitalised letter.

So, pyDataLog, Pyke, and probably a few others (constraints, another library I just became aware of) may well work for you, but they are not of the solution set for me.

So, anyway, at this point in my tale of woe, I had come to the opinion that Logical Programming might just be an awful lot like parsing a tree structure. Um, so, maybe an example. This is what a lot of the example data looked like as I perused the subject of Logical Programming: three tuples from which relationship trees could be parsed.

data_blob1 = "(son1 mother1 father1)
              (son2 mother1 father2)
               ...
              (dauther57 mother21 father43)"

Or, as often as not, the same problem would be formatted as:

data_blob2 = "(name1 son name2)
              (name2 daughter name3)
              ...
              (name78 son name3)"

data_blob1 being an example of (node: leaf, leaf).
data_blob2 being an example of (node <named relation> node),
   which is the same thing as (node <edge> node).
   (Given that I'm fairly new to Graph Theory, so my analysis is probably off in some wonderful little -- or major -- way.)


Anyway, if it looks like a tree structure and acts like a tree structure, it probably is a tree structure.

ete2 is a great Python Library for trees.
networkx is a pretty darn awesome Python Tree Library.
HTML & XML are trees, so there are countless tree parsers libraries out there for these two.

And I am sure that I shall use at least one of these quite extensively in the years to come.

And then, since it's probably mathematically (programmically?) impossible to eliminate the problems inherent in Blob Text from Data Input, the only real problem that remained was that no one else seemed to be using these libraries with Logical Programming in mind, so if not reinventing the wheel, I was certainly in the position of having to cobble my own wheel together from bits and pieces.

Somewhere about here (see, I told you I could get wordy, so just skip ahead if this is boring to you, real code lies below), I came across Recursive CTE's in SQL, which solve the tree parsing problem in a known way by a platform that many folks use.

So, SQL.
Only SQL is actually leaving the boat.
I mean, I didn't know that at first, it's a toolkit that I'll need for webdesign, data management, so OK, rationalization complete, I loaded mySQL, brought up the workbench, leafed through a dozen tutorials, online books...

And then:

Oh, wait!
What the unholy crap am I doing?
Learn mySQL? Why? The standard libary has a sqlite module, so I'll just use that.
And, let's see, to set up the recursive functions...
No, stop!
Again with the learning stuff?
What are you doing?
Using sqlite for recursive functions?
Why? Why? Why?
Python does that out of the box.


So, I don't have to learn SQL, load a separate library, or even learn Logical Programming...

Well, that last, I don't really know what Logical Programming is. I mean, I know that figuring familial relations on the fly is a textbook example of what Logical Programming can do, as is the Eight Queens Problem. So, maybe I'm just looking at this wrong and I should just call Logical Programming that which solves either of these two use case patterns... and Python does that, out of the box: no need to learn Prolog, SQL, or even load a second hand library.

Python just does it.

SQL Sucks

Overkill by any other name...


Short rant here, more of a have to write it to get it out of my system aside, than anything else.

So, here it goes:

My grandmother, were she alive today, God Rest Her Soul, would understand Comma Separated Data Files. She would not understand SQL. There are books on SQL (rated beginner, intermediate, and advanced). Special tools are required just to visualize the data. An engine must be started just get the thing to idle (if you know what I mean). And to top it off, the entire thing is based on esoteric mathematical models that few programmers (much less lay people) know or even care about (or that were even around in the 1950s).

So, to say SQL is complicated is an understatement.
And to say SQL is overkill for most applications is an understatement.

Still, everyone seems to use it, the web is built around it, and I figured one of the reasons (at least, as of last week) was it's elegant handling of recursion (which, still, may well be true). But using SQL isn't needed for recursion (ensuring a lock on data for parallel process, well, that's another story, and not a case use I've ever had to implement on my own, and certainly not what I was trying to do).

So, there you have it.
SQL: complicated, way too complicated for my use case.


Parsing a Family Tree in Python

Or should that be, Parsing the Paufler Family Tree?
Eh, best not to use real names and values...



Given data of the form:

family_tree = [('Brett Paufler', 'Boy', 'Mommy', 'Daddy'),
               ('Mommy', 'Girl', 'Mat Grandma', 'Mat Grandpa'),
               ('Daddy', 'Boy', 'Pat Grandma', 'Pat Grandpa')
               ]

The following code works as one might expect.

def are_brothers((a,b,c,d),(w,x,y,z)):
    '''returns True if two boys have the same parents
    '''
    return all([b=='Boy',x=='Boy',c==y,d==z])


def are_sisters((a,b,c,d),(w,x,y,z)):
    '''returns True if two girls have the same parents
    '''
    return all([b=='Girl',x=='Girl',c==y,d==z])


def are_siblings((a,b,c,d),(w,x,y,z)):
    '''returns True if two whatever share the same parents
    '''
    return all([c==y,d==z])


def list_all_brothers(family_tree):
    '''returns a list of all brothers in given family_tree
    '''
    return [(a,w) for (a,b,c,d) in family_tree
                      for (w,x,y,z) in family_tree
                      if are_brothers((a,b,c,d),(w,x,y,z))
                      and a < w] #this '<' here is a thing of beauty


def list_all_ancestors((a,b,c,d),family_tree):
    '''returns a list of ancestors
    for subject person
    '''
    ancestors = set([])
    parents = [c,d]

    while parents:
        p =  parents.pop()
        p = [(a,b,c,d) for (a,b,c,d) in family_tree if a==p]
        if p:
            a,b,c,d = p[0]
            ancestors.add((a,b,c,d))
            parents += [c,d]
    return ancestors


def are_related(a,b,family_tree):
    '''returns true if a and b share a common ancestor
    from list_all_ancestors
    '''
    aF = set(list_all_ancestors(a,family_tree))
    aF.add(a)
    bF = set(list_all_ancestors(b,family_tree))
    bF.add(b)
    if aF.intersection(bF):
        return True
    else:
        return False


Please note: there are no import dependencies, this is raw Python at it's most fundamental level, and it's as 'Logical' as I understand 'Logical Programming' to be.

Of course, that said, I'm sure I'll learn something new in a week or two that will make me grimace at that statement. But then, this entire website has become a sort of shrine to things that make me grimace, so no sense changing my tune now.

Of course, to be fair, this site is also filled with things that make me beam with pride & joy and it's not really possible for me to know which this page will turn out to be a few weeks, months, or years down the line, so I've sort of decided to post it all.

Anyway, back on point, Logical Programming, at it's most basic, which is to say the level that encompasses my current understanding, can be obtained by rather basic implementation of list comprehensions. No need to look elsewhere for that.

But what about more complicated problems?


The Eight Queens Problem in Python

But I thought there was only one queen in chess?
Dear, more importantly, there is only one queen in my life...



Simply stated, The Eight Queens Problem concerns finding the arrangement of 8 Queens on a chessboard, such that none are attacking any of the others (do not share a rank, file -- column, row -- or any diagonal).

So, that's the problem.
Want to know what's funny about that?
I thought it would be hard, so hard to implement in Python that I spent a week (maybe two) looking for simpler solutions.
Um, gee, I can be a bit of an idiot at times.

As follows is the Solution to the Eight Queens Problem in Python.

from itertools import permutations

#range(1,9) spits out [1,2,3,4,5,6,7,8]
#permutations spits out every permutation of same
#zipping together gives every possible chessboard combination
#  with no two pieces in same rank or file
boards = [zip(range(1,9),p) for p in permutations(range(1,9))]

print len(boards)
#40320
print boards[0]
#print first possible solution set
#Note, rank and file different for each tuple
#[(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6), (7, 7), (8, 8)]


def no_diagonals(board):
    '''given a list of tuples representing a possible solution
    returns False if any are diagonally aligned, True otherwise
    '''
    for x,y in board:
        for r in (range(-7,0,1) + range(1,8,1)):
            if (x+r,y+r) in board:
                return False
            elif (x-r,y+r) in board:
                return False
    return True

#And this is the solution
#Take the first list with no overlapping rank and files
#And filter with no_diagonals()         
boards = [b for b in boards if no_diagonals(b)]


print len(boards)
#92, which is the correct number of answers
print boards[0]
#A sample solution set
#[(1, 1), (2, 5), (3, 8), (4, 6), (5, 3), (6, 7), (7, 2), (8, 4)]

There's a lot of crap text in the above, so on the assumption you're smart, here's the quick, psuedo-code version.

boards = [zip(range(1,9),p) for p in permutations(range(1,9))]
boards = [b for b in boards if no_diagonals(b)]

Easy-peasy.
So, I spent two weeks looking for a simpler solution to that?
Excuse me, I must now stand in the corner and hang my head in shame.


Picture Perfect

A picture being worth a thousand words.
Or, er, that is to say, presentation is everything.



On the plus side, once I realized I could solve this in Python, I spent an evening (lying awake, crying tears of sorrow into my pillow) working out the structure of the code, and an hour the next morning pounding it out.

Yeah, I should have felt good about that, but I didn't.
I needed to redeem myself.
Hence, the pretty pictures that abound on this page; for which, here be the code.

def board_image(board):
    '''standard board graphic
    '''
    #holding array, 1 being white in grayscale
    #np being the result of import numpy as np
    bI = np.ones((100,100), dtype=float)
    
    #these are the board grid lines
    for x in range(10,100,10):
        bI[x,10:90] = 0.0
        bI[10:90,x] = 0.0
        
    #these are the squares, which represent the queens
    for (x,y)in board:
        bI[x*10:x*10+10,y*10:y*10+10] = 0.0

    print bI #debug
    skimage.io.imsave("eight_queens.png", bI) #save png
    return bI #return array for next funtion

	
def all_boards_image(boards):
    '''standard boards, full array
    '''
    #make array with full 92 solution set
    #precomposed into image arrays
    images = []
    for b in boards:
        images.append(board_image(b))

    #arrange the img solution sets
    #into a 23x4 grid 
    img = np.vstack((np.hstack(images[0:23]),
                     np.hstack(images[23:46]),
                     np.hstack(images[46:69]),
                     np.hstack(images[69:92])))
    
    #save the solution set as an image
    skimage.io.imsave("eight_queens.png",img)

I hate to say it, but those pretty pictures are why folks are willing to spend the big bucks on experienced programmers.

Visualizing the solution took me +/- 2 weeks (clearly Logical Programming is not -- currently -- my strong suit).
Pounding out the code, +/- 1 hr (it really is trivial once it clicks).
While doing the rote imaging work to make it look cool, just a few hours more (while having fun and just plain goofing around; seriously, I can do this imaging stuff in my sleep).

Of course, the secondary images originate from the need to debug my mistakes.
But the trick is making it look cool; and if only for myself, I think I have done just that.


This is where I usually put a link to my homepage or some related post.
The link this time is to the project for which I am most proud (not just on my entire site, but in my entire life).
Minataur Tails


Brett@Paufler.net
© Copyright 2015 Brett Paufler
Terms of Service