An easy to understand solution to the eight queens problem in python

Sunday, July 1, 2012

This is a simplified version of the famous eight queens problem, often I wondered on how I could I write recursive code for this which would exactly simulate the way one would place the queens on the board manually and remove them from a given position if it isn't the right position and once a solution is found, move on with the next till all solutions were found.

Accordingly this code models the board as a python list and add and remove methods simulate placing and removing a queen from a specific position in the board, hopefully this one will make the understanding part of it little easier and simpler.

Listing 1: eight_queens.py

""" A simple solution to 8 queens problem for easier
    understanding with the board modeled
    as a list and append/remove methods simulate
    placing/removing the queen from the board till
    one correct solution is reached and continues
    from there

    Author: S.Prasanna
    Copyright (C) 2011 by S.Prasanna.
"""

board = []
size = 8

def danger(row, col):
    """ Return if there is a danger by placing queen in
        a given row, col
    """
    for (i, j) in board:
        if row == i: return True
        if col == j: return True
        if abs(row - i) == abs(col - j): return True

    return False
    
def placequeen(row):
    if row > size:
        print board
    else:
        for col in range(1, size + 1):
            if not danger(row, col):
                board.append((row, col))
                placequeen(row + 1)
                board.remove((row,col))

if __name__ == "__main__":
    placequeen(1)
Syntax highlighter: Pygments

Sample Output:

For a board of size 4:

[(1, 2), (2, 4), (3, 1), (4, 3)]
[(1, 3), (2, 1), (3, 4), (4, 2)]

11 comments:

Vasilis Saltis said...

Great code!
Much more understandable than the on in the samples in wiki python! And almost same speed.

Yashpal Singh said...

great piece of simple code...

Amit said...

If i change the size to 16, the code keeps generating output and does not stop, plz help

Anonymous said...

great code. Can be made simpler by deleting

if row == i: return True

as it is a redundant check

Prasanna Seshadri said...

Thanks for finding it out. Will update.

Anonymous said...

for the size 8, I'm getting so many different prints of boards.. are they the different arrangements of the board or is it an error?

Anonymous said...

Why did we remove (row,column) in the last step?

Anonymous said...

you remove because if it will not successfully place it on that position, we'll back up and try again.

Anonymous said...

hello,anybody pls help how to display the solution like aboard
eg:for solution:[(1, 2), (2, 4), (3, 1), (4, 3)]
the output should be:
0 x 0 0
0 0 0 x
x 0 0 0
0 0 x 0

Bhagyashri Bhandare said...

code is helpful for us...thank you

Anonymous said...

but remove(remove,column) should not be in the if statement I think.Can anyone explain that step please?


Copyright © 2016 Prasanna Seshadri, www.prasannatech.net, All Rights Reserved.
No part of the content or this site may be reproduced without prior written permission of the author.