Dither and Bicker

Recently I've been catching up on all the games I missed back in the late eighties and nineties. Thanks to Steam, the Mac Games Store (Mac Game Store), Good Old Games (gog.com), iTunes, and of course the random altruistic blog poster. My current game du jour is The 7th Guest.

I won't lie, I've never been very good at pure puzzlers, but the main difference between myself today and fifteen odd years ago is that I'm more comfortable with letting computers solve these damn things for me. I've also been looking for excuses to practice python, so its two bird with one stone...

The puzzle in question is the queens problem: arrange eight queens on a chessboard such that none would "attack" each other in chess rules. That's to say that one queen cannot be on the same vertical, horizontal, or diagonal path as another.

First off what are the rules:

• There can be only one queen per row, per column. Because of this I only need a one dimensional array to store the values. My array will track the column of a queen, each index will correspond to a different row. A chessboard is 8x8, so the array will have eight indexes, each with a value between 0 and 7
• A vertical mismatch can then be determined if any of the "column" values occur more than once in the array.
• A diagonal mismatch is a little trickier. For my purposes, two points (x_i, y_i and x_j, y_j) are diagonal to each other if |x_i - x_j| == |y_i -y_j|

Those rules being determined, there's a matter of how to feed in the various board configurations to test. I could nest eight loops and run through each, but that'd take forever. What I really want to do is perform the computation in a single loop.

Since I'm using a one dimensional array to track this, a sample line would look like:

[0,1,2,3,4,5,6,7] or [0,2,1,3,5,4,6,7], etc...

Every index of the array will hold a value from zero to seven. The starting array would look like [0,0,0,0,0,0,0,0] and the ending array would look like [7,7,7,7,7,7,7,7].

Looking at these numbers again, the question became very simple. Finding the maximum number of loops is tricky in decimal (base ten) logic, but all these indexes could only go up to eight. Fortunately Python supports base eight (aka octal) arithmetic right out of the box. If counted in octal, converted the counter to a string and then sliced the resulting characters into an array, I could find all possible combinations in one loop and then process accordingly.

def printBoard( board ):
    for row in range(0, 8):
        rowstring = ''

        for col in range(0, 8):
            if(board[row] == col):
                rowstring += 'q'
            else :
                rowstring += '_'
            rowstring += ' '

        print rowstring

    print '\n\n'
    return


success_count = 0

for i in range (0, 0100000000):
    octa = int( oct(i) )
    mask = '%(#)09d' % { "#" : octa }

    board = [ int(mask[1]), int(mask[2]), int(mask[3]), int(mask[4]), int(mask[5]), int(mask[6]), int(mask[7]), int(mask[8]) ];

    works = 1

    for rowindex in range(0, 8):
        for testindex in range(0, 8):
            if(testindex != rowindex):
                #check for horizontal
                if( board[testindex] == board[rowindex] ):                    
                    works = 0
                    break

                # check for diagonal
                if( abs(testindex - rowindex) == abs(board[testindex] - board[rowindex]) ):
                    works = 0
                    break

        if(works == 0):
            break

    if(works == 1) :
        success_count = success_count + 1
        print "Board ", success_count
        printBoard( board )

As it turns out, there's ninety two solutions to this puzzle, meaning I probably would've guessed the answer faster than coding had I stuck with it but c'est la vie.

And not to keep you in suspense, here's one of the valid solutions to the puzzle:

_ _ _ _ _ q _ _  
_ _ _ q _ _ _ _  
q _ _ _ _ _ _ _  
_ _ _ _ q _ _ _  
_ _ _ _ _ _ _ q  
_ q _ _ _ _ _ _  
_ _ _ _ _ _ q _  
_ _ q _ _ _ _ _