Page 1 of 1

Help with N Queens

Posted: 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()
toc = time()
print("Time: ", toc-tic)
print("No solutions.")
else:
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()
``````

Re: Help with N Queens

Posted: 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.

Re: Help with N Queens

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

Re: Help with N Queens

Posted: 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.