antiloquax
Posts: 406
Joined: Sun Nov 20, 2011 11:37 am
Contact: Website

Help with N Queens

Thu May 16, 2013 1:16 pm

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

 # nqueens.py
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.")
    else:
        for ans  in answers:
            print(ans)

def nQueens(n):
    """Top-level function."""
    def queens(k):
        """Recursive function."""
        if k == 0:
            return [[]]
        else:
            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__":
    main()

User avatar
davef21370
Posts: 897
Joined: Fri Sep 21, 2012 4:13 pm
Location: Earth But Not Grounded

Re: Help with N Queens

Fri May 17, 2013 1:21 pm

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 :)

Dave.
Apple say... Monkey do !!

antiloquax
Posts: 406
Joined: Sun Nov 20, 2011 11:37 am
Contact: Website

Re: Help with N Queens

Fri May 17, 2013 4:49 pm

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.
mark

User avatar
johnbeetem
Posts: 944
Joined: Mon Oct 17, 2011 11:18 pm
Location: The Coast
Contact: Website

Re: Help with N Queens

Fri May 17, 2013 6:01 pm

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.

Return to “Python”