Page 1 of 1

Help with N Queens

Posted: Thu May 16, 2013 1:16 pm
by antiloquax
I am having a play with the N Queens problem. I have some working code, but I am not very happy with it. In the program, I make a new empty and add new (partial)solutions to it before returning the current list of (partial)solutions. I think the way I have done this looks clumsy, but I can't work out another way. Any help appreciated:

Code: Select all

from time import *

def main():
    print("*** The N-Queens Problem ***")
    n = int(input("Size of board: "))
    tic = time()
    answers = nQueens(n)
    toc = time()
    print("Time: ", toc-tic)
    if not answers:
            print("No solutions.")
        for ans  in answers:

def nQueens(n):
    """Top-level function."""
    def queens(k):
        """Recursive function."""
        if k == 0:
            return [[]]
            sols = []
            for solution, row in [(s,r) for s in queens(k-1) for r in range(1, n+1)]:
                if not unsafe(solution, row):
                    sols.append(solution + [row])
        return sols
    return queens(n)

def unsafe(part, r):
    """Takes a partial solution and a row. Returns True if the queen is unsafe."""
    col = len(part)
    for i in range(col):
        if abs(part[i]-r) in (0, col-i):
            return True
    return False

if __name__ == "__main__":

Re: Help with N Queens

Posted: Fri May 17, 2013 1:21 pm
by davef21370
It may be worth using a class, that way you could create a list of Queens and add a Queen to the board by creating a new instance of the class and have a method in the class to check if it's in a safe position, if not move down (or across) a square and check again. If the Queen 'falls off' the board then delete the current Queen and move the position of the preceding one, if that one falls off do the same.

I think that sounds a bit complicated but you obviously know the n Queens problem and have an idea what I mean. Might try this myself :)


Re: Help with N Queens

Posted: Fri May 17, 2013 4:49 pm
by antiloquax
Thanks Dave. Yes, I hadn't thought of that. In fact I don't think I've ever used recursion in an OOP program. I'll have to try it.

Re: Help with N Queens

Posted: Fri May 17, 2013 6:01 pm
by johnbeetem
I've done it using a permutation method. All solutions have exactly one queen in each row, in a different column. So you simply start with N rows, each with a queen in a different column, and then enumerate all the row permutations using recursion. For each permutation, just check for diagonal captures.

This is quick and dirty, and there are probably much better methods. I implemented this in Intel 8080 ASM on my first computer, a Heathkit H-8, back in 1978 or so. For 8 queens, each row is represented as an 8-bit byte.