November 21st, 2012, 04:37 PM

NQueens problem
This is more than just frustrating!
I think most of you super PRO's are quite familiar with this problem. I am being asked to a build a function "def Queens(N)" which receives as a parameter an integer N which represents the size of an NxN chessboard where I will have to place N queens and count the amount of possibilities there is of positioning N queens on the board without having one threaten the other.
In other words, no two queens can be in the same row, column or diagonal. I have the idea of how the algorithm works, I wrote it down on paper millions of times but then I get to blank when I start the code!
Could anyone please post the way to start the function?  I thought about using a recursion but still i'm not yet into PRO programming and im just into doing simple and understandable pieces of code...
Thanks in advance.
November 22nd, 2012, 08:54 AM

Have you looked up the eight queens problem on wikipedia?
November 22nd, 2012, 03:16 PM

Originally Posted by Quackajack
Have you looked up the eight queens problem on wikipedia?
Yes, I did my research but I repeat, I am still a newbie and I don't understand all the complicated codes that are used in the given examples...
November 22nd, 2012, 11:54 PM

Code:
$ python c 'import q;q.queens(4)'
depth += 1
# Trying to place a queen on rank 1. Open files on [1, 2, 3, 4].
# Accept square a1.
depth += 1
# Trying to place a queen on rank 2. Open files on [2, 3, 4].
# a1 attacks b2
# Accept square c2.
depth += 1
# Trying to place a queen on rank 3. Open files on [2, 4].
# c2 attacks b3
# c2 attacks d3
depth = 1
# Accept square d2.
depth += 1
# Trying to place a queen on rank 3. Open files on [2, 3].
# Accept square b3.
depth += 1
# Trying to place a queen on rank 4. Open files on [3].
# b3 attacks c4
depth = 1
# a1 attacks c3
depth = 1
depth = 1
# Accept square b1.
depth += 1
# Trying to place a queen on rank 2. Open files on [1, 3, 4].
# b1 attacks a2
# b1 attacks c2
# Accept square d2.
depth += 1
# Trying to place a queen on rank 3. Open files on [1, 3].
# Accept square a3.
depth += 1
# Trying to place a queen on rank 4. Open files on [3].
# Accept square c4.
depth += 1
# Solved. We've placed all 4 queens.
[2, 4, 1, 3]
depth = 1
depth = 1
# d2 attacks c3
depth = 1
depth = 1
# Accept square c1.
depth += 1
# Trying to place a queen on rank 2. Open files on [1, 2, 4].
# Accept square a2.
depth += 1
# Trying to place a queen on rank 3. Open files on [2, 4].
# a2 attacks b3
# Accept square d3.
depth += 1
# Trying to place a queen on rank 4. Open files on [2].
# Accept square b4.
depth += 1
# Solved. We've placed all 4 queens.
[3, 1, 4, 2]
depth = 1
depth = 1
depth = 1
# c1 attacks b2
# c1 attacks d2
depth = 1
# Accept square d1.
depth += 1
# Trying to place a queen on rank 2. Open files on [1, 2, 3].
# Accept square a2.
depth += 1
# Trying to place a queen on rank 3. Open files on [2, 3].
# d1 attacks b3
# Accept square c3.
depth += 1
# Trying to place a queen on rank 4. Open files on [2].
# c3 attacks b4
depth = 1
depth = 1
# Accept square b2.
depth += 1
# Trying to place a queen on rank 3. Open files on [1, 3].
# b2 attacks a3
# b2 attacks c3
depth = 1
# d1 attacks c2
depth = 1
depth = 1
file q.py
Code:
# n queens
# recursion looks like a good choice because
# python saves the backtracking state and the
# stack depth won't be excessive.
# How do you handle solutions that are symmetrically or by rotation the same?
import string
def algebraic(f,r):
return string.ascii_lowercase[f]+string.digits[r+1]
def adjust(a):
try:
return [1+A for A in a]
except:
return 1+a
def queens(N,FILES=[]):
print('depth += 1')
RANK = len(FILES)
if N == RANK:
print("# Solved. We've placed all %d queens."%N)
print(adjust(FILES))
else:
print('# Trying to place a queen on rank %d. Open files on %s.'%(adjust(RANK),adjust(set(range(N))set(FILES))))
for FILE in set(range(N))set(FILES):
for (R,F) in enumerate(FILES):
if (F==FILE+RANKR) or (F==FILERANK+R):
print('# %s attacks %s'%(algebraic(F,R),algebraic(FILE,RANK)))
break
else:
print('# Accept square %s.'%(algebraic(FILE,RANK)))
queens(N,FILES+[FILE])
print('depth = 1')
Last edited by b49P23TIvg; November 22nd, 2012 at 11:59 PM.
[code]
Code tags[/code] are essential for python code and Makefiles!
November 24th, 2012, 01:58 PM

Originally Posted by b49P23TIvg
Code:
$ python c 'import q;q.queens(4)'
depth += 1
# Trying to place a queen on rank 1. Open files on [1, 2, 3, 4].
# Accept square a1.
depth += 1
# Trying to place a queen on rank 2. Open files on [2, 3, 4].
# a1 attacks b2
# Accept square c2.
depth += 1
# Trying to place a queen on rank 3. Open files on [2, 4].
# c2 attacks b3
# c2 attacks d3
depth = 1
# Accept square d2.
depth += 1
# Trying to place a queen on rank 3. Open files on [2, 3].
# Accept square b3.
depth += 1
# Trying to place a queen on rank 4. Open files on [3].
# b3 attacks c4
depth = 1
# a1 attacks c3
depth = 1
depth = 1
# Accept square b1.
depth += 1
# Trying to place a queen on rank 2. Open files on [1, 3, 4].
# b1 attacks a2
# b1 attacks c2
# Accept square d2.
depth += 1
# Trying to place a queen on rank 3. Open files on [1, 3].
# Accept square a3.
depth += 1
# Trying to place a queen on rank 4. Open files on [3].
# Accept square c4.
depth += 1
# Solved. We've placed all 4 queens.
[2, 4, 1, 3]
depth = 1
depth = 1
# d2 attacks c3
depth = 1
depth = 1
# Accept square c1.
depth += 1
# Trying to place a queen on rank 2. Open files on [1, 2, 4].
# Accept square a2.
depth += 1
# Trying to place a queen on rank 3. Open files on [2, 4].
# a2 attacks b3
# Accept square d3.
depth += 1
# Trying to place a queen on rank 4. Open files on [2].
# Accept square b4.
depth += 1
# Solved. We've placed all 4 queens.
[3, 1, 4, 2]
depth = 1
depth = 1
depth = 1
# c1 attacks b2
# c1 attacks d2
depth = 1
# Accept square d1.
depth += 1
# Trying to place a queen on rank 2. Open files on [1, 2, 3].
# Accept square a2.
depth += 1
# Trying to place a queen on rank 3. Open files on [2, 3].
# d1 attacks b3
# Accept square c3.
depth += 1
# Trying to place a queen on rank 4. Open files on [2].
# c3 attacks b4
depth = 1
depth = 1
# Accept square b2.
depth += 1
# Trying to place a queen on rank 3. Open files on [1, 3].
# b2 attacks a3
# b2 attacks c3
depth = 1
# d1 attacks c2
depth = 1
depth = 1
file q.py
Code:
# n queens
# recursion looks like a good choice because
# python saves the backtracking state and the
# stack depth won't be excessive.
# How do you handle solutions that are symmetrically or by rotation the same?
import string
def algebraic(f,r):
return string.ascii_lowercase[f]+string.digits[r+1]
def adjust(a):
try:
return [1+A for A in a]
except:
return 1+a
def queens(N,FILES=[]):
print('depth += 1')
RANK = len(FILES)
if N == RANK:
print("# Solved. We've placed all %d queens."%N)
print(adjust(FILES))
else:
print('# Trying to place a queen on rank %d. Open files on %s.'%(adjust(RANK),adjust(set(range(N))set(FILES))))
for FILE in set(range(N))set(FILES):
for (R,F) in enumerate(FILES):
if (F==FILE+RANKR) or (F==FILERANK+R):
print('# %s attacks %s'%(algebraic(F,R),algebraic(FILE,RANK)))
break
else:
print('# Accept square %s.'%(algebraic(FILE,RANK)))
queens(N,FILES+[FILE])
print('depth = 1')
That's one hella big piece of code...
The thing is that i'm trying so hard to work this out using a single List. For example, I am working on a 8x8 chessboard, thus i'm using an 8 elements list where each index points at a column and the value inside of a certain index (column) points at the row that the queen is at.
I am so lost in the recursion and I could really use some help here :(
I am not allowed to use "enumeration"; in fact I don't even know what it is XD please consider :] i'm just 3 weeks into college and it is a nightmare when it gets to crazy codes!
November 24th, 2012, 03:07 PM

The program is 28 lines long, much of which is just to explain what it is doing. The first block is output from a 4x4 chessboard. I see now that I inconsistently named files with algebraic notation (letters) and numbers. I suppose I could try again showing diagrams.
Post your effort, we'll try to explain or fix it.
[code]
Code tags[/code] are essential for python code and Makefiles!
November 25th, 2012, 02:24 PM

Originally Posted by b49P23TIvg
The program is 28 lines long, much of which is just to explain what it is doing. The first block is output from a 4x4 chessboard. I see now that I inconsistently named files with algebraic notation (letters) and numbers. I suppose I could try again showing diagrams.
Post your effort, we'll try to explain or fix it.
Alright! I managed to get out of this question! but for checking purposes; is the answer 92 possibilities in a 8x8 chessboard?
November 25th, 2012, 04:17 PM

Well, Mr/Ms "Yes, I did my research", I got 92 solutions for an 8x8 board, as did the wikipedia article, of which they draw the unique solutions after accounting for translation and rotation.
Now, did you learn anything about recursion?
[code]
Code tags[/code] are essential for python code and Makefiles!
November 26th, 2012, 03:44 AM

Originally Posted by b49P23TIvg
Well, Mr/Ms "Yes, I did my research", I got 92 solutions for an 8x8 board, as did the
wikipedia article, of which they draw the unique solutions after accounting for translation and rotation.
Now, did you learn anything about recursion?
Absolutely!