## Help with N Queens

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

### Help with N Queens

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()
``````

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

### Re: Help with N Queens

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

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

johnbeetem
Posts: 945
Joined: Mon Oct 17, 2011 11:18 pm
Location: The Mountains
Contact: Website

### Re: Help with N Queens

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.